Metóda bubliny C sériový výstup. Triedenie bublín a všetky-všetko-všetko. Vylepšený triediaci algoritmus v Pascal

Umiestňujeme pole zhora nadol, z nulového prvku do poslednej.

Myšlienka metódy: Krok triedenia spočíva v priechode zo zdola nahor poľa. Na ceste existujú dvojice susedných prvkov. Ak sú prvky niektorých párov v nesprávnom poradí, potom ich zmenia na miestach.

Po nulovom priechode po poli "TOP" sa ukáže, že je najviac "ľahký" prvok - odtiaľto analógie s bublinou. Nasledujúca pasáž sa vykonáva na druhý prvok zhora, takže druhý najväčší prvok stúpa do správnej polohy ...

Priechody pre celú klesajúcu spodnú časť poľa, kým v ňom zostáva len jeden prvok. Na tomto triedení končí, pretože sekvencia je usporiadaná vzostupne.

Šablóny. VLASTNOSTI BUBTBY (T A, DLHÁ, ŽIVOTNÁ Veľkosť) (Long I, J, T X; pre (I \u003d 0; I< size; i++) { // I - číslo pasu pre (j \u003d veľkosť-1; j\u003e i; j-) ( // vnútorný cyklus priechodu ak (A\u003e A [j]) (X \u003d A; A \u003d A [J]; A [J] \u003d X;)))

Priemerný počet porovnaní a výmeny majú kvadratické poradie rastu: theta (N2), odtiaľ môžete dospieť k záveru, že bublinový algoritmus je veľmi pomalý a je neúčinný.
Avšak, má obrovské plus: je jednoduchý a môže byť akýmkoľvek spôsobom zlepšiť. Čo teraz pôjdeme.

Po prvé, zvážte situáciu, keď sa nestane žiadna výmena na žiadnom z prevodov. Čo to znamená?

To znamená, že všetky páry sú umiestnené v správnom poradí, takže pole je už zoradené. A pokračovať v procese nedáva zmysel (najmä ak je pole zoradené od samého začiatku!).

Prvé zlepšenie algoritmu je teda zapamätať, či bola na tejto pasáži vykonaná akákoľvek výmena. Ak nie, algoritmus dokončí prácu.

Proces zlepšenia možno pokračovať, ak si spomeniete nielen na skutočnosť výmeny, ale aj index poslednej výmeny K. V skutočnosti: všetky páry balíka prvkov s indexmi, menšie k, sú už umiestnené v požadovanom poradí. Ďalšie pasáže môžu byť dokončené na indexu k namiesto presunu na hornú hranicu verziu, ktorú som nainštaloval vopred.

Kvalitatívne, ďalšie zlepšenie algoritmu je možné získať z nasledujúceho pozorovania. Hoci svetelná bublina z dna sa vstane v jednom priechode, ťažké bubliny sa znížia pri minimálnej rýchlosti: jeden krok pre iteráciu. Takže pole 2 3 4 5 6 1 bude zoradené v 1 prechode a triedenie sekvencie 6 1 2 3 4 5 bude vyžadovať 5 prechádza.

Aby ste sa vyhli podobnému efektu, môžete zmeniť smer nasledujúceho z iných prechodov. Výsledný algoritmus sa niekedy nazýva " shaker-triedenie".

Šablóny. VOID SHAKERSORTH (T A, DLHÁ, KTORÁ SAŤ) (Dlhý J, K \u003d veľkosť-1; dlhé lb \u003d 1, UB \u003d veľkosť-1; // hranice neuskutovanej časti poľa T x; robiť ( // prejsť späť hore Pre (J \u003d UB; J\u003e 0, J-) (AK (A\u003e A [J]) (X \u003d A; A \u003d A [J] A [J] \u003d X; K \u003d J;) LB \u003d K + 1; // prejsť zhora nadol pre (j \u003d 1; j<=ub; j++) { if (a > a [j]) (X \u003d A; A \u003d A [j] a [j] \u003d X; K \u003d J;)) UB \u003d K-1; ) Kým (lb< ub); }

Ako opísané zmeny ovplyvnili účinnosť metódy? Priemerný počet porovnaní, hoci sa znížil, ale zostáva o (N 2), zatiaľ čo počet výmen sa vôbec nezmenil. Priemer (je to najhoršie) počet operácií zostáva kvadratický.

Ďalšia pamäť sa samozrejme nevyžaduje. Správanie sa zlepšenej (ale nie počiatočnej) metódy je dosť prirodzené, takmer triedené pole bude zoradené oveľa rýchlejšie. Zoradiť podľa bubliny je stabilný, ale triedenie shakru stráca túto kvalitu.

V praxi, metóda bubliny, dokonca aj s vylepšeniami, prác, bohužiaľ, príliš pomalé. A preto - takmer sa neuplatňuje.

Metóda bubliny

Triedenie jednoduché výmeny , zoradiť podľa bubliny (Eng. triedenie bubliny.) - Jednoduchý triediaci algoritmus. Rozumieť a implementovať tento algoritmus - najjednoduchšie, ale je to účinné len pre malé polia. Zložitosť algoritmu: o ( n.²).

Algoritmus sa považuje za vzdelávací a prakticky sa nevzťahuje mimo vzdelávacej literatúry, namiesto toho v praxi sa uplatňujú vklady.

Algoritmus

Triedenie podľa bublínového zoznamu náhodných čísel.

Algoritmus sa skladá z opakujúcich sa uličiek na usporiadaní poľa. Pre každý priechod sú prvky konzistentne porovnávané v pároch a ak je objednávka nesprávna, je splnená výmena prvkov. Pojem poľa sa opakujú, kým sa ďalšia pasáž ukáže, že výmeny už nie sú potrebné, čo znamená - pole je zoradené. S priechodom algoritmu, prvok, ktorý nie je na svojom mieste, "objaví" do požadovanej polohy ako bubliny vo vode, teda názov algoritmu.

Niekedy na každom kroku je pole viditeľné od začiatku, potom od konca. Toto sa nazýva Shaker Triedenie.

Príklady implementácie

Python

Def Swap (ARR, I, J): ARR [I], ARR [J] \u003d ARR [J], ARR [I] DEF BUBBLE_SORT (ARR): I \u003d LEN (ARR), zatiaľ čo i\u003e 1: pre J v Xrange (I - 1): Ak ar [j]\u003e Arr [J + 1]: Swap (ARR, J, J + 1) I - \u003d 1

Vba.

Sub Triediť (Mus () tak dlho) Dim n tak dlho, ja tak dlho, TMP tak dlho i \u003d 1 robiť, zatiaľ čo (i< UBound (Mus) ) If Mus(i) > Mus (i + 1) Potom TMP \u003d Mus (I) Mus (I) \u003d Mus (I + 1) Mus (I + 1) \u003d TMP IF I\u003e 1 Potom I \u003d I - 1 INÉ I \u003d I + 1 END Inak i \u003d i + 1 koniec, ak končí slučka

Vylepšený triediaci algoritmus v Pascal

P: \u003d true; (Existuje permutácia) K: \u003d 1; (Zobrazenie čísla) Kým P Začiatok P: \u003d FALSE; Pre I: \u003d 1 až N - K Urobte, ak X [i]\u003e X [i + 1] potom začnite: \u003d X [I]; X [I]: \u003d X [i + 1]; X [i + 1]: \u003d A; P: \u003d true; Koniec; K: \u003d K + 1; Koniec;

Php.

$ Veľkosť \u003d počet ($ ARR) -1; Pre ($ i \u003d $ veľkosť; $ i\u003e \u003d 0; $ i -) (pre ($ j \u003d 0; $ j<=($i -1 ) ; $j ++) if ($arr [ $j ] >$ ARR [$ J +1]) ($ K \u003d $ ARR [$ J]; $ ARR [$ J] \u003d $ Arr [$ J +1]; $ ARR [$ J +1] \u003d $ K;)

Nielenže sa nepovažuje za najrýchlejšiu metódu, okrem toho zavrie zoznam najpomalších spôsobov, ako si objednať. Má však svoje výhody. Takže, triedenie podľa metódy bubliny - najviac, neexistuje logické a prirodzené riešenie problému, ak je potrebné umiestniť prvky v určitom poradí. Bežná osoba manuálne, napríklad, bude využívať ich - len na intuícii.

Odkiaľ pochádza taký neobvyklý názov?

Názov spôsobu bol vynájdený použitím analógie s vzduchovými bublinami vo vode. Toto je metafora. Rovnako ako malé vzduchové bubliny vzostup - koniec koncov, ich hustota je väčšia ako akákoľvek kvapalina (v tomto prípade - voda) a každý prvok poľa, tým menej oceňuje, tým viac sa postupne robí jeho spôsobmi na začiatok počet čísel.

Popis algoritmu

Zoradiť podľa bubliny sa vykonáva nasledovne:

prvá pasáž: Prvky radu čísel sa užívajú dva a tiež porovnávané páry. Ak je v niektorých dvoch prvkoch, prvá hodnota je vyššia ako druhá, program vytvára ich zdieľanie poľa;
v dôsledku toho pole spadá do konca. Zatiaľ čo všetky ostatné prvky zostávajú, pretože boli v chaotickom poradí a vyžadujú viac triedenia;
preto je druhý priechod potrebný: je vyrobený analogicky s predchádzajúcim (už opísaným) a má niekoľko porovnaní - mínus jeden;
Číslo pasáže tri porovnania na jednotku menej ako druhú a dvakrát ako prvý. Atď;
zhrníme, že každá pasáž má (celkové hodnoty v poli, konkrétne číslo) mínus (číslo pasáže) porovnaní.

Stručne povedané, algoritmus budúceho programu môže byť napísaný takto:

kONTROLAČNOSTI ČÍSLA JE KONTROLAČNOSTI, KTORÝMI ZNÍŽIŤ DVAHO NÁKLADY, DRUHOSŤ DRUHOSTIUJÚCEJ
nesprávne umiestnené vo vzťahu k sebe navzájom sa zmení na miestach programu poľa.

Pseudokóda na základe opísaného algoritmu

Najjednoduchšia implementácia sa vykonáva takto:

Postup SORTIRIROVKA_PUZIRKOM;

Spustiť

cyklus j. z nachalnii_index predtým kONECHII_INDEX;

cyklus i. z nachalnii_index predtým konechii_index-1.;

ak massiv [I]\u003e Masiv

(zmeniť hodnoty na miestach);

koniec

Samozrejme, tu jednoduchosť zhoršuje situáciu: tým jednoduchší algoritmus, najmä v ňom všetky chyby sa prejavujú. Náklady na dobu je príliš veľký aj pre malé pole (existuje otázka relativity: Pre priemerný čas sa môže zdať malý, ale v programátorom programátora, každý druhý alebo dokonca milisekunda na účte).

Trvalo to lepšie. Napríklad, s prihliadnutím na výmenu hodnôt v poli podľa miest:

Postup SORTIRIROVKA_PUZIRKOM;

Spustiť

shorTirovka. \u003d pravda;

cyklus shorTirovka. \u003d pravda;

shorTirovka. \u003d false;

cyklus i. z nachalnii_index predtým konechii_index-1.;

ak massiv [I]\u003e Masiv (Prvý prvok je väčší ako druhý), potom:

(Zmena prvkov na miestach);

shorTirovka. \u003d pravda; (Označujú, že výmena bola vyrobená).

Koniec.

Nevýhody metódy

Hlavný mínus je trvanie procesu. Koľko času sa vykonáva bublina?

Realizácia sa vypočíta zo štvorca počtu čísel v poli - konečný výsledok je proporcionálny.

V prípade najhoršej verzie bude pole prejsť toľkokrát, koľkokrát je v IT prvkoch mínus jedna hodnota. Je to preto, že je v konečnom dôsledku len jeden prvok, ktorý nemá čo porovnávať, a posledná pasáž masívu sa stáva k ničomu.

Okrem toho, spôsob triedenia jednoduchými výmenami, ako je tiež volal, len pre malé polia. Veľké objemy údajov s ním nebude spracované: Výsledkom bude buď chyby alebo zlyhanie programu.

Dôstojnosť

Zoradiť podľa bubliny je veľmi jednoduché na pochopenie. V programoch učebných programov technických univerzít, pri štúdiu radu prvkov poľa, trvá prvé. Metóda sa ľahko implementuje ako v jazyku. programovanie Delphi. (D (DELPHI) a C / C ++ (SI PLUS PLUS), neuveriteľne jednoduchý algoritmus pre umiestnenie hodnôt v správnom poradí a na triedenie bublinou sú ideálne pre začiatočníkov.

Vzhľadom na nedostatky sa algoritmus neuplatňuje v mimoškolských účely.

Princíp triedenia v porovnania

Počiatočný pohľad na pole 8 22 4 74 44 37 1 7

Krok 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Krok 2. 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Krok 3. 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Krok 4. 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Krok 5. 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Krok 6. 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Krok 7. 1 4 7 8 22 37 44 74

Triedenie podľa bubliny v Pascal

Príklad:

cONST KOL_MAS \u003d 10;

vaR Massiv: Array of Integer;

a, B, K: Integer;

writeln ("vstup", Kol_mas, "Prvky poľa");

pre A: \u003d 1 až KOL_MAS Radlnn (Masiv [A]);

pre A: \u003d 1 až KOL_MAS-1

pre b: \u003d A + 1 na KOL_MAS

ak Massiv [A]\u003e Massiv [B] potom začnite

k: \u003d Massiv [A]; Massiv [A]: \u003d Masiv [B]; Massiv [B]: \u003d K;

koniec;

writeln ("po triedení");

pre A: \u003d 1 až KOL_MAS WINTELN (Masiv [A]);

Triedenie podľa bubliny v jazyku s (SI)

#Include.

int hlavné (int argc, char * argv)

INT MASSIV \u003d (36, 697, 73, 82, 68, 12, 183, 88), I, FF;

pre (;) (

ff \u003d 0;

pre (I \u003d 7; I\u003e 0; I -) (

Ak (masiv [i]< massiv) {

Swap (masiv [i], masiv);

Ak (ff \u003d\u003d 0) prestávka;

getch (); // oneskorenie obrazovky

Tagy: Zoradiť podľa Bubble Si, Si triedenie bublínZoradiť podľa bubline dvojrozmerné pole

Zoradiť podľa bubliny

A akt algoritmu je veľmi jednoduchý. Prejdeme do radu čísel a skontrolujeme objednávku (ďalšie číslo by malo byť viac a rovné predchádzajúcemu), akonáhle narazili na porušenie objednávky, okamžite vymieňame prvky na miestach, dostaneme na koniec Array a potom začiatok najprv.

Zoradiť pole (1, 5, 2, 7, 6, 3)
Ideme na masív, skontrolujeme prvé číslo a po druhé, idú vo vzostupnom poradí. Ďalej je tu porušenie objednávky, zmeníme tieto prvky
1, 2, 5, 7, 6, 3
Pokračujeme v prechádzajúcom poľa, 7 viac ako 5, ale 6 menej, takže vymeníme z miest
1, 2, 5, 6, 7, 3
3 porušuje objednávku, zmeny miest od 7
1, 2, 5, 6, 3, 7
Vrátime sa na začiatok poľa a urobíme to isté

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Hovorí sa, že je to podobné "plávajúce" viac "pľúc" prvkov, ako je bubliny, čo je dôvod, prečo algoritmus a prijal taký názov. VLASTNOSTI BUBTBY (INT * A, SIZNUTIE SIZE_T) (SIBLE_T I, J, INT TMP; PRE (I \u003d 1; I< size; i++) { for (j = 1; j < size; j++) { if (a[j] > a) (TMP \u003d A [j] a [j] \u003d A; A \u003d TMP;))

Tento algoritmus bude vždy robiť (n-1) 2 kroky, bez ohľadu na vstupné údaje. Aj keď je pole triedené, bude ešte prejsť (n-1) 2-krát. Okrem toho sa opäť skontrolujú už triedené údaje.

Nech je potrebné triediť pole 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

Potom, čo sa zmenilo na miestach prvku a a nie je potrebné prejsť túto časť poľa. Berieme ho do úvahy a údajného algoritmu

VLASTNOSTI BUBTBYLOPORT2 (INT * A, SIZNUTIE SIZNUTIE) (SIBLY_T I, J; Int TMP; pre (I \u003d 1; I< size; i++) { for (j = i; j > 0; j--) (ak (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Ďalšia implementácia

VLASTNOSTI BUBLIBYORT2B (INT * A, SIZNUTIE SIBLY_T) (SIBLY_T I, J; Int TMP; pre (I \u003d 1; I< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

V tomto prípade bude polovičné menej krokov, ale stále problém triedenia už zoradeného poľa zostáva: musíte urobiť tak, že triedené pole sa raz zobrazia. Ak to chcete urobiť, zadajte variabilný flag: Bude vynechaný (flag \u003d 0), ak je pole zoradené. Akonáhle ideme na porušenie objednávky, príznak bude zdvihnutý (vlajka \u003d 1) a začneme triediť pole ako obvykle.

VLASTNOSTI BLÓNU BLÁDKA (INT * A, SIZNUTIE SIZE_TU) (SIBLY_T I; INT TMP; KABLE VLASTNOSTI; DO (FLAG \u003d 0; pre (I \u003d 1; I< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

V tomto prípade je komplexnosť tiež asi N2, ale v prípade zoradeného poľa bude len jedna pasáž.

Teraz zlepšiť algoritmus. Budeme píšeme funkciu všeobecného formulára tak, že triedila pole typu neplatné. Pretože typ premennej nie je známy, bude potrebné ďalej prenášať veľkosť jedného prvku poľa a porovnávacie funkciu.

Int Intsort (Const Vid * A, Const Vid * B) (Return * ((((Int *) A)\u003e * ((Int *) b);) Vlastne BListové bublinkORT3G (Void * A, SIZNIKA_T položka, veľkosť veľkosti_t, int (* CMP) (CONST VOID *, CONST VOID *)) (SIBLE_T_T I; VOID * TMP \u003d NULL; KRÁTNÝ VLASTNOSTI; TMP \u003d MALLOC (položka); DO (FLAG \u003d 0; pre (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); }

Funkcia vyzerá škaredá - často sa vypočíta adresa aktuálneho a predchádzajúceho prvku. Zdôrazňujeme pre toto oddelené premenné.

Vlasti Bith BubblesPort3gi (Void * A, Size_t položka, Size_t Size, Int (* CMP) (CONST VOID *, CONST VOID *))) (SIZNUTIA_T I; VOID * TMP \u003d NULL; VOID * PRÍPRAVA, * TMP; MALLOC (položka); DO (FLAG \u003d 0; I \u003d 1; PREV \u003d (Char *) A; cuto \u003d (char *) predchádza + položka; zatiaľ čo (i< 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 s týmito funkciami môžete triediť polia ľubovoľného typu, napríklad

Void Main () (INT A \u003d (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); INT I; BLOIDOVANIEHODNOTLIČNÍTKY, 10, INTSORT); pre (I \u003d 0; ja< 10; i++) { printf("%d ", a[i]); } _getch(); }

Triedenie multidimenzionálneho poľa

Statické multidimenzionálne pole sa v podstate nelíši od triedenia jednorozmerného. Môžete použiť vlastnosť, že statické jednorozmerné a multidimenzionálne polia majú rovnaký pohľad v pamäti.

Void Main () (INT A \u003d (1, 9, 2, 8, 3, 7, 4, 6, 5); INT I, J; BLOIDOVÉHODNOSTI, 9, ITTSORT); pre (I \u003d 0; ja< 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #Include. #Include. #Include. Vlasti BitbelDr2D (INT ** A, SIBLY_T M, SIZNÍCKA /T N) (INT TMP; SIMBER_T I, J, K, JP. K.< size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] > a) (TMP \u003d A [I] [J]; A [I] [j] \u003d A; A \u003d TMP; flag \u003d 1;))), zatiaľ čo (vlajka); ) #Define Size_x 3 #Define Size_y 4 Void Main () (INT ** A \u003d NULL, INT I, J; A \u003d (INT **) MALLOC (SITEOF (INT *) * SIBLOP_X); pre (I \u003d 0; I.< SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

Po druhé, môžete najprv presunúť pole na jeden dimenzionálny, triediť jednorozmerné pole, potom ho presunúť späť do dvojrozmerného.

Vlasti BubblesPort3gi2D (VOID ** A, SIZNÍCTVO SIVER_T_T, SIZNUTIA_T M, SIZNUTIE_T N, Int (* CMP) (Const Void *, Const Void *)) (SIZNÁA_TABY SIZNUTIE \u003d M * N, SUB_SIZE \u003d N * položka; SIBLY_T I, J , K; VOID * ARR \u003d MALLOC (veľkosť * položka); char * p1d \u003d (char *) arr; char * p2d \u003d (char *) a; // kopírovať dvojrozmerný typ prázdnotu do jednorozmerného pre (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); } }

Ak vám táto funkcia zamieňa, potom použite napísané. Zavolajte z predchádzajúceho príkladu

Odhaduje sa, že do štvrtého času centralizované počítače Zaplatí sa triedeniu údajov. Je to preto, že je oveľa jednoduchšie nájsť hodnotu v poli, ktoré bolo vopred triedené. V opačnom prípade je vyhľadávanie trochu ako vyhľadávanie ihly v sena.

Existujú programátori, ktorí vykonávajú všetky pracovné hodiny v štúdii a implementácii triediacich algoritmov. Je to preto, že prevažná väčšina podnikateľských programov zahŕňa správu databáz. Ľudia stále hľadajú informácie v databázach po celú dobu. To znamená, že vyhľadávacie algoritmy sú veľmi v dopyte.

Ale je tu jeden "ale". Hľadať algoritmy fungujú oveľa rýchlejšie s databázami, ktoré sú už zoradené. V tomto prípade sa vyžaduje len lineárne vyhľadávanie.

Zatiaľ čo počítače sú bez užívateľov v niektorých časových bodoch, triediace algoritmy pokračujú v práci s databázami. Opäť, vyhľadávajú používatelia a databáza je už zoradená, na základe konkrétneho gólu vyhľadávania.

Tento článok obsahuje príklady implementácie štandardných triediacich algoritmov.

Zoradenie výberu (Zoradiť podľa výberu)

Ak chcete triediť pole vo vzostupnom poradí, sledujete každú iteráciu, aby ste našli položku s najvyššou hodnotou. S ním musíte vymeniť posledný prvok. Ďalší prvok s najväčšou hodnotou sa stáva predposledným miestom. To by sa malo stať, kým prvky, ktoré sú na prvom mieste v poliach nebudú správne.

C ++ kód

void SortalOgo :: Selektionsort (Int dáta, Int požičiavanie) (INT J \u003d 0; Int TMP \u003d 0; pre (int i \u003d 0; ja Údaje [K]) (J \u003d K;)) TMP \u003d dáta [I]; Údaje [i] \u003d údaje [j]; Údaje [j] \u003d TMP; ))

Druhu bubliny

S triedením bublín sú priľahlé prvky porovnávajú a menia na miestach, ak je ďalší prvok menší ako predchádzajúci. Vyžaduje sa niekoľko priechodov. Počas prvého priechodu prvé dva prvky v oblasti bojujú. Ak nie sú v poriadku, menia miesta a potom porovnávajú prvky v nasledujúcom páre. S rovnakým podmienkou, tiež menia miesta. Triedenie sa teda vyskytuje v každom cykle, kým sa dosiahne koniec poľa.

C ++ kód

void SortalOgo :: BUBTBYLTER (Int dáta, Int požičiavanie) (Int TMP \u003d 0; pre (int i \u003d 0; ja \u003d (i + 1); j -) (ak (údaje [j]

Zoradiť Zoradiť (Zoradiť podľa vkladania)

Pri triedení vložiek je pole rozdelené do dvoch oblastí: objednané a neusporiadané. Spočiatku je celá pole neusporiadaná oblasť. Pri prvom priechode je prvý prvok z neusporiadanej oblasti zakrytý a umiestnený v správnej polohe v usporiadanej oblasti.

Na každej pasáži sa veľkosť objednanej oblasti zvýši o 1 a veľkosť neusporiadanej oblasti sa zníži o 1.

Hlavný cyklus pracuje v rozsahu od 1 do n-1. Na i-thi je prvok [I] vložený do správnej polohy v usporiadanej oblasti. To sa vykonáva presunutím všetkých prvkov objednanej oblasti, ktoré sú väčšie ako [i], jedna poloha vpravo. [I] sa vkladá do intervalu medzi týmito prvkami, ktoré sú menšie ako [I], a tie, ktoré sú vyššie [I].

C ++ kód

vOID SORREALGO :: INSERTIONSORT (INT DATA, INT LEND) (Int Key \u003d 0; Int I \u003d 0; pre (INT J \u003d 1; J \u003d 0 && Data [i]\u003e kľúč) (dáta \u003d dáta [i]; i \u003d i-1; dáta \u003d kľúč;)))

Zlúčenie (Zlúčenie Zlúčenie)

C ++ kód

void SortalOGO :: Mergesort (Int dáta, Int požičiavanie) (ak (LEND\u003e 1) (Int Middle \u003d LEND / 2; Int REM \u003d LEND-Stred; Int * l \u003d nový int; pre ( int i \u003d 0; ja

Rýchly druh

Rýchle triedenie používa algoritmus "Rozdeliť a dobyť". Začína rozdelením pôvodného poľa do dvoch oblastí. Tieto časti sú umiestnené vľavo a vpravo od označeného prvku nazývaného referencie. Na konci procesu bude jedna časť obsahovať prvky menšie ako podpora a druhá časť bude obsahovať prvky viac odkazov.

C ++ kód

vOID SORREALGO :: QUICKSORT (INT * DATA, INT CONST LEN) (INT CONST LEND \u003d LEN; Int PIVOT \u003d 0; Int Ind \u003d LEND / 2; Int I, J \u003d 0, K \u003d 0; IF (LEND\u003e 1) (int * l \u003d nový int; int * r \u003d nový int; pivovanie \u003d dáta; pre (i \u003d 0; ja