introduction sorting techniques c
Zoznam rôznych techník triedenia v C ++.
Triedenie je technika, ktorá sa implementuje na usporiadanie údajov v konkrétnom poradí. Triedenie je potrebné, aby sa zabezpečilo, že údaje, ktoré používame, sú v konkrétnom poradí, aby sme z hromady údajov mohli ľahko získať požadovanú informáciu.
Ak sú údaje neudržiavané a netriedené, ak požadujeme konkrétnu informáciu, budeme ich musieť vždy vyhľadávať jeden po druhom, aby sme údaje mohli načítať.
=> Prečítajte si sériu Easy C ++ Training Series.
Preto je vždy vhodné, aby sme vaše údaje usporiadali v konkrétnom poradí, aby bolo možné ľahko a efektívne vyhľadávať informácie a tiež ďalšie operácie s údajmi.
Údaje ukladáme vo forme záznamov. Každý záznam je tvorený jedným alebo viacerými poľami. Keď má každý záznam jedinečnú hodnotu konkrétneho poľa, hovoríme mu kľúčové pole. Napríklad, v triede môže byť Roll No jedinečné alebo kľúčové pole.
spoločnosti, ktoré vám platia za vyskúšanie ich produktov
Údaje môžeme zoradiť podľa konkrétneho kľúčového poľa a potom ich usporiadať vzostupne / zväčšiť alebo zostupne / zmenšiť.
Podobne v telefónnom slovníku každý záznam pozostáva z mena osoby, adresy a telefónneho čísla. V tomto prípade je telefónne číslo jedinečné alebo kľúčové pole. Môžeme triediť údaje slovníka na tomto telefónnom poli. Prípadne môžeme tiež triediť údaje buď číselne, alebo alfanumericky.
Keď dokážeme upraviť dáta, ktoré sa majú triediť v samotnej hlavnej pamäti, bez potreby ďalšej pomocnej pamäte, nazvime to ako Interné triedenie .
Na druhej strane, keď potrebujeme pomocnú pamäť na ukladanie prechodných údajov počas triedenia, potom túto techniku nazveme ako Externé triedenie .
V tomto tutoriáli sa podrobne naučíme rôzne techniky triedenia v C ++.
Čo sa dozviete:
Techniky triedenia v C ++
C ++ podporuje rôzne techniky triedenia uvedené nižšie.
Triedenie bublín
Bublinové triedenie je najjednoduchšia technika, pri ktorej porovnávame každý prvok s jeho susedným prvkom a vymieňame ich, ak nie sú v poriadku. Týmto spôsobom na konci každej iterácie (nazývanej prechod) prebubláva najťažší prvok na konci zoznamu.
Nižšie je uvedený príklad bublinového triedenia.
Pole na triedenie:
Ako je vidieť vyššie, pretože je to malé pole a bolo takmer zoradené, podarilo sa nám získať úplne zoradené pole za pár priechodov.
Poďme implementovať techniku Bubble Sort v C ++.
#include using namespace std; int main () { int i, j,temp; int a[5] = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Výkon:
Zoznam vstupov ...
10 2 0 43 12
Zoznam zoradených prvkov ...
0 2 10 12 43
Ako je zrejmé z výstupu, v technike bublinového triedenia je pri každom prechode prebublávaný najťažší prvok až na koniec poľa, čím sa pole úplne roztriedi.
Výber Zoradiť
Je jednoduchá, ale ľahko implementovateľná technika, pri ktorej nájdeme najmenší prvok v zozname a umiestnime ho na správne miesto. Pri každom prechode sa vyberie ďalší najmenší prvok a umiestni sa na správne miesto.
Zoberme si rovnaké pole ako v predchádzajúcom príklade a vykonajme zoradenie výberu, aby sme toto pole zoradili.
Ako je znázornené na vyššie uvedenej ilustrácii, pre N počet prvkov vezmeme N-1 priechody na úplné zoradenie poľa. Na konci každého prechodu sa najmenší prvok v poli umiestni na správne miesto v zoradenom poli.
Ďalej implementujeme Selection Sort pomocou C ++.
#include using namespace std; int findSmallest (int[],int); int main () { int myarray[5] = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Výkon:
Zadajte zoznam prvkov, ktoré sa majú zoradiť
12 45 8 15 33
Zoradený zoznam prvkov je
8 12 15 33 45
Pri triedení výberu je pri každom prechode najmenší prvok v poli umiestnený na správne miesto. Preto na konci procesu triedenia dostaneme úplne zoradené pole.
Triedenie vloženia
Insertion sort je technika, pri ktorej vychádzame z druhého prvku zoznamu. Porovnáme druhý prvok s predchádzajúcim (1sv) prvok a umiestnite ho na správne miesto. V ďalšom postupe ho pre každý prvok porovnáme so všetkými jeho predchádzajúcimi prvkami a vložíme tento prvok na správne miesto.
Vyššie uvedené tri techniky triedenia sú jednoduché a ľahko implementovateľné. Tieto techniky fungujú dobre, ak je veľkosť zoznamu menšia. Keď sa zoznam zväčšuje, tieto techniky nie sú také efektívne.
Technika bude jasná po porozumení nasledujúcej ilustrácie.
Pole, ktoré sa má zoradiť, je nasledovné:
Teraz pre každý prechod porovnávame aktuálny prvok so všetkými jeho predchádzajúcimi prvkami. Pri prvom prechode teda začíname druhým prvkom.
Takže potrebujeme N počet prechodov na úplné triedenie poľa obsahujúceho N počet prvkov.
Poďme implementovať techniku Insertion Sort pomocou C ++.
#include using namespace std; int main () { int myarray[5] = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Výkon:
Zoznam vstupov je
12 4 3 1 15
Zoradený zoznam je
1 3 4 12 15
Vyššie uvedený výstup zobrazuje celé zoradené pole pomocou triedenia podľa vloženia.
Rýchle triedenie
Quicksort je najefektívnejší algoritmus, ktorý možno použiť na triedenie údajov. Táto technika využíva stratégiu „rozdeľuj a panuj“, v ktorej je problém rozdelený na niekoľko čiastkových problémov a po vyriešení týchto problémov sa jednotlivé čiastkové problémy jednotlivo zlúčia do jedného úplného zoradeného zoznamu.
V zozname quicksort najskôr rozdelíme zoznam okolo otočného prvku a potom umiestnime ďalšie prvky do ich správnych polôh podľa otočného prvku.
Ako je znázornené na vyššie uvedenom obrázku, v technike Quicksort rozdelíme pole okolo otočného prvku tak, že všetky prvky menšie ako otočný sú vľavo, ktoré z tých väčších ako otočný sú v jeho pravej časti. Potom vezmeme tieto dve polia nezávisle a zoradíme ich a potom ich spojíme alebo dobyjeme, aby sme získali výsledné zoradené pole.
Kľúčom k Quicksortu je výber otočného prvku. Môže to byť prvý, posledný alebo stredný prvok poľa. Prvým krokom po výbere otočného prvku je umiestniť otočný čep do správnej polohy, aby sme mohli správne rozdeliť pole.
Implementujme techniku rýchleho triedenia pomocou C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr[], int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr[j] <= pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } //quicksort algorithm void quickSort(int arr[], int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr[], int size) { int i; for (i=0; i < size; i++) cout< Výkon:
Vstupné pole
12 23 3 43 51
Pole zoradené podľa Quicksortu
3 12 23 43 51
V implementácii quicksort vyššie máme rutinu oddielov, ktorá sa používa na rozdelenie vstupného poľa okolo otočného prvku, ktorý je posledným prvkom v poli. Potom rekurzívne zavoláme rutinu rýchleho triedenia, aby sme jednotlivo zoradili čiastkové polia, ako je to znázornené na obrázku.
Zlúčiť zoradenie
Toto je ďalšia technika, ktorá využíva stratégiu „Rozdeľuj a panuj“. V tejto technike najskôr rozdelíme zoznam na rovnaké polovice. Potom na týchto zoznamoch vykonáme nezávisle techniku zlučovania, aby boli oba zoznamy zoradené. Nakoniec oba zoznamy zlúčime, aby sme získali úplný zoradený zoznam.
Zlúčenie a rýchle zoradenie sú rýchlejšie ako väčšina ostatných spôsobov triedenia. Ich výkonnosť zostáva nedotknutá, aj keď sa zoznam zväčšuje.
Pozrime sa na ilustráciu techniky Merge Sort.
Na vyššie uvedenom obrázku vidíme, že technika zlučovacieho triedenia opakovane rozdeľuje pôvodné pole do podskupín, kým v každom podskupine nie je iba jeden prvok. Akonáhle je to hotové, podradné polia sa potom samostatne triedia a zlúčia dohromady, aby vytvorili úplné zoradené pole.
Ďalej implementujme Merge Sort pomocou jazyka C ++.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray[i]; } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< Výkon:
Zadajte počet prvkov, ktoré sa majú triediť: 5
Zadajte 5 prvkov, ktoré sa majú zoradiť: 10 21 47 3 59
Zoradené pole
3 10 21 47 59
Shell Sort
Shell sort je rozšírenie techniky vkladania. Pri triedení vloženia sa zaoberáme iba ďalším prvkom, zatiaľ čo pri triedení škrupinou poskytujeme prírastok alebo medzeru, pomocou ktorých z nadradeného zoznamu vytvárame menšie zoznamy. Prvky v podzoznamoch nemusia byť súvislé, skôr sú zvyčajne oddelené od seba hodnotou „gap_value“.
Triedenie podľa shellu funguje rýchlejšie ako pri vložení a vyžaduje menej pohybov ako pri vložení.
Ak poskytneme medzeru, potom budeme mať nasledujúce podzoznamy s každým prvkom, ktorý je od seba vzdialený 3 prvky.
Potom triedime tieto tri podlisty.
Vyššie uvedené pole, ktoré sme získali po zlúčení zoradených podradených polí, sú takmer zoradené. Teraz môžeme na tomto poli vykonať zoradenie a zoradiť tak celé pole.
Vidíme teda, že akonáhle rozdelíme pole na podlisty pomocou príslušného prírastku a potom ich spojíme dohromady, dostaneme takmer zoradený zoznam. Je možné vykonať techniku triedenia vloženia v tomto zozname a pole je zoradené v menšom počte pohybov ako pôvodné triedenie vloženia.
Ďalej je uvedená implementácia Shell Sort v C ++.
#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}; //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
Pole po triedení škrupiny:
18 23 43 45 53
Shell sort teda funguje ako obrovské zlepšenie oproti sortingu s vložením a na zoradenie poľa nezaberie ani polovičný počet krokov.
Hromadné triedenie
Heapsort je technika, pri ktorej sa na triedenie zoznamu používa dátová štruktúra haldy (min. Halda alebo max. Halda). Najprv zostavíme haldu z netriedeného zoznamu a pomocou nej tiež triedime pole.
Heapsort je efektívny, ale nie taký rýchly alebo pri zlúčení.
Ako je znázornené na vyššie uvedenom obrázku, najskôr z prvkov poľa, ktoré sa majú triediť, zostrojíme maximálnu hromadu. Potom prechádzame haldu a zamieňame posledný a prvý prvok. V tejto chvíli je posledný prvok už zoradený. Potom opäť zostrojíme maximálnu hromadu zo zvyšných prvkov.
Opäť prechádzajte haldu a zamieňajte prvý a posledný prvok a pridajte posledný prvok do zoradeného zoznamu. Tento proces pokračuje, kým v halde nezostane iba jeden prvok, ktorý sa stane prvým prvkom zoradeného zoznamu.
Poďme teraz implementovať Heap Sort pomocou C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr[], int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr[root], arr[largest]); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr[], int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr[], int n) { for (int i=0; i Výkon:
Vstupné pole
4 17 3 12 9
Zoradené pole
3 4 9 12 17
Doteraz sme stručne diskutovali o všetkých hlavných technikách triedenia pomocou ilustrácie. Každú z týchto techník sa podrobne naučíme v našich ďalších cvičeniach spolu s rôznymi príkladmi, aby sme každej technike porozumeli.
Záver
Na zabezpečenie triedenia a správneho poradia je potrebné triedenie. Netriedené a neudržiavané môže trvať dlhší čas, kým získate prístup, a tak by mohli zasiahnuť výkon celého programu. Pre všetky operácie spojené s údajmi, ako je prístup, vyhľadávanie, manipulácia atď., Preto potrebujeme údaje triediť.
V programovaní sa používa veľa triediacich techník. Každá technika môže byť použitá v závislosti od dátovej štruktúry, ktorú používame, alebo od času, ktorý algoritmus vyžaduje na triedenie dát alebo pamäťového priestoru, ktorý algoritmus na triedenie dát použil. Technika, ktorú používame, závisí aj od toho, akú dátovú štruktúru triedime.
Techniky triedenia nám umožňujú triediť naše dátové štruktúry v konkrétnom poradí a usporiadať prvky buď vzostupne alebo zostupne. Videli sme techniky triedenia ako Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort a Heap sort. Triedenie podľa bublín a triedenie podľa výberu sú jednoduchšie a ľahšie implementovateľné.
V našich ďalších tutoriáloch si podrobne pozrieme každú z vyššie spomenutých techník triedenia.
=> Kliknutím sem získate bezplatný kurz C ++.
Odporúčané čítanie
- Hromadné triedenie v C ++ s príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Zoradenie vloženia v C ++ s príkladmi
- JMeter Video 1: Úvod, stiahnutie a inštalácia JMeter
- Úvod do programovacieho jazyka Java - videonávod
- Proces predstavenia a inštalácie Pythonu
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Metóda MongoDB Sort () s príkladmi