Tagi: Sortuj bubble Si, sortowanie bąbelkowe, sortowanie bubble dwuwymiarową tablicę
Sortuj bubble.
A akt algorytmu jest bardzo prosty. Przechodzimy przez tablicę liczb i sprawdzamy zamówienie (następny numer powinien być bardziej równy poprzednim), gdy tylko natknęli się na naruszenie zamówienia, natychmiast wymieniać elementy w miejscach, osiągamy koniec Tablica, a następnie zacznij pierwszy.
Sortuj tablicę (1, 5, 2, 7, 6, 3)
Idziemy na masyw, sprawdź pierwszy numer, a drugi, idą w porządku rosnącym. Następnie jest naruszenie zamówienia, zmieniamy te elementy
1, 2, 5, 7, 6, 3
Nadal przechodzimy przez tablicę, 7 więcej niż 5, ale 6 mniej, więc wymieniamy z miejsc
1, 2, 5, 6, 7, 3
3 narusza zamówienie, zmień miejsca od 7
1, 2, 5, 6, 3, 7
Wracamy do początku tablicy i róbmy to samo
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Mówi się, że jest to podobny do "pływających" elementów "płuc", takich jak baniek, dlatego algorytm i otrzymał taką nazwę. void bubbesort (Int * A, rozmiar_t, rozmiar) (rozmiar_t i, j; int tmp; dla (i \u003d 1; ja< size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) (tmp \u003d a [j]; a [j] \u003d a; a \u003d tmp;))))
Algorytm ten zawsze zrobi (N-1) 2 kroki, niezależnie od danych wejściowych. Nawet jeśli tablica jest posortowana, nadal będzie przekazywany (n-1) 2 razy. Ponadto już posortowane dane zostaną ponownie sprawdzane.
Niech konieczne, aby posortować tablicę 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Po zmianie w miejscach elementu a i nie ma potrzeby przekazania tej sekcji tablicy. Bierzemy go pod uwagę i domniemany algorytm
Void bubblesort2 (int * A, rozmiar_t) (rozmiar_t i, j; int tmp; dla (i \u003d 1; ja< size; i++) { for (j = i; j > 0; j--) (jeśli (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
Kolejna realizacja
Void bubblesort2b (Int * a, rozmiar_t) (size_t i, j; int tmp; dla (i \u003d 1; ja< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }
W tym przypadku będzie pół mniejszych kroków, ale nadal problem sortowania już posortowanej tablicy pozostaje: musisz to zrobić, aby posortowana tablica jest oglądana raz. Aby to zrobić, wprowadź zmienną flagą: zostanie pominięty (flag \u003d 0), jeśli tablica jest sortowana. Gdy tylko pójdziemy na naruszenie zamówienia, flaga zostanie podniesiona (flaga \u003d 1) i zaczniemy sortować tablicę jak zwykle.
Void bubblesort3 (Int * A, rozmiar_g, Size_t) (size_t i; int tmp; flaga znakowa; zrobić (flag \u003d 0; dla (i \u003d 1; ja< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }
W tym przypadku złożoność znajduje się również o N2, ale w przypadku posortowanej tablicy, będzie tylko jeden fragment.
Teraz popraw algorytm. Napiszymy funkcję formularza ogólnego, tak aby posortował tablicę typu Void. Ponieważ rodzaj zmiennej nie jest znany, konieczne będzie dalsze przekazywanie rozmiaru jednego elementu tablicy i funkcji porównania.
Int intsort (const void * a, const void * b) (powrót * ((int *) a)\u003e * ((int *) b);) void bubblesort3g (nieważny element * A, element_t, rozmiar_t, Int (*) CMP) (Const Void *, Const Void *)) (size_t i; void * tmp \u003d null; flaga znakowa; tmp \u003d malloc (element); do (flag \u003d 0; dla (i \u003d 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }
Funkcja wygląda brzydki - często obliczany jest adres prądu i poprzedniego elementu. Wyróżniamy dla tego oddzielne zmienne.
Void bubblesort3gi (pustka * A, rozmiar size_t, rozmiar_t, Int (* cmp) (const void *, const void *)) (size_t i; void * tmp \u003d null; void * prev, * cur; char flag; tmp \u003d malloc (element); zrobić (flag \u003d 0; i \u003d 1; prev \u003d (char *) a; cur \u003d (char *) prev + element; podczas gdy (ja< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }
Teraz z tymi funkcjami można sortować tablice dowolnego typu
Nieważne główne () (int a \u003d (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int I; bubblesort3gi (A, rozmiarof (int), 10, intsort); dla (i \u003d 0; ja< 10; i++) { printf("%d ", a[i]); } _getch(); }
Sortowanie wielowymiarowej tablicy
Statyczna wielowymiarowa tablica jest zasadniczo różna od sortowania jednowymiarowa. Możesz użyć właściwości, że statyczne jednoimensowe i wielowymiarowe tablice mają ten sam widok w pamięci.
Nieważne główne () (int a \u003d (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubblesort3gi (A, rozmiarof (int), 9, intsort); dla (i i \u003d 0; ja< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include
Po drugie, możesz najpierw przesunąć tablicę do jednego wymiarowego, sortuj tablicę jednowymiarową, a następnie przesuń go z powrotem do dwuwymiarowej.
Void bubblesort3gi2d (void ** A, rozmiar_t, size_t m, size_t n, int (* cmp) (const void *, const void *)) (rozmiar_t size \u003d m * n, sub_size \u003d n * element; size_t i, j , k; void * arr \u003d malloc (rozmiar * element); char * p1d \u003d (Char *) arr; Char * P2D \u003d (Char *) A; // Skopiuj dwuwymiarowy typ pustki w jeden wymiarowy dla (i \u003d 0; ja< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }
Jeśli ta funkcja cię myli, użyj wpisanego. Zadzwoń z poprzedniego przykładu
Umieściamy tablicę od góry do dołu, od elementu zerowego do ostatniego.
Idea metody: krok sortowania polega na przejściu z dołu w górę tablicy. Po drodze są pary sąsiednich elementów. Jeśli elementy niektórych par są w złym porządku, zmienimy je w miejscach.
Po przejściu zerowego przez tablicę "Top" okazuje się najbardziej "lekki" element - stąd analogię z bańką. Poniższy fragment jest wykonany do drugiego elementu z góry, więc drugi co do wielkości element wznosi się do właściwej pozycji ...
Wykonujemy przejścia dla całej malejącej dolnej części tablicy, dopóki nie pozostanie w nim tylko jeden element. Na tym końcu sortowania, ponieważ sekwencja jest uporządkowana rosnąco.
Szablon.
Średnia liczba porównania i wymiany mają porządek kwadratowy wzrostu: THETA (N 2), stąd można stwierdzić, że algorytm bąbelkowy jest bardzo powolny i jest nieskuteczny.
Niemniej jednak ma ogromny plus: jest prosty i można go ulepszyć w jakikolwiek sposób. Co teraz pójdziemy.
Najpierw rozważ sytuację, gdy żadna wymiana nie nastąpiła na żadnej z przełęczy. Co to znaczy?
Oznacza to, że wszystkie pary znajdują się w odpowiedniej kolejności, więc tablica jest już posortowana. I kontynuować proces nie ma sensu (zwłaszcza jeśli tablica została posortowana od samego początku!).
Pierwszą poprawą algorytmu jest pamiętanie, czy na tym przejściu dokonano żadnej wymiany. Jeśli nie, algorytm kończy pracę.
Proces poprawy można kontynuować, jeśli pamiętasz nie tylko fakt wymiany, ale także wskaźnik ostatniej wymiany k. Rzeczywiście: wszystkie pary pakietu elementów z indeksami, mniejsze K, są już umieszczone w żądanej kolejności. Dalsze przejścia można zakończyć w indeksie K, zamiast przeprowadzić się do wersji górnej granicy, którą zainstalowałem z wyprzedzeniem.
Jakościowo, kolejna poprawa algorytmu można uzyskać z następującej obserwacji. Chociaż bańki lekki z dna wzrośnie w jednym przejściu, ciężkie pęcherzyki są obniżone przy minimalnej prędkości: jeden krok do iteracji. Tak więc tablicę 2 3 4 5 6 1 będzie sortowane w 1 przejściu, a sortowanie sekwencji 6 1 2 3 4 5 będzie wymagało 5 przejść.
Aby uniknąć podobnego efektu, można zmienić kierunek następnego przez inne przejścia. Wynikowy algorytm jest czasami nazywany " sortowanie shaker.".
Szablon.
Jak opisane zmiany wpłynęły na skuteczność metody? Średnia liczba porównań, choć zmniejszyła się, ale pozostaje o (n 2), podczas gdy liczba wymiany nie zmieniła się w żaden sposób. Średnia (jest najgorsza) liczba operacji pozostaje kwadratowa.
Dodatkowa pamięć jest oczywiście nie wymagana. Zachowanie ulepszonej (ale nie wstępnej) metody jest raczej naturalne, prawie posortowane tablicę będzie sortowane znacznie szybciej. Sortuj bubble jest stabilny, ale sortowanie shaker traci tę jakość.
W praktyce metoda bąbelkowa, nawet z ulepszeniami, pracami, niestosami, zbyt wolnymi. Dlatego - prawie nie ma zastosowania.
Wszyscy wiedzą, że od klasy wymiany sortowania najszybsza metoda jest tak zwana szybkie sortowanie. Rozprawy są pisane o niej, istnieje wiele artykułów na temat Habré, opiera się na złożonych algorytmach hybrydowych na nim. Ale dzisiaj nie będzie szybkie sortowanie., ale o kolejnej metodzie wymiany - stare dobre sortowanie bąbelkowe. oraz jego ulepszenia, modyfikacje, mutacje i odmiany.
Praktyczne wyczekiwanie tych metod nie jest AHTI. Jakie wiele z habies jest utrzymywane wszystkie w pierwszej klasie. W związku z tym artykuł skierowany jest do tych, którzy są po prostu zainteresowani teorią algorytmów i dokonuje pierwszych kroków w tym kierunku.
obraz: bąbelki.
Dzisiaj porozmawiamy o najprostszym wymiany sortowania..
Jeśli ktoś jest zainteresowany, powiem, że są inne klasy - sortowanie wyboru, wkładki sortowania., sortowanie fuzji, dystrybucja sortowania, sortowanie hybrydowe. i sortowanie równoległe.. Przy okazji, nadal jest sortowanie ezoteryczne.. Są to różne fałszywe, zasadniczo niezrealizowane, komiczne i inne pseudo-algorytmy, o których piszę kilka artykułów w piniu "It-humor".
Ale dzisiejszy wykład, nie jest związany, jesteśmy teraz zainteresowani tylko dla bezpretensjonalnego sortowania przez wymianę. Sortowanie się, istnieje również wiele giełdów (wiem więcej niż kilkanaście), więc uważamy za tzw sortowanie bąbelkowe. I niektóre inne, z nim ściśle ze sobą powiązane.
Ostrzeżenie z góry, że prawie wszystkie powyższe metody są bardzo powolne, a głęboka analiza ich tymczasowej złożoności nie będzie. Niektórzy szybciej, niektóre z najbardziej pamiętnych, ale z grubsza mówiąc, możemy to powiedzieć średnio O.(n2.). Nie widzę też powodu, aby sprzęgnąć artykuł przez wdrożenia w żadnych językach programowania. Zainteresowany bez najmniejszej pracy będzie można znaleźć przykłady kodu na rozecie, Wikipedii lub gdzieś indziej.
Ale z powrotem do wymiany sortowania. Układ występuje w wyniku wielu spójnych wyliczeń tablicy i porównania parametrów elementów między sobą. Jeśli porównywane elementy nie są sortowane przez siebie, zmienimy je w miejscach. Jedyne pytanie brzmi dokładnie, co Makarska tablica do obejścia i jaką zasadę wybrać parę do porównania.
Zacznijmy nie z sortowaniem bańki odniesienia, ale z algorytmu zwanego ...
Głupie sortowanie
Sortowanie i naprawdę głupi. Wyświetlamy tablicę w lewo i w prawo i po drodze porównując sąsiedzi. Jeśli spełnimy kilka wzajemnie nieskorygowanych elementów, zmienimy je w miejscach i wrócimy do kręgów, a potem masz na myśli na samym początku. Przechodzimy, sprawdź tablicę, jeśli spotkali się ponownie "złe" kilka sąsiednich elementów, a następnie zmieniamy w miejscach i znowu rozpoczynamy wszystkie Syzdnov. Kontynuujemy, aż tablica jest powoli posortowana."Więc każdy głupiec jest w stanie uporządkować" - powiesz, a będziesz absolutnie rację. Dlatego sortowanie i nazwano "głupi". W tym wykładzie konsekwentnie poprawimy i modyfikujemy tę metodę. Teraz ma tymczasową złożoność O.(n 3.), wytwarzając jedną korektę, wniesiemy O.(n2.), a potem przyspieszysz trochę więcej, a potem, a w końcu dostajemy O.(n. Log. n.) - I nie będzie "szybkiego sortowania"!
Wprowadzamy jedną poprawę głupiego rodzaju. Uważając, że dwa sąsiednie nieużywane elementy podczas przechodzenia i zmieniając je w miejscach, nie wrócę do początku tablicy i spokojnie pomijając jego obwodnicę do samego końca.
W tym przypadku przed nami nie jest niczym więcej niż słynnym ...
Sortowanie bąbelkowe
Lub sortuj według prostych wymian. Immortal klasyczny gatunek. Zasada działania jest prosta: omijanie tablicy od początku do końca, przechodząc przylegające sąsiednie elementy po drodze. W wyniku pierwszego przejścia maksymalny element "pojawi się". Teraz musimy przejść do niesłusznej części tablicy (od pierwszego elementu na przedostatni) i zmienić wzdłuż ścieżki niesolontowanych sąsiadów. Drugim co do wielkości elementem będzie na przedostatnim miejscu. Kontynuując w tym samym duchu, obejmiemy całą malejącą nieskalową część tablicy, przesunięcie znalezionego maxima do końca.Jeśli nie tylko umieścić maksimę, aby umieścić maximę, a także na początku, aby przenieść minimum, a następnie mamy ...
Sortowanie shakera.
jest sortuj według mieszania, jest sortowanie koktajlowe.. Proces zaczyna się jak w "Bubble": wyciskamy maksimum na podwórkach. Następnie obracamy się do 180 0 i przejdziemy w przeciwnym kierunku, a jednocześnie płacisz na początku, a nie maksimum i przynajmniej. Po posortowaniu pierwszych i ostatnich elementów w tablicy, znów robimy olcha. Kilkakrotnie spacerując z powrotem, w wyniku, zakończ proces, będąc na środku listy.Sortowanie shakera działa trochę szybciej niż bańka, ponieważ masyw we właściwych kierunkach na przemian migruje Maksimę i Minimę. Ulepszenia, jak mówią, jest oczywiste.
Jak widać, jeśli jest kreatywny, wyrzucanie ciężkich (płuc) elementów do końców tablicy jest szybsze. Dlatego rzemieślnicy oferowali kolejny niestandardowy "drogowy", aby ominąć listę.
Równomierne sortowanie
Tym razem nie rozbawimy się na grzbiecie i odwrócimy się i wrócimy do pomysłu systematycznego czołgu z powrotem w prawo, ale tylko większy krok. Na pierwszym przełęczeniu elementy z dziwnym kluczem porównują z sąsiadami, które rosną przy głosowaniu (1 th w porównaniu z 2, potem 3 z 4, 5 z 6 i tak dalej). Następnie, przeciwnie, "elementy" czytają ", porównując / zmienić za pomocą" dziwnych ". Potem znowu jest coś "coś", a potem znowu "nawet nacięcie". Proces zatrzymuje się, gdy po zamówieniu dwóch przechodzi wzdłuż masywu ("dziwak-czarny" i "ballotless"), nie wystąpiła pojedyncza wymiana. Stało się sortowane.W zwykłej "bańce" podczas każdego przejścia, wyciskamy obecną maksimum na końcu tablicy. Jeśli przesuniesz eksplozję zapytanych i nieparzystych indeksów, natychmiast wszystkie mniej więcej dużych elementów tablicy jednocześnie w jednym przebiegu są wciśnięte w prawo do jednej pozycji. Więc okazuje się szybciej.
Szoliliśmy ten ostatni namalowany* dla Sortannya bulbashko.** - Sortanna Grebinets.***. Ta metoda organizuje dość szybko, O.(n2.) - jego najgorsza złożoność. Średnio mamy O.(n. Log. n.) i najlepsi nawet nie wierz O.(n.). To jest bardzo godny konkurent do każdego "szybkiego sortowania" i tego, zawiadomienie, bez użycia rekurencji. Obiecałem jednak, że w przelotowej prędkości nie będziemy zagłębiać się w prędkość rejsową, będę milczeć i wyłączyć go bezpośrednio do algorytmu.
Żółw do obudowy
Mała prehistoria. W 1980 r. Vlodzimezh Doboshevich wyjaśnił, dlaczego bąbelki i sortowanie pochodne działają tak powoli. To wszystko ze względu na żółwie. "Turtles" - małe przedmioty na końcu listy. Jako możesz zauważyć sortowanie bąbelkowe skoncentrowane na "królikach" (nie należy mylić z "królikami" babushkina) - duże na znaczeniu elementów na początku listy. Są bardzo mocno poruszające się do końca. Ale wolno satysfakcjonujące gady czołgają się niechętnie. Dostosowany "Tortila" może używać obliczenia.obraz: Żółw winy
Sortuj kalkulację
W "Bubble", "Shaker" i "Nawocny", z masywem w tablicy porównano sąsiednie elementy. Główną ideą "obliczeń" jest początkowo przyjmowanie wystarczająco dużej odległości między komponowanymi elementami, a wraz z tablicą powstaje z tablicy, zależy to do minimum. Tak więc, jak połączamy tablicę, stopniowo wygładzając na coraz bardziej schludnych pasmach.Początkowa luka między komponowanymi elementami jest lepiej nie brać żadnych ABBA, ale biorąc pod uwagę szczególną wielkość wywoływanej współczynnik zmniejszony, o optymalnej wartości wynosi około 1,247. Po pierwsze, odległość między elementami jest równa wielkości stałej tablicy zmniejsz czynnik (Wynik, naturalnie, jest zaokrąglony do najbliższej całości). Następnie przechodząc tablicę z tym krokiem, dzielimy krok zmniejsz czynnik I ponownie przejdziemy przez listę. Kontynuuje to, dopóki różnice indeksu osiągnie jednostkę. W takim przypadku tablica jest niepowiązana przez konwencjonalną bańkę.
Doświadczony i teoretyczny sposób jest optymalną wartością. współczynnik zmniejszony:
Gdy ta metoda została wymyślona, \u200b\u200bniewielu osób zwróciła na to uwagi na złącze lat 70. i 80.. Dekada później, gdy programowanie przestał być wielu naukowcami i inżynierami IBM, a już lawina zyskała ogromną naturę, metoda została ponownie otwarta, zbadana i spopularyzowana w 1991 r. Stephen Lacey i Richard Boxing.
Właściwie to wszystko, co chciałem opowiedzieć o bąbelku, a inni lubią to.
- Uwagi
* Malowane ( ukr.) - poprawa
** sortvania bulbashko ( ukr.) - Sortuj bubble
*** Sorthanny Grebinzts ( ukr.) - Sortowanie obliczeń
Cześć wszystkim!
Dziś zbadamy sortowanie metodą "Bubble". Algorytm ten jest często używany w szkołach i uniwersytetach, więc użyjemy języka Pascala. I co to jest sortowanie? Sortowanie jest zamawianie elementów z mniejszych do większej liczby (sortowanie w rosnącym) lub z większego elementu do mniejszego (sortowanie malejące). Sortuj zwykle tablice.
Istnieją różne algorytmy sortowania. Niektóre, cóż, sortują dużą liczbę elementów, innych, bardziej wydajnych z bardzo małą liczbą przedmiotów. Nasza metoda bąbelka jest charakterystyczna:
Plusy:
- Łatwy do wdrożenia algorytmu
- Piękne imię
- Jedna z najwolniejszych metod sortowania (czujno czasu wykonania, zależy od długości tablicy n2)
- Prawie nieużywane w prawdziwym życiu (używane głównie do celów szkoleniowych)
Algorytm: Podejmujemy element tablicy, porównaj z następującymi elementami, jeśli nasz element, więcej niż następny element, zmienimy je w miejscach. Po przejściu przez całą tablicę możemy być pewni, że maksymalny element będzie "wypchnięty" - i najwyżej stań. Tak więc jeden element jest już dokładnie w ich miejscu. Dlatego Musimy umieścić je wszystkie w naszym miejscu, dlatego musimy powtórzyć tę operację, tyle razy, ile mamy elementy tablicy minus 1. Ostatni element automatycznie stanie się automatycznie, jeśli stojak reszty w ich miejscach.
Wróćmy do naszej tablicy: 3 1 4 2
Bierzemy pierwszy element "3" w porównaniu z następującymi "1". Dlatego "3"\u003e "1", a następnie zmienamy miejsca:
1 3 4 2
Teraz porównywanie "3" i "4", trojka nie jest więcej niż czwarta, to nic nie znaczy. Następnie porównaj "4" i "2". Cztery więcej niż dwa - oznacza, że \u200b\u200bzmieniamy miejsca: 1 3 2 4. Cykl zakończył się. Więc największym elementem musi już stać na swoim miejscu !! Widzimy, że się wydarzyliśmy. Gdziekolwiek "4" (nasz największy element) nie był - wciąż jest, po przejściu przez cykl całej tablicy, będzie to ostatni. Analogia - jak bańka powietrza pływa w wodzie - oba nasz element wyskakuje w tablicy. Dlatego algorytm nazywany jest "sortowaniem bańki". Aby ustawić następny element, musisz najpierw uruchomić cykl, ale ostatni element nie można już rozważyć, ponieważ jest na swoim miejscu.
Porównaj "1" i "3" - nie zmieniamy niczego.
Porównaj "3" i "2" - trzy więcej niż dwa, wtedy zmieniamy miejsca. Okazuje się: 1 2 3 4. Drugi cykl został zakończony. Dokonaliśmy już dwóch cykli - oznacza to, że możemy powiedzieć, że mamy, dwa ostatnie elementy są już posortowane. Pozostaje sortować trzeci element, a czwarty, automatycznie wzrośnie we właściwym miejscu. Po raz kolejny porównujemy pierwszy element i drugi - widzimy, że mamy wszystko w naszych miejscach, oznacza to, że można rozważyć tablicę, posortowany przez zwiększenie elementów.
Teraz pozostaje zaprogramowanie algorytmu w języku Pascala. const n \u003d 4; (Przynosimy stałą, będzie to długość tablicy) Var I, J, K: Integer; (Dwie zmienne dla zainwestowanego cyklu, jeden w celu zmiany elementów w miejscach) M: macierz o liczbie całkowitej; (Przynosimy tablicę) Rozpocznij (poprosimy o tablicę z klawiatury :) Writeln ("Wpisz tablicę:"); Dla I: \u003d 1 do n rozpocznij Writeln (I, "Element:"); Readln (M [I]); koniec; (Cykl zewnętrzny jest odpowiedzialny za fakt, że musimy powtórzyć cykl wewnętrzny tyle razy, jak elementy tablicy minusa 1.) dla I: \u003d 1 do N-1 rozpocznij (rozpocznij cykl wewnętrzny już przenosi elementy i porównuje się nawzajem.) Dla J: \u003d 1 do NI rozpocznij (jeśli element, więcej niż następny, a następnie zmienić miejsca.) Jeśli M [J]\u003e Mężczyźni zaczynają k: \u003d M [J]; m [j]: \u003d m; M: \u003d k; koniec; koniec; koniec; (Wyjście wynik :) dla I: \u003d 1 do n pisz (m [i], ""); koniec.
Oto wynik: 
Ale samouczek wideo
Sortuj bubble - najprostszy algorytm sortowania stosowany wyłącznie do celów szkoleniowych. Nie ma praktycznej aplikacji do tego algorytmu, ponieważ nie jest skuteczne, zwłaszcza jeśli konieczne jest posortowanie tablicy wielkości. Plusy sortowania bańki obejmują prostotę realizacji algorytmu.
Bańka algorytmu sortowania spada do powtórzenia fragmentów przez elementy posortowanej tablicy. Przejście elementów tablicy wykonuje cykl wewnętrzny. Dla każdego przejścia dwa sąsiednie elementy są porównywane, a jeśli kolejność nieprawidłowych przedmiotów zmienia miejsca. Cykl zewnętrzny będzie działać do momentu sortowania tablicy. W ten sposób cykl zewnętrzny steruje liczbą reakcji cyklu wewnętrznego, gdy z następnym fragmentem nie będzie permutacji nad elementami tablicy, tablica zostanie uznana za posortowany. Aby dobrze zrozumieć algorytm, posortuj metodę bąbelkową, na przykład, z 7 numerów (patrz tabela 1).
array źródła: 3 3 7 1 2 5 0
| Numer iteracji | Elementy tablicy | Przestawiony | ||||||
|---|---|---|---|---|---|---|---|---|
| wymieniać się szyk | 3 | 3 | 7 | 1 | 2 | 5 | 0 | |
| 0 | 3 | 3 | fałszywe | |||||
| 1 | 3 | 7 | fałszywe | |||||
| 2 | 1 | 7 | 7\u003e 1, prawda | |||||
| 3 | 2 | 7 | 7\u003e 2, prawdziwe | |||||
| 4 | 5 | 7 | 7\u003e 5, prawda | |||||
| 5 | 0 | 7 | 7\u003e 0, prawda | |||||
| tech. szyk | 3 | 3 | 1 | 2 | 5 | 0 | 7 | |
| 0 | 3 | 3 | fałszywe | |||||
| 1 | 1 | 3 | 3\u003e 1, prawda | |||||
| 2 | 2 | 3 | 3\u003e 2, prawda | |||||
| 3 | 0 | 3 | 3\u003e 0, prawda | |||||
| 4 | 3 | 5 | fałszywe | |||||
| 5 | 5 | 7 | fałszywe | |||||
| tech. szyk | 3 | 1 | 2 | 0 | 3 | 5 | 7 | |
| 0 | 1 | 3 | 3\u003e 1, prawda | |||||
| 1 | 2 | 3 | 3\u003e 2, prawda | |||||
| 2 | 0 | 3 | 3\u003e 0, prawda | |||||
| 3 | 3 | 3 | fałszywe | |||||
| 4 | 3 | 5 | fałszywe | |||||
| 5 | 5 | 7 | fałszywe | |||||
| tech. szyk | 1 | 2 | 0 | 3 | 3 | 5 | 7 | |
| 1 | 2 | fałszywe | ||||||
| 0 | 2 | 2\u003e 0, prawdziwe | ||||||
| 2 | 3 | fałszywe | ||||||
| 3 | 3 | fałszywe | ||||||
| 3 | 5 | fałszywe | ||||||
| 5 | 7 | fałszywe | ||||||
| tech. szyk | 1 | 0 | 2 | 3 | 3 | 5 | 7 | |
| 0 | 1 | 1\u003e 0, prawdziwe | ||||||
| 1 | 2 | fałszywe | ||||||
| 2 | 3 | fałszywe | ||||||
| 3 | 3 | fałszywe | ||||||
| 3 | 5 | fałszywe | ||||||
| 5 | 7 | fałszywe | ||||||
| end Array. | 0 | 1 | 2 | 3 | 3 | 5 | 7 | |
| Koniec sortowania | ||||||||
Aby posortować tablicę pięciu wprowadzeń cyklu wewnętrznego, dla. Bieganie, na cykl wywołał 6 razy, ponieważ elementy w tablicy 7, a następnie iTeretacje (powtórzenia) z cyklu dla cyklu powinny być mniejsze. Każda iteracja porównuje dwa sąsiednie elementy tablicy. Jeśli obecny element tablicy jest więcej niż następny, a następnie zmień je w miejscach. Tak więc, aż do sortowania tablicy zostanie uruchomiony cykl wewnętrzny, a operacja porównania zostanie wykonana. Należy pamiętać, że dla każdego pełnego wykonania a co najmniej jeden element tablicy znajduje swoje miejsce. W najgorszym przypadku zajmie N-2 uruchomienie cyklu wewnętrznego, gdzie n jest liczbą elementów tablicy. Sugeruje to, że sortowanie bąbelkowe jest niezwykle skuteczne dla dużych tablic.
Rozwijamy program, w którym najpierw musisz wprowadzić rozmiar jednowymiarowej tablicy, po czym tablica jest wypełniona liczbami losowymi i jest sortowana przez metodę bąbelkową.
// bup_sort.cpp: Określa punkt wejściowy dla aplikacji konsoli. #Include "stdafx.h" #include
Wynik programu jest pokazany na rysunku 1.
