Bublinové třídění si. Metody řazení v programování: bublinové třídění. Kde se vzal tak neobvyklý název?
Odhaduje se, že až čtvrtinu času centralizovaných počítačů stráví třídění dat. Je to proto, že je mnohem snazší najít hodnotu v poli, které bylo předem seřazeno. Jinak to hledání trochu připomíná hledání jehly v kupce sena.
Existují programátoři, kteří tráví veškerý svůj pracovní čas studiem a implementací třídicích algoritmů. Je to proto, že naprostá většina podnikového softwaru zahrnuje správu databází. Lidé neustále hledají informace v databázích. To znamená, že vyhledávací algoritmy jsou velmi žádané.
Ale je tu jedno "ale". Vyhledávací algoritmy pracují mnohem rychleji s databázemi, které jsou již seřazeny. V tomto případě je vyžadováno pouze lineární vyhledávání.
Zatímco počítače jsou v určitých okamžicích bez uživatelů, třídicí algoritmy nadále fungují v databázích. Hledači přicházejí znovu a databáze je již setříděna podle toho či onoho účelu vyhledávání.
Tento článek poskytuje příklady implementací standardních třídicích algoritmů.
Výběr řazení
Chcete-li seřadit pole ve vzestupném pořadí, musíte v každé iteraci najít prvek s největší hodnotou. S ním musíte vyměnit poslední prvek. Další prvek s nejvyšší hodnotou se umístí na předposlední místo. K tomu by mělo dojít, dokud nebudou prvky na prvních místech v poli ve správném pořadí.
C++ kód
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
Bublinové řazení
Bublinové řazení porovnává sousední prvky a vyměňuje místa, pokud je další prvek menší než předchozí. Je vyžadováno více průchodů daty. Během prvního průchodu se porovnávají první dva prvky v poli. Pokud nejsou v pořádku, prohodí se a poté se porovnají prvky v dalším páru. Za stejných podmínek také mění místa. K řazení tedy dochází v každém cyklu, dokud není dosaženo konce pole.
C++ kód
void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i Vložení řazení rozdělí pole na dvě oblasti: uspořádané a neuspořádané. Zpočátku je celé pole neuspořádanou oblastí. Při prvním průchodu je první prvek z neuspořádané oblasti odstraněn a umístěn do správné polohy v uspořádané oblasti. Při každém průchodu se velikost uspořádané oblasti zvětší o 1 a velikost neuspořádané oblasti se sníží o 1. Hlavní smyčka probíhá od 1 do N-1. Při j-té iteraci je prvek [i] vložen do správné pozice v uspořádané oblasti. To se provádí posunutím všech prvků uspořádané oblasti, které jsou větší než [i] o jednu pozici doprava. [i] se vloží do prostoru mezi prvky, které jsou menší než [i] a ty, které jsou větší než [i]. C++ kód
void SortAlgo::insertionSort(int data, int lenD) ( int klíč = 0; int i = 0; for (int j = 1; j C++ kód
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i Rychlé řazení používá algoritmus rozděl a panuj. Začíná rozdělením původního pole na dvě oblasti. Tyto části jsou vlevo a vpravo od označeného prvku, nazývaného podpora. Na konci procesu bude jedna část obsahovat prvky menší než reference a druhá část bude obsahovat prvky větší než reference. C++ kód
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = délka; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = new int ; int * R = new int ; pivot = data; for (i=0;i Praktický přínos těchto metod není tak velký a mnoho uživatelů habra si tím vším prošlo v první třídě. Proto je článek určen těm, kteří se právě začali zajímat o teorii algoritmů a podnikají první kroky tímto směrem. obrázek: bubliny Dnes si povíme o tom nejjednodušším výměnné třídění. Pokud by měl někdo zájem, řeknu, že existují další třídy - výběr řazení, řazení vložení, Sloučit třídění, třídění distribuce, hybridní druhy A paralelní druhy. Mimochodem, existuje také esoterické třídění. Jsou to různé falešné, zásadně nerealizovatelné, komické a jiné pseudoalgoritmy, o kterých napíšu pár článků v hubu „IT Humor“. Ale to nemá nic společného s dnešní přednáškou, nás teď zajímají jen jednoduché burzovní třídění. Existuje také spousta samotných burzovních řazení (znám více než desítku), takže se podíváme na tzv. bublinový druh a některé další s ním úzce související. Předem upozorňuji, že téměř všechny výše uvedené metody jsou velmi pomalé a nebude docházet k žádnému hloubkovému rozboru jejich časové náročnosti. Někdo je rychlejší, někdo pomalejší, ale zhruba řečeno lze říci, že průměrně Ó(n 2). Také nevidím důvod zahlcovat článek implementacemi v jakýchkoli programovacích jazycích. Zájemci mohou snadno najít příklady kódu na Rosettě, Wikipedii nebo jinde. Ale vraťme se k řazení burz. Řazení nastává jako výsledek opakované sekvenční iterace pole a porovnávání dvojic prvků mezi sebou. Pokud porovnávané prvky nejsou vůči sobě seřazeny, pak je prohodíme. Jedinou otázkou je, jak přesně pole obejít a na jakém základě vybrat páry pro porovnání. Začněme ne standardním řazením bublin, ale algoritmem zvaným... "Takhle umí třídit každý blázen," řeknete a budete mít naprostou pravdu. Proto se třídění říká „hloupost“. V této přednášce budeme tuto metodu důsledně vylepšovat a upravovat. Nyní má dočasné potíže Ó(n 3), po provedení jedné opravy ji již provedeme Ó(n 2), pak to ještě trochu zrychlíme, pak ještě trochu víc a nakonec to dostaneme Ó(n log n) – a vůbec to nebude „Quick Sort“! Udělejme jedno jediné vylepšení hloupého třídění. Poté, co jsme během průchodu objevili dva sousedící neseřazené prvky a prohodili je, nevrátíme se zpět na začátek pole, ale budeme ho klidně dál procházet až do úplného konce. V tomto případě před sebou nemáme nic jiného než známé... Pokud budeme makat nejen maxima na konec, ale i minima na začátek, pak se nám to daří... Třídění na třepačce funguje o něco rychleji než třídění podle bublin, protože jak maxima, tak minima střídavě migrují skrz pole v požadovaných směrech. Zlepšení, jak se říká, je zřejmé. Jak vidíte, pokud k procesu výčtu přistoupíte kreativně, pak vytlačení těžkých (lehkých) prvků na konce pole proběhne rychleji. Řemeslníci proto navrhli další nestandardní „cestovní mapu“, jak seznam obejít. V pravidelné „bublině“ během každého průchodu systematicky mačkáme aktuální maximum na konec pole. Pokud skočíte podél sudých a lichých indexů, pak jsou všechny více či méně velké prvky pole současně posunuty o jednu správnou pozici v jednom běhu. Takto to funguje rychleji. Podívejme se na poslední přezdobený* Pro Sortuvannya bulbashka** - Třídění podle hřebenu***. Tato metoda se velmi rychle organizuje, Ó(n 2) je jeho nejhorší obtížnost. V průměru v průběhu času máme Ó(n log n), a to nejlepší, ani tomu nebudete věřit, Ó(n). To znamená, že je to velmi důstojný konkurent všech druhů „rychlých druhů“ a to, pozor, bez použití rekurze. Slíbil jsem však, že se dnes nebudeme ponořit do cestovní rychlosti, takže přestanu mluvit a přejdu přímo k algoritmu. obrázek: vinná želva Je lepší brát počáteční mezeru mezi porovnávanými prvky ne ledajakou, ale s přihlédnutím ke speciální hodnotě tzv redukčním faktorem, jehož optimální hodnota je přibližně 1,247. Za prvé, vzdálenost mezi prvky se rovná velikosti pole dělené redukční faktor(výsledek je samozřejmě zaokrouhlen na nejbližší celé číslo). Poté, po procházení pole tímto krokem, opět krok vydělíme redukční faktor a znovu projděte seznam. Toto pokračuje, dokud rozdíl indexu nedosáhne jedné. V tomto případě je pole seřazeno s pravidelnou bublinou. Optimální hodnota byla stanovena experimentálně a teoreticky redukční faktor: Když byla tato metoda vynalezena, málokdo jí na přelomu 70. a 80. let věnoval pozornost. O deset let později, kdy programování již nebylo oblastí vědců a inženýrů IBM, ale rychle si získávalo masovou popularitu, byla metoda znovu objevena, prozkoumána a popularizována v roce 1991 Stephenem Lacym a Richardem Boxem. To je vlastně vše, co jsem vám chtěl říct o třídění bublin a dalších podobných. - Poznámky * zkráceno ( ukrajinština) - zlepšení Ahoj všichni! Dnes se podíváme na bublinkové třídění. Tento algoritmus se často vyučuje na školách a univerzitách, proto budeme používat Pascal. Takže, co je třídění? Řazení je řazení prvků od nejmenšího po největší (vzestupné řazení) nebo od největšího prvku po nejmenší (sestupné řazení). Pole jsou obvykle tříděna. Existují různé třídicí algoritmy. Některé jsou dobré v řazení velkého počtu prvků, jiné jsou efektivnější s velmi malým počtem prvků. Charakteristická je naše bublinková metoda: Algoritmus:
Vezmeme prvek pole, porovnáme ho s dalším, pokud je náš prvek větší než další prvek, pak je prohodíme. Po projití celého pole si můžeme být jisti, že maximální prvek bude „vytlačen“ – a bude úplně poslední. Jeden prvek je tedy již přesně na svém místě. Protože musíme je všechny umístit na svá místa, proto musíme tuto operaci opakovat tolikrát, kolikrát máme prvků pole mínus 1. Poslední prvek zůstane automaticky stát, pokud jsou ostatní na svých místech.
Vraťme se k našemu poli: 3 1 4 2 Nyní zbývá pouze naprogramovat tento algoritmus v Pascalu. konst n = 4; (Nastavíme konstantu, to bude délka pole) var i, j, k:integer; (Dvě proměnné pro vnořenou smyčku, jedna pro výměnu prvků) m:array of integer; (Vytvoříme pole) begin (Pole si vyžádáme z klávesnice:) Writeln("Zadejte pole:"); for i:=1 až n do begin Writeln(i, " prvek:"); Readln(m[i]); konec; (Vnější smyčka je zodpovědná za skutečnost, že musíme opakovat vnitřní smyčku tolikrát, kolikrát máme prvky pole mínus 1.) for i:=1 až n-1 do begin (Vnitřní smyčka již iteruje prvky a porovnává mezi sebou.) for j :=1 až n-i do begin (Pokud je prvek větší než následující, pak prohoď místa.) if m[j]>m then begin k:=m[j]; m[j]:=m; m:=k; konec; Zde je videonávod Štítky: Bublinové řazení Seřadit pole (1, 5, 2, 7, 6, 3) 1, 2, 5, 3, 6, 7 Říká se, že je to podobné „vznášení“ „lehčích“ prvků, jako jsou bubliny, a proto dostal algoritmus své jméno. void bubbleSort(int *a, velikost_t velikost) ( velikost_t i, j; int tmp; pro (i = 1; i< size; i++) {
for (j = 1; j < size; j++) {
if (a[j] >a) ( tmp = a[j]; a[j] = a; a = tmp; ) ) ) Tento algoritmus vždy provede (n-1) 2 kroky, bez ohledu na vstupní data. I když je pole seřazeno, bude stále procházet (n-1) 2krát. Navíc budou znovu zkontrolována již vytříděná data. Řekněme, že potřebujeme seřadit pole 1, 2, 4, 3 1 2 4 3 Jakmile jsou prvky a a a prohozeny, není již potřeba procházet touto částí pole. Vezměme to v úvahu a přepracujme algoritmus Void bubbleSort2(int *a, velikost_t velikost) ( velikost_t i, j; int tmp; pro (i = 1; i< size; i++) {
for (j = i; j >0; j--) (pokud (a[j]< a) {
tmp = a[j];
a[j] = a;
a = tmp;
}
}
}
}
Další implementace Void bubbleSort2b(int *a, velikost_t velikost) ( velikost_t i, j; int tmp; pro (i = 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 případě bude kroků o polovinu méně, ale problém s řazením již seřazeného pole stále zůstává: musíte se ujistit, že funkce seřazené pole jednou prohlédne. K tomu zavedeme proměnnou flag: bude vynechána (flag = 0), pokud je pole seřazeno. Jakmile narazíme na porušení objednávky, příznak se zvedne (příznak = 1) a začneme pole třídit jako obvykle. Void bubbleSort3(int *a, velikost_t velikost) ( size_t i; int tmp; příznak char; do ( příznak = 0; pro (i = 1; i)< size; i++) {
if (a[i] < a) {
tmp = a[i];
a[i] = a;
a = tmp;
flag = 1;
}
}
} while (flag);
}
V tomto případě je složitost také v řádu n 2 , ale v případě setříděného pole bude pouze jeden průchod. Nyní vylepšíme algoritmus. Pojďme napsat obecnou funkci pro třídění pole typu void. Protože typ proměnné není znám, budete muset dodatečně předat velikost jednoho prvku pole a porovnávací funkci. Int intSort(const void *a, const void *b) ( return *((int*)a) > *((int*)b); ) void bubbleSort3g(void *a, size_t item, size_t size, int (* cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; char flag; tmp = malloc(item); do ( flag = 0; for (i = 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);
}
Funkce vypadá ošklivě – často se počítá adresa aktuálního a předchozího prvku. Zvýrazněme pro to samostatné proměnné. Void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) ( size_t i; void *tmp = NULL; void *prev, *cur; char flag; tmp = malloc(položka do (příznak = 0; i = 1; předchozí = (znak*)a; cur = (znak*)předchozí + položka; while (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);
}
Nyní pomocí těchto funkcí můžete například třídit pole libovolného typu Void main() ( int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi(a, sizeof(int), 10, intSort); for (i = 0;< 10; i++) {
printf("%d ", a[i]);
}
_getch();
}
Třídění statického vícerozměrného pole se v podstatě neliší od třídění jednorozměrného pole. Můžete využít toho, že statická jednorozměrná a vícerozměrná pole mají v paměti stejné zastoupení. Void main() ( int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi(a, sizeof(int), 9, intSort); for (i = 0;< 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include Za druhé, můžete nejprve pole přesunout do jednorozměrného, seřadit jednorozměrné pole a poté jej přesunout zpět do dvourozměrného. Void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) ( size_t size = m*n, sub_size = n*item; size_t i, j , k void *arr = malloc(velikost * položka char *p1d = (char*)arr;< 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);
}
}
Pokud jste zmateni touto funkcí, použijte tu typovanou. Volejte z předchozího příkladu Nejen, že není považována za nejrychlejší metodu, navíc uzavírá seznam nejpomalejších metod řazení. Má to však i své výhody. Bublinové třídění je tedy nejlogičtějším a nejpřirozenějším řešením problému, pokud potřebujete uspořádat prvky v určitém pořadí. Obyčejný člověk to například využije manuálně – prostě intuicí. Název metody byl vynalezen pomocí analogie se vzduchovými bublinami ve vodě. To je metafora. Stejně jako malé vzduchové bublinky stoupají nahoru – jejich hustota je ostatně větší než hustota jakékoli kapaliny (v tomto případě vody), takže každý prvek pole, čím menší je na hodnotě, tím více se postupně proměňuje. cestu na začátek seznamu čísel. Bublinové řazení funguje takto: Ještě stručněji, algoritmus budoucího programu lze napsat takto: Nejjednodušší implementace vypadá takto: Postup Sortirovka_Puzirkom;
Start
smyčka pro j z počáteční_index před konechii_index;
smyčka pro i z počáteční_index před konechii_index-1;
Li massiv[i]>masiv (vyměnit hodnoty); Konec
Zde jednoduchost samozřejmě situaci jen zhoršuje: čím jednodušší je algoritmus, tím více se v něm objevují všechny nedostatky. Spotřeba času je příliš velká i pro malé pole (zde vstupuje do hry relativita: průměrnému člověku se může množství času zdát malé, ale v byznysu programátora se počítá každá sekunda nebo dokonce milisekunda). Bylo zapotřebí lepší implementace. Například s přihlédnutím k záměně hodnot v poli: Postup Sortirovka_Puzirkom;
Start
sortirovka
= pravda; cyklus zatím sortirovka
= pravda;
sortirovka
= nepravda;
smyčka pro i z počáteční_index před konechii_index-1;
Li massiv[i]>masiv(první prvek je větší než druhý), pak: (swap prvky); sortirovka
= pravda; (označeno, že výměna byla provedena).
Konec.
Hlavní nevýhodou je doba trvání procesu. Jak dlouho trvá vytvoření bubliny? Doba provádění se počítá ze druhé mocniny počtu čísel v poli – konečný výsledek je jí úměrný. V nejhorším případě bude pole procházet tolikrát, kolikrát je v něm prvků mínus jedna hodnota. To se děje proto, že nakonec zbude pouze jeden prvek, se kterým nelze porovnávat, a poslední průchod polem se stává zbytečnou akcí. Kromě toho je jednoduchá metoda výměnného třídění, jak se také nazývá, účinná pouze pro malá pole. S jeho pomocí nebude možné zpracovat velké množství dat: výsledkem budou buď chyby, nebo selhání programu. Bublinové řazení je celkem jednoduché na pochopení. V učebních osnovách technických univerzit se při studiu uspořádání prvků pole probírá jako první. Metoda se snadno implementuje v programovacím jazyce Delphi (D) i C/C++ (C/C plus plus), neuvěřitelně jednoduchý algoritmus pro uspořádání hodnot ve správném pořadí a Bubble Sort je ideální pro začátečníky. Algoritmus se pro své nedostatky nepoužívá pro mimoškolní účely. Počáteční pohled 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 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 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 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 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 Příklad: const kol_mas=10; var pole:pole celého čísla; a, b, k: celé číslo; writeln("vstup", kol_mas, "prvky pole"); for a:=1 to kol_mas do readln(pole[a]); for a:=1 to kol_mas-1 do begin for b:=a+1 to kol_mas do begin if massiv[a]>massiv[b] pak začněte k:=pole[a]; massiv[a]:=massiv[b]; pole[b]:=k; konec; writeln("po řazení"); for a:=1 to kol_mas do writeln(pole[a]); #zahrnout #zahrnout int main(int argc, char* argv) int massiv = (36, 697, 73, 82, 68, 12, 183, 88),i, ff; pro (; ;)( ff = 0; pro (i = 7; i>0; i--)( if (pole[i]< massiv) {
swap(array[i],massiv); if (ff == 0) break; getch(); // zpoždění obrazovkyŘazení vložení
Sloučit třídění
Rychlé řazení
Každý dobře ví, že z třídy výměnných tříd je nejrychlejší metodou tzv rychlé řazení. Píšou se o něm disertační práce, věnuje se mu mnoho článků o Habrém a na jeho základě se vymýšlejí složité hybridní algoritmy. Ale o tom dnes nebudeme mluvit rychlé řazení, a o další metodě výměny - staré dobré bublinový druh a jeho vylepšení, modifikace, mutace a variace. Hloupé řazení
Řazení je opravdu hloupé. Prohlížíme si pole zleva doprava a porovnáváme sousedy podél cesty. Pokud narazíme na dvojici vzájemně neseřazených prvků, prohodíme je a vrátíme se na nulu, tedy na úplný začátek. Znovu projdeme a zkontrolujeme pole, pokud opět narazíme na „nesprávnou“ dvojici sousedních prvků, pak vyměníme místo a začneme znovu. Pokračujeme, dokud není pole kousek po kousku seřazeno. Bublinové řazení
Nebo řazení pomocí jednoduchých výměn. Nesmrtelná klasika žánru. Princip činnosti je jednoduchý: procházíme polem od začátku do konce a současně vyměňujeme nesetříděné sousední prvky. V důsledku prvního průchodu se maximální prvek „vznese“ na poslední místo. Nyní opět procházíme neseřazenou část pole (od prvního prvku k předposlednímu) a po cestě měníme neseřazené sousedy. Druhý největší prvek bude na předposledním místě. Ve stejném duchu budeme procházet stále se zmenšující netříděnou část pole a posouvat nalezená maxima na konec. Třídění třepačky
Ona je stejná náhodné řazení, je stejná třídění koktejlů. Proces začíná jako v „bublině“: maximum vytlačíme úplně dozadu. Poté se otočíme o 180 0 a jdeme opačným směrem, přičemž se vracíme zpět na začátek nikoli na maximum, ale na minimum. Po seřazení prvního a posledního prvku v poli provedeme znovu salto. Poté, co jsme několikrát přešli tam a zpět, nakonec proces ukončíme a ocitneme se uprostřed seznamu. Řazení sudé-liché
Tentokrát se nebudeme motat po poli tam a zpět, ale opět se vrátíme k myšlence systematického obcházení zleva doprava, ale uděláme jen širší krok. Při prvním průchodu jsou prvky s lichým klíčem porovnávány se svými sousedy umístěnými na sudých místech (1. je porovnáván s 2., poté 3. se 4., 5. s 6. atd.). Pak naopak porovnáváme/měníme „sudé“ prvky s „lichými“. Pak znovu „lichá-sudá“, pak znovu „sudá-lichá“. Proces se zastaví, když po dvou po sobě jdoucích průchodech polem („lichá-sudá“ a „sudá-lichá“) nedošlo k jediné výměně. Takže to vyřídili. Za všechno mohou želvy
Trochu pozadí. V roce 1980 Włodzimierz Dobosiewicz vysvětlil, proč bublinové třídění a jeho deriváty fungují tak pomalu. Všechno je to kvůli želvám. „Želvy“ jsou malé prvky, které se nacházejí na konci seznamu. Jak jste si možná všimli, bublinové druhy se zaměřují na „králíky“ (neplést s Babushkinovými „králíky“) – prvky s velkou hodnotou na začátku seznamu. K cíli postupují velmi svižně. Pomalí plazi se ale na start plazí neochotně. Tortillu si můžete upravit pomocí hřebeny. Hřebenové třídění
V „bublině“, „třepačce“ a „liché-sudé“ se sousední prvky porovnávají při iteraci polem. Hlavní myšlenkou „hřebenu“ je zpočátku zaujmout dostatečně velkou vzdálenost mezi porovnávanými prvky a podle uspořádání pole tuto vzdálenost zúžit na minimum. Tímto způsobem pole tak trochu češeme a postupně uhlazujeme do stále úhlednějších pramenů.
** Seřazeno podle žárovky ( ukrajinština) – Bublinové řazení
*** Řazení podle hřebenu ( ukrajinština) – Hřebenové třídění
Klady:
mínusy:
Mějme určité pole: 3 1 4 2
Vezmeme první prvek „3“ a porovnáme jej s dalším „1“. Protože "3" > "1", pak si vyměňte místa:
1 3 4 2
Nyní porovnáme „3“ a „4“, tři nejsou více než čtyři, což znamená, že neděláme nic. Dále porovnejte „4“ a „2“. Čtyři jsou více než dva - měníme místa: 1 3 2 4. Cyklus je u konce. To znamená, že největší prvek by již měl být na svém místě!! Vidíme, že se to tady stalo. Kdekoli se nachází „4“ (náš největší prvek), bude to stále poslední prvek poté, co smyčka projde celým polem. Analogie - stejně jako vzduchová bublina se vznáší ve vodě, tak se náš prvek vznáší v poli. Proto se tento algoritmus nazývá "Bubble Sort". Pro umístění dalšího prvku je nutné spustit cyklus znovu, ale poslední prvek již nelze uvažovat, protože je na svém místě.
Porovnáváme „1“ a „3“ - nic neměníme.
Porovnáváme „3“ a „2“ - Tři je více než dva, což znamená, že měníme místa. Ukazuje se: 1 2 3 4 . Druhý cyklus je dokončen. Již jsme dokončili dva cykly, což znamená, že můžeme s jistotou říci, že naše poslední dva prvky již byly vytříděny. Jediné, co musíme udělat, je seřadit třetí prvek a čtvrtý automaticky zapadne na správné místo. Ještě jednou porovnáme první prvek a druhý - vidíme, že již máme vše na svém místě, což znamená, že pole lze považovat za seřazené ve vzestupném pořadí prvků.
konec; konec; (Vytiskněte výsledek:) for i:=1 až n do Write(m[i], " "); konec. Zde je výsledek:
Bubble sort C, Bubble sort, Bubble druh dvojrozměrného pole
Projdeme pole, zkontrolujeme první číslo a druhé, jsou ve vzestupném pořadí. Dále přichází porušení řádu, tyto prvky vyměníme
1, 2, 5, 7, 6, 3
Pokračujeme v procházení pole, 7 je více než 5, ale 6 je méně, takže je vyměníme
1, 2, 5, 6, 7, 3
3 rozbije pořadí, vymění místo se 7
1, 2, 5, 6, 3, 7
Vrátíme se na začátek pole a uděláme to samé
1, 2, 3, 5, 6, 7
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 4Třídění vícerozměrného pole
Kde se vzal tak neobvyklý název?
Popis algoritmu
Pseudokód založený na popsaném algoritmu
Nevýhody metody
Výhody
Princip vizuálního třídění
Příklad řazení bublin v Pascalu
Příklad řazení bublin v jazyce C