introduction sorting techniques c
Seznam različnih tehnik razvrščanja v jeziku C ++.
Razvrščanje je tehnika, ki se izvaja za razvrščanje podatkov v določenem vrstnem redu. Razvrščanje je potrebno, da zagotovimo, da so podatki, ki jih uporabljamo, v določenem vrstnem redu, tako da lahko zlahka pridobimo zahtevane podatke iz kupa podatkov.
Če so podatki neurejeni in nesortirani, ko želimo določen podatek, ga bomo morali vsakič enkrat poiskati, da jih pridobimo.
=> Preberite serijo Easy C ++ Training Series.
Zato je vedno priporočljivo, da podatke hranimo urejene v določenem vrstnem redu, tako da lahko pridobivanje informacij in druge postopke, ki se izvajajo s podatki, enostavno in učinkovito.
Podatke hranimo v obliki zapisov. Vsak zapis je sestavljen iz enega ali več polj. Ko ima vsak zapis edinstveno vrednost določenega polja, ga imenujemo ključno polje. Na primer, v razredu je Roll No lahko enolično ali ključno polje.
kako narediti skriptne strani
Podatke lahko razvrstimo v določeno ključno polje in jih nato razvrstimo po naraščajočem / naraščajočem zaporedju ali po padajočem / padajočem vrstnem redu.
Podobno je v telefonskem slovarju vsak zapis sestavljen iz imena osebe, naslova in telefonske številke. Pri tem je telefonska številka edinstveno ali ključno polje. Podatke slovarja lahko razvrstimo na tem telefonskem polju. Podatke lahko razvrstimo tudi številčno ali alfanumerično.
Ko lahko prilagodimo podatke, ki bodo razvrščeni v samem glavnem pomnilniku, ne da bi potrebovali drug pomožni pomnilnik, potem to imenujemo kot Notranje razvrščanje .
Po drugi strani pa, ko potrebujemo pomožni pomnilnik za shranjevanje vmesnih podatkov med razvrščanjem, potem tehniko imenujemo kot Zunanje razvrščanje .
V tej vadnici bomo podrobno spoznali različne tehnike razvrščanja v jeziku C ++.
Kaj se boste naučili:
Tehnike razvrščanja v jeziku C ++
C ++ podpira različne tehnike razvrščanja, kot so navedene spodaj.
Razvrstitev mehurčkov
Bubble sort je najpreprostejša tehnika, pri kateri vsak element primerjamo s sosednjim elementom in elemente zamenjamo, če niso v redu. Tako se na koncu vsake ponovitve (imenovane prelaz) na koncu seznama napihne najtežji element.
Spodaj je primer sortiranja mehurčkov.
Niz, ki ga je treba razvrstiti:
Kot je razvidno zgoraj, ker gre za majhno polje in je bilo skoraj razvrščeno, smo v nekaj prehodih uspeli dobiti popolnoma razvrščeno polje.
Uvedimo tehniko razvrščanja po mehurčkih v jeziku 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 < Izhod:
Seznam vnosov…
10 2 0 43 12
Razvrščen seznam elementov…
0 2 10 12 43
Kot je razvidno iz izhoda, je v tehniki razvrščanja mehurčkov pri vsakem prehodu najtežji element mehurček do konca polja, s čimer se vrsta popolnoma razvrsti.
Razvrsti razvrstitev
Preprosta, a enostavna izvedba tehnike, pri kateri najdemo najmanjši element na seznamu in ga postavimo na svoje mesto. Ob vsakem prehodu se izbere naslednji najmanjši element in postavi v svoj pravilen položaj.
Vzemimo isto matriko kot v prejšnjem primeru in izvedemo Selection Sort, da razvrstimo to matriko.
Kot je prikazano na zgornji sliki, za N število elementov vzamemo N-1 prehode, da popolnoma razvrstimo matriko. Na koncu vsakega prehoda je najmanjši element v matriki postavljen na svoj pravilen položaj v razvrščeni matriki.
Nato izvedimo Selection Sort z uporabo 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< Izhod:
Seznam vnosov elementov, ki jih je treba razvrstiti
12 45 8 15 33
Razvrščen seznam elementov je
8 12 15 33 45
Pri izbirnem razvrščanju je z vsakim prehodom najmanjši element v matriki postavljen na svoj pravilen položaj. Na koncu postopka razvrščanja dobimo popolnoma razvrščeno matriko.
Razvrstitev vstavka
Razvrstitev pri vstavljanju je tehnika, pri kateri začnemo pri drugem elementu seznama. Drugi element primerjamo s prejšnjim (1st) in ga postavite na svoje mesto. V naslednjem prehodu ga za vsak element primerjamo z vsemi prejšnjimi elementi in ga vstavimo na ustrezno mesto.
Zgornje tri tehnike razvrščanja so preproste in enostavne za izvedbo. Te tehnike se dobro obnesejo, ko je velikost seznama manjša. Ko se seznam povečuje, te tehnike ne delujejo tako učinkovito.
Tehnika bo jasna z razumevanjem naslednje ilustracije.
Niz, ki ga je treba razvrstiti, je naslednji:
Zdaj za vsak prehod primerjamo trenutni element z vsemi prejšnjimi elementi. Tako pri prvem podajanju začnemo z drugim elementom.
Torej potrebujemo N število prehodov za popolno razvrščanje matrike, ki vsebuje N število elementov.
Izvedimo tehniko razvrščanja po vstavitvi s pomočjo 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 < Izhod:
Seznam vnosov je
12 4 3 1 15
Razvrščen seznam je
1 3 4 12 15
Zgornji izhod prikazuje celotno razvrščeno polje z uporabo vstavljanja.
Hitro razvrščanje
Quicksort je najučinkovitejši algoritem, ki ga lahko uporabimo za razvrščanje podatkov. Ta tehnika uporablja strategijo »deli in osvoji«, pri kateri je problem razdeljen na več podproblemov in se po rešitvi teh podproblemov združijo v popoln razvrščen seznam.
V hitrem vrstnem redu najprej razdelimo seznam okoli vrtilnega elementa, nato pa postavimo ostale elemente na ustrezne položaje glede na vrtilni element.
Kot je prikazano na zgornji sliki, v tehniki Quicksort matriko razdelimo okoli vrtilnega elementa tako, da so vsi elementi, ki so manjši od vrtišča, na levi, kateri od tistih, ki so večji od vrtišča, so na desni. Nato ta dva niza zavzamemo samostojno in jih razvrstimo ter nato združimo ali osvojimo, da dobimo nastalo razvrščeno polje.
Ključ Quicksorta je izbira vrtilnega elementa. Lahko je prvi, zadnji ali srednji element polja. Prvi korak po izbiri elementa vrtišča je postavitev vrtišča v pravi položaj, da lahko matriko ustrezno razdelimo.
Uvedimo tehniko hitrega razvrščanja s pomočjo 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< Izhod:
Vhodno polje
12 23 3 43 51
Niz razvrščen s Quicksort
3 12 23 43 51
V zgornji izvedbi hitrega sortiranja imamo particijsko rutino, ki se uporablja za razdelitev vhodne matrike okoli vrtilnega elementa, ki je zadnji element v matriki. Nato rekurzivno pokličemo rutino hitrega sortiranja, da posamično razvrstimo podniza, kot je prikazano na sliki.
Združi razvrsti
To je še ena tehnika, ki uporablja strategijo »deli in vladaj«. Pri tej tehniki seznam najprej razdelimo na enaki polovici. Nato na teh seznamih izvedemo tehniko sortiranja z združevanjem, tako da sta oba seznama razvrščena. Na koncu združimo oba seznama, da dobimo popoln razvrščen seznam.
Razvrščanje z združitvijo in hitro razvrščanje sta hitrejša od večine drugih tehnik razvrščanja. Njihova uspešnost ostaja nedotaknjena, tudi če se seznam poveča.
Oglejmo si ponazoritev tehnike spajanja razvrščanja.
Na zgornji sliki vidimo, da tehnika sortiranja z združevanjem izvorno matriko večkrat deli na podniz, dokler ni v vsaki podmreži samo en element. Ko je to končano, se podnizi nato samostojno razvrstijo in združijo v celotno razvrščeno polje.
Nato izvedimo Merge Sort z uporabo jezika 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< Izhod:
Vnesite število elementov za razvrščanje: 5
Vnesite 5 elementov za razvrščanje: 10 21 47 3 59
Razvrščeno polje
3 10 21 47 59
Razvrstitev lupine
Razvrščanje lupine je podaljšek tehnike razvrščanja vstavljanja. Pri razvrščanju vstavitve imamo opravka le z naslednjim elementom, medtem ko pri razvrščanju lupine zagotovimo prirastek ali vrzel, s katero iz nadrejenega seznama ustvarimo manjše sezname. Ni nujno, da so elementi na podseznamih sosednji, ampak so navadno ločeni med vrzelmi.
Razvrščanje lupine deluje hitreje kot razvrščanje vstavitve in zahteva manj premikov kot razvrščanje vstavitve.
Če zagotovimo vrzel, potem bomo imeli naslednje pod-sezname z vsakim elementom, ki je ločen po 3 elemente.
Nato razvrstimo te tri sezname.
Zgornji niz, ki smo ga dobili po združitvi razvrščenih podnizov, je skoraj razvrščen. Zdaj lahko na tej matriki izvedemo razvrščanje vstavljanja, da razvrstimo celotno matriko.
Tako vidimo, da ko matriko z ustreznim prirastkom razdelimo na sezname in jih nato združimo, dobimo skoraj razvrščen seznam. Na tem seznamu je mogoče izvesti tehniko razvrščanja vstavljanja in matriko razvrstiti v manj premikih kot prvotna razvrstitev vstavitve.
Spodaj je prikazano razvrščanje lupine v jeziku 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 Izhod:
Niz, ki ga je treba razvrstiti:
45 23 53 43 18
Niz po razvrščanju lupine:
18 23 43 45 53
Razvrščanje lupine tako deluje kot velik napredek v primerjavi z razvrščanjem vstavkov in ne opravi niti polovice korakov za razvrščanje polja.
Razvrsti kup
Heapsort je tehnika, pri kateri se za razvrščanje seznama uporablja struktura podatkov kopice (min-heap ali max-heap). Najprej zgradimo kopico iz nesortiranega seznama, kup pa uporabimo tudi za razvrščanje polja.
Heapsort je učinkovit, vendar ne tako hiter ali Merge sort.
Kot je prikazano na zgornji sliki, najprej sestavimo največ kup iz elementov matrike, ki jih je treba razvrstiti. Nato prehodimo kup in zamenjamo zadnji in prvi element. Trenutno je zadnji element že razvrščen. Nato iz preostalih elementov spet sestavimo največ kup.
Spet prehodite kup in zamenjajte prvi in zadnji element ter dodajte zadnji element na razvrščeni seznam. Ta postopek se nadaljuje, dokler na kupu ne ostane le en element, ki postane prvi element razvrščenega seznama.
Zdaj uporabimo Heap Sort z uporabo 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 Izhod:
Vhodno polje
4 17 3 12 9
Razvrščeno polje
3 4 9 12 17
Do zdaj smo s ponazoritvijo na kratko razpravljali o vseh glavnih tehnikah razvrščanja. Vsako od teh tehnik se bomo podrobno naučili v naslednjih vajah skupaj z različnimi primeri za razumevanje posamezne tehnike.
Zaključek
Razvrščanje je potrebno, da so podatki razvrščeni in v pravilnem vrstnem redu. Dostop do nesortiranih in neurejenih lahko traja dlje časa in tako lahko vpliva na delovanje celotnega programa. Za vse operacije, povezane s podatki, kot so dostop, iskanje, manipulacija itd., Moramo podatke razvrstiti.
Pri programiranju je uporabljenih veliko tehnik razvrščanja. Vsako tehniko lahko uporabimo glede na strukturo podatkov, ki jo uporabljamo, ali čas, ki ga algoritem porabi za razvrščanje podatkov ali prostora v pomnilniku, ki ga zavzame algoritem za razvrščanje podatkov. Tehnika, ki jo uporabljamo, je odvisna tudi od tega, katero strukturo podatkov razvrščamo.
Tehnike razvrščanja omogočajo razvrščanje podatkovnih struktur v določenem vrstnem redu in razvrščanje elementov v naraščajočem ali padajočem vrstnem redu. Videli smo tehnike razvrščanja, kot so Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort in Heap sort. Razvrščanje mehurčkov in razvrščanje po izbiri sta enostavnejša in enostavnejša za izvedbo.
V naslednjih vajah bomo podrobno videli vsako od zgoraj omenjenih tehnik razvrščanja.
=> Kliknite tukaj za brezplačni tečaj C ++.
Priporočeno branje
- Razvrstitev kopice v C ++ z primeri
- Združi razvrstitev v jeziku C ++ s primeri
- Razvrstitev vstavka v C ++ z primeri
- JMeter Video 1: Uvod, JMeter Prenos in namestitev
- Uvod v programski jezik Java - Video vadnica
- Uvod in postopek namestitve Pythona
- Ukaz za razvrščanje Unix s sintakso, možnostmi in primeri
- Metoda sortiranja () MongoDB () s primeri
