Sortowanie przez scalanie w Javie

Każdy programista musi najpierw przemyśleć schemat/plan/architekturę przyszłej pracy, inaczej wszystko skończy się bałaganem i kompletną anarchią. Jak w przypadku każdego postu, na początku potrzebujesz planu, zaczynajmy.

• 1) Weźmy temat sortowania przez scalanie dla początkujących.
• 2) Stworzymy architekturę i plan dalszej pracy.
• 3) Przepracujemy i opiszemy wszystkie części planu.
• 4) Sprawdźmy wydajność i jakość.

• 2.1) Co to jest sortowanie przez scalanie.
• 2.2) Opis możliwych podpisów.
• 2.3) Podaj przykład.
• 2.4) Opisz implementację w Javie na przykładzie.
• 2.5) Wszystko ekstra.

Scal - sortowanie przez scalanie w Javie

Wyraża zasadę „dziel i rządź”. Jaki jest pomysł i jego znaczenie?

1. Sortowanie.

   Dzielimy tablicę na części, aż będzie równa 1 elementowi. Sortowany jest każdy 1 element.

2. Połączenie.

   Łączenie posortowanych elementów.
   Oparty na zasadzie dwóch talii kart. Na stół kładziemy 2 talie kart wartościami do góry, a kartę o najniższej wartości umieszczamy na trzecim powstałym stosie kart. Docelowo, jeśli w danej talii skończą nam się karty, przenosimy je jedna po drugiej do powstałej talii. Rezultatem będzie połączenie dwóch posortowanych tablic, jedna nowa, posortowana tablica.

Czas spędzony wynosi O(n log2 n). Sortowanie uważa się za dość szybkie. Krótko o złożoności algorytmicznej, jeśli ktoś potrzebuje.Często można zobaczyć funkcje takie jak:

Sort(A, p, q);
Merge(A, p, q, r);

To mniej więcej to samo, tylko powiązane z indeksami. Zmienne w nich to:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

Jeśli te zmienne nie zostaną opisane, to ten, kto sam prosi o wykonanie takiej funkcji, nie wie, czego chce. Będziesz musiał przeszukać Google, aby dowiedzieć się, co to jest, prawdopodobnie znajdziesz to, być może. Podajmy przykład naszego sortowania. Istnieje tablica {6, 1, 3, 5, 2, 4, 7, 8}, jeśli jej długość jest większa niż 1, to dzielimy ją na 2 części i otrzymujemy część lewą {6, 1, 3, 5}i prawą {2, 4, 7, 8}. Kontynuujemy akcję dzielenia na 2 części, aż jej długość będzie większa niż 1. W rezultacie otrzymamy pęczek tablic o długości 1 elementu, a mianowicie: {6} {1} {3} {5} {2} {4} {7} {8}. Implementacja w Javie wygląda mniej więcej tak:

public int [] sortArray(int[] arrayA){ // sortowanie Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Następnie musisz połączyć te tablice w 1. Jak to się robi? Aby uniknąć wielokrotnego przeglądania każdej tablicy, wprowadźmy indeksy pozycji dla każdej tablicy. Następnie przejdziemy przez pętlę raz, równą długości sumy tych dwóch tablic. Weź pierwszą tablicę i drugą tablicę, weź pierwszy element, porównaj element nr 1 w pierwszej tablicy z elementem nr 1 w drugiej tablicy ? Mniejszy z nich jest umieszczany w wynikowej tablicy. Ważne jest tutaj, że jeśli wzięliśmy element z pierwszej tablicy, to po przejściu pętli powinna ona odnosić się do 2. elementu pierwszej tablicy i do 1. elementu drugiej tablicy. W tym celu należy zwiększyć indeks drugiej tablicy o +1 i podczas sprawdzania odjąć go od numeru cyklu, analogicznie dla pierwszej tablicy. Czy jest jasne, dlaczego to zrobić? A może nic nie jest jasne? :-) Na przykład są 2 tablice: {1}{4}{8}i {3}{6}{7} I jest pętla:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

Przy pierwszym przebiegu pętli okazuje się, że arrayC[1] = {1}: wzięliśmy ten element z pierwszej tablicy. Następnie, przechodząc przez drugą pętlę, musimy już porównać element {4}i {3}, ale aby to zrobić, musimy wziąć pod uwagę indeksy pozycji i przesunięcie obu tablic, w tym celu je wprowadzamy.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

Ale to nie wszystko, trzeba liczyć się z tym, że niektóre tablice mogą zakończyć się wcześniej. Na przykład są 3 tablice: {1}{3}{5}i {6}{7}{9} Pierwsza tablica zakończy się przed przybyciem drugiej, w tym celu należy wprowadzić czek i w zasadzie funkcja scalania jest gotowa.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

Najtrudniejszą rzeczą w tym sortowaniu jest zasada przejścia rekursyjnego. Te. wrzucamy lewą stronę do rekurencji, aż będzie podzielna przez 2, a następnie rozwijamy ją z powrotem, słowami jest to bardzo skomplikowane i zagmatwane, ale kiedy próbujesz sobie wyobrazić, jeśli nie jest to jeszcze jasne, to jest kompletny bałagan. Weźmy tablicę: {2}{1}{4}{3}. Pierwsza rekursja sortowania podzieli go na 2 części i uruchomi funkcję ponownie z elementami 2-1 , a następnie ponownie z elementami 2 i 1 , zwróci je po kolei, aby najpierw doszły do ​​funkcji scalającej, a przyjdzie 1-2 out , wtedy rekurencja powróci i wrzuci 4-3 do scalania , następnie 4 i 3 , po czym scalanie zwróci 3-4 i dopiero wtedy rekurencja ponownie się zawróci i 1-2 i 3-4 zostaną zostanie uwzględniony w procesie scalania , a posortowana tablica zostanie zwrócona jako 1-2-3-4 . Cóż, to wszystko, sortowanie składa się z dwóch funkcji.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

Jeśli zapiszesz jakiś rodzaj głównego, otrzymasz coś takiego:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

Dla mnie to sortowanie to kompletna porażka, było milion pytań, ale żadnych odpowiedzi, przekopałem cały Internet, przeczytałem ponownie, obejrzałem mnóstwo filmów, ale jak zwykle sam znalazłem odpowiedzi. I dopiero wtedy, gdy zacząłem pisać rozwiązanie zupełnie inne niż to, które wszędzie miga) Ale ostatecznie okazało się, że jest podobne do wszystkich innych))) Sortowanie jest w rzeczywistości najprostsze, najważniejsze jest, aby zaprezentować je interaktywnie w akcji i wszystko się układa, jak ogarniesz, nakręcę film)))) Na razie wystarczy mi tylko: Sortowanie przez scalanie Sortowanie przez scalanie Najważniejsze jest, aby zawsze planować od początek. Lepiej trochę poczekać i pomyśleć, zanim zaczniesz cokolwiek robić. Może to zająć więcej czasu, ale zamiast konieczności przepisywania go kilka razy i wymyślania kul, pojawi się zrozumienie i rozwiązanie. Dziękuję wszystkim za poświęcony czas, życzę powodzenia i dobrego nastroju. ) PS: Krytyka, dobra i zła, a także pytania są bardzo mile widziane. )))