shell sort c with examples
Technika Shell Sort v C ++: Kompletný prehľad.
Triedenie škrupiny sa často nazýva vylepšenie oproti triedeniu vložením. Pri triedení vloženia berieme prírastky o 1, aby sme prvky porovnali a umiestnili ich na správne miesto.
Pri škrupinovom triedení je zoznam zoradený tak, že ho rozdelíte do niekoľkých menších podzoznamov. Nie je potrebné, aby zoznamy obsahovali súvislé prvky. Technika triedenia škrupín namiesto toho používa prírastok i, ktorý sa tiež nazýva „medzera“, a používa ho na vytvorenie zoznamu prvkov, ktoré sú od seba vzdialené „i“.
=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.
čo je plánovanie a stratégia testov
Čo sa dozviete:
Všeobecný algoritmus
Všeobecný algoritmus pre triedenie škrupín je uvedený nižšie.
shell_sort (A, N)
kde A - zoznam, ktorý sa má triediť; N - gap_size
set gap_size = N, flag = 1
zatiaľ čo gap_size> 1 alebo flag = 1, opakujte
začať
nastavený príznak = 0
nastaviť gap_size = (gap_size + 1) / 2
koniec
pre i = 0 až i<(N-gap_size) repeat
začať
ak A (i + gap_size)> A (i)
vymeniť A (i + gap_size), A (i)
nastavený príznak = 0
koniec
koniec
Vo vyššie uvedenom algoritme sme teda najskôr nastavili N, čo je medzera na triedenie poľa A pomocou škrupinového triedenia. V ďalšom kroku pomocou medzery rozdelíme pole na čiastkové polia. Potom v ďalšom kroku triedime každé z podradených polí tak, aby sme na konci slučky dostali zoradené pole.
Ďalej zvážme podrobný príklad, aby sme lepšie pochopili triedenie škrupín pomocou obrázkového znázornenia.
Ilustrácia
Ilustrujme si triedenie Shell príkladom.
Zvážte nasledujúce pole 10 prvkov.
Ak poskytneme medzeru 3, potom budeme mať nasledujúce podzoznamy s každým prvkom, ktorý je od seba vzdialený 3 prvky. Potom triedime tieto tri podlisty.
Zoradené podzoznamy a výsledný zoznam, ktoré získame po kombinácii troch zoradených podzoznamov, sú uvedené nižšie.
Vyššie uvedené pole, ktoré sme získali po zlúčení zoradených podskupín, je takmer zoradené. Teraz môžeme v tomto zozname vykonať zoradenie a zoradiť celé pole. Tento posledný krok je uvedený nižšie pre vašu informáciu.
Ako je vidieť vyššie, po vykonaní triedenia shellu a zlúčení zoradených podlistov sme na úplné zoradenie zoznamu potrebovali iba tri ťahy. Vidíme teda, že môžeme výrazne znížiť počet krokov potrebných na zoradenie poľa.
Voľba prírastku na vytvorenie podzoznamov je jedinečnou vlastnosťou triedenia škrupín.
Príklad C ++
Pozrime sa na implementáciu triedenia shellov v C ++ nižšie.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Výkon:
Pole na triedenie:
45 23 53 43 18 24 8 95 101
Pole po triedení škrupiny:
8 18 23 24 43 45 53 95 101
Použili sme ten istý zoznam, ktorý sme použili na ilustrácii, a vidíme, že začneme spočiatku vytvorením dvoch podzoznamov a následným zmenšením medzery. Po vytvorení podzoznamov podľa zadanej medzery triedime každý z podzoznamov. Po zoradení všetkých čiastkových zoznamov dostaneme takmer zoradený zoznam. Teraz je možné tento zoznam triediť pomocou základného triedenia vloženia, ktoré zaberie veľmi málo ťahov.
Ďalej implementujme triedenie shellov pomocou jazyka Java.
Príklad Java
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i Výkon:
Pole na triedenie:
45 23 53 43 18 24 8 95 101
Pole po triedení škrupiny:
8 18 23 24 43 45 53 95 101
Rovnakú logiku sme implementovali pre triedenie shell v programoch C ++ aj Java. Ako je vysvetlené vyššie v programe Java, najskôr rozdelíme pole na podskupiny a potom ich roztriedime, aby sme získali úplné zoradené pole.
Záver
Shell sort je vysoko efektívny algoritmus, ktorý vedie k zlepšeniu oproti druhu vkladania.
Zatiaľ čo triedenie vkladania funguje tak, že sa jeho prvky zväčšujú o 1, triedenie škrupiny používa parameter „medzera“ na rozdelenie poľa na podradené polia, ktorých prvky sú od seba vzdialené. Potom môžeme triediť individuálny zoznam pomocou vloženého triedenia a získať tak kompletné zoradené pole.
Shellové triedenie funguje rýchlejšie ako zoradenie podľa vloženia a v porovnaní s triedením podľa vloženia trvá zoradenie poľa menej pohybov. Náš nadchádzajúci tutoriál bude skúmať všetko o technike triedenia hromád na triedenie dátových štruktúr.
=> Navštívte tu a naučte sa C ++ od nuly.
Odporúčané čítanie
- Výber Zoradiť v C ++ s príkladmi
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Bublinové triedenie v C ++ s príkladmi
- Zoradenie vloženia v C ++ s príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Hromadné triedenie v C ++ s príkladmi
- Rýchle triedenie v C ++ s príkladmi