introduction sorting techniques c
Popis različitih tehnika sortiranja u jeziku C ++.
Razvrstavanje je tehnika koja se provodi za raspoređivanje podataka određenim redoslijedom. Razvrstavanje je potrebno kako bi se osiguralo da podaci koje koristimo budu u određenom redoslijedu kako bismo lako mogli doći do potrebnih podataka iz gomile podataka.
Ako su podaci neuredni i nerazvrstani, kada želimo određeni podatak, morat ćemo ga svaki put pretraživati jedan po jedan kako bismo dohvatili podatke.
=> Pročitajte seriju Easy C ++ Training Series.
Stoga je uvijek korisno da svoje podatke držimo poredane u određenom redoslijedu kako bi se pronalaženje podataka, kao i druge radnje izvršene na podacima, mogle obavljati lako i učinkovito.
Podaci pohranjujemo u obliku zapisa. Svaki se zapis sastoji od jednog ili više polja. Kada svaki zapis ima jedinstvenu vrijednost određenog polja, nazivamo ga ključnim poljem. Na primjer, u klasi Roll No može biti jedinstveno ili ključno polje.
besplatni program za sigurnosnu kopiju za Windows 7
Podatke možemo razvrstati u određeno polje ključa, a zatim ih poredati u rastućem / rastućem redoslijedu ili u opadajućem / opadajućem redoslijedu.
Slično tome, u telefonskom rječniku svaki se zapis sastoji od imena osobe, adrese i telefonskog broja. U tome je telefonski broj jedinstveno ili ključno polje. Podatke rječnika možemo sortirati na ovom telefonskom polju. Također možemo sortirati podatke numerički ili alfanumerički.
Kada možemo prilagoditi podatke koji će se sortirati u samoj glavnoj memoriji bez potrebe za nekom drugom pomoćnom memorijom, tada ih nazivamo kao Interno sortiranje .
S druge strane, kada nam je potrebna pomoćna memorija za spremanje među podataka tijekom sortiranja, tada tehniku nazivamo kao Vanjsko sortiranje .
U ovom uputstvu detaljno ćemo naučiti razne tehnike sortiranja u jeziku C ++.
Što ćete naučiti:
Tehnike sortiranja u C ++
C ++ podržava razne tehnike sortiranja kako su navedene u nastavku.
Razvrstavanje mjehurića
Bubble sort je najjednostavnija tehnika u kojoj uspoređujemo svaki element sa susjednim elementom i mijenjamo elemente ako nisu u redu. Na taj se način na kraju svake iteracije (koja se naziva prolaz) na kraju popisa napuhavaju najteži elementi.
Slijedi primjer sortiranja mjehurića.
Niz za sortiranje:
Kao što se vidi gore, budući da se radi o malom nizu i koji je gotovo razvrstan, uspjeli smo dobiti potpuno razvrstani niz u nekoliko dodavanja.
Primijenimo tehniku Bubble Sort u 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 < Izlaz:
Popis unosa ...
10 2 0 43 12
Poređani popis elemenata ...
0 2 10 12 43
Kao što se vidi iz rezultata, u tehnici razvrstavanja mjehurića, pri svakom prolazu najteži element se oblači do kraja niza, čime se niz u potpunosti sortira.
Sortiranje odabira
Jednostavna je, ali jednostavna za implementaciju tehnika u kojoj pronalazimo najmanji element na popisu i postavljamo ga na svoje mjesto. Pri svakom prolazu odabire se sljedeći najmanji element i postavlja se u njegov odgovarajući položaj.
Uzmimo isti niz kao u prethodnom primjeru i izvedimo Sortiranje odabira da bismo sortirali ovaj niz.
Kao što je prikazano na gornjoj ilustraciji, za N broja elemenata uzimamo N-1 prolaze kako bismo u potpunosti sortirali niz. Na kraju svakog prolaza, najmanji element u nizu postavlja se na svoj odgovarajući položaj u razvrstanom nizu.
Dalje, provedimo Sortiranje odabira pomoću 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< Izlaz:
Popis ulaznih elemenata za sortiranje
12 45 8 15 33
Sortirani popis elemenata je
8 12 15 33 45
U sortiranju odabira, pri svakom prolazu, najmanji element u nizu postavlja se u svoj odgovarajući položaj. Stoga na kraju postupka sortiranja dobivamo potpuno sortirani niz.
Sortiranje umetanja
Razvrstavanje umetanja tehnika je u kojoj počinjemo od drugog elementa popisa. Drugi element uspoređujemo s prethodnim (1sv) element i smjestite ga na odgovarajuće mjesto. U sljedećem prolazu, za svaki element, uspoređujemo ga sa svim prethodnim elementima i ubacujemo taj element na odgovarajuće mjesto.
Gore navedene tri tehnike sortiranja jednostavne su i jednostavne za primjenu. Ove se tehnike dobro izvode kada je veličina popisa manja. Kako popis raste u veličini, ove tehnike ne izvode to učinkovito.
Tehnika će biti jasna razumijevanjem sljedeće ilustracije.
Niz za sortiranje je sljedeći:
Sada za svaki prolaz uspoređujemo trenutni element sa svim prethodnim elementima. Tako u prvom prolazu započinjemo s drugim elementom.
Dakle, potreban nam je N broj prolaza da bismo u potpunosti sortirali niz koji sadrži N broj elemenata.
Primijenimo tehniku sortiranja umetanja koristeći 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 < Izlaz:
Popis unosa je
12 4 3 1 15
Sortirani popis je
1 3 4 12 15
Gornji izlaz prikazuje kompletni sortirani niz pomoću sortiranja umetanja.
Brzo sortiranje
Quicksort je najučinkovitiji algoritam koji se može koristiti za sortiranje podataka. Ova tehnika koristi strategiju 'podijeli i osvoji' u kojoj je problem podijeljen na nekoliko potproblema i nakon pojedinačnog rješavanja tih podproblema spajaju se u cjelovit razvrstani popis.
U brzom sortiranju prvo dijelimo popis oko pivot elementa, a zatim postavljamo ostale elemente na odgovarajuće položaje prema pivot elementu.
Kao što je prikazano na gornjoj ilustraciji, u Quicksort tehnici dijelimo niz oko pivot elementa tako da su svi elementi manji od pivota s njegove lijeve strane, a koji su od većih od pivota s njegove desne strane. Zatim uzimamo ova dva niza neovisno i razvrstavamo ih, a zatim pridružujemo ili osvajamo kako bismo dobili rezultatski razvrstani niz.
Ključ Quicksorta je odabir pivot elementa. To može biti prvi, zadnji ili srednji element niza. Prvi korak nakon odabira pivot elementa je postavljanje pivota u njegov ispravan položaj tako da možemo na odgovarajući način podijeliti niz.
Primijenimo tehniku brzog sortiranja koristeći 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< Izlaz:
Ulazni niz
12 23 3 43 51
Niz sortiran s Quicksortom
3 12 23 43 51
U gornjoj implementaciji brzog sortiranja imamo particijsku rutinu koja se koristi za particioniranje ulaznog polja oko pivot elementa koji je posljednji element u nizu. Tada rkuzivno pozivamo rutinu sortiranja kako bismo pojedinačno razvrstali podnizove kao što je prikazano na ilustraciji.
Spoji sortiranje
Ovo je još jedna tehnika koja koristi strategiju 'Podijeli i osvoji'. U ovoj tehnici popis prvo dijelimo na jednake polovice. Zatim izvodimo tehniku sortiranja spajanjem na tim popisima neovisno, tako da se oba popisa sortiraju. Na kraju, spajamo oba popisa da bismo dobili cjeloviti razvrstani popis.
Spajanje i brzo sortiranje brže su od većine ostalih tehnika sortiranja. Njihova izvedba ostaje netaknuta čak i kad popis postane veći.
Pogledajmo ilustraciju tehnike spajanja sortiranja.
Na gornjoj ilustraciji vidimo da tehnika sortiranja spajanjem dijeli izvorni niz u više nizova sve dok u svakom podnizu nema samo jedan element. Jednom kad se to učini, podnizovi se zatim sortiraju neovisno i spajaju zajedno kako bi stvorili cjeloviti sortirani niz.
Dalje, provedimo Merge Sort koristeći jezik 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< Izlaz:
Unesite broj elemenata za sortiranje: 5
Unesite 5 elemenata za razvrstavanje: 10 21 47 3 59
Sortirani niz
3 10 21 47 59
Sortiranje školjke
Sortiranje školjke je produžetak tehnike sortiranja umetanja. U sortiranju umetanjem bavimo se samo sljedećim elementom, dok u sortiranju ljuske osiguravamo priraštaj ili prazninu pomoću koje stvaramo manje popise od nadređenog popisa. Elementi na popisima ne moraju biti susjedni, već su obično razdvojeni.
Sortiranje ljuske izvodi se brže od sortiranja Umetanje i zahtijeva manje poteza od sortiranja Umetanje.
Ako pružimo prazninu od, tada ćemo imati sljedeće pod-popise sa svakim elementom koji je razdvojen po 3 elementa.
Zatim razvrstavamo ove tri podliste.
Gornji niz koji smo dobili nakon spajanja razvrstanih podsredova gotovo je razvrstan. Sada možemo izvesti sortiranje umetanja na ovom nizu kako bismo sortirali cijeli niz.
Tako vidimo da nakon što podijelimo niz na podspise pomoću odgovarajućeg priraštaja, a zatim ih spojimo, dobit ćemo gotovo razvrstani popis. Tehnika sortiranja umetanja na ovom popisu može se izvesti, a niz se sortira u manje poteza od izvorne sorte umetanja.
Slijedi implementacija Shell Sort u 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 Izlaz:
Niz za sortiranje:
45 23 53 43 18
Niz nakon sortiranja ljuske:
18 23 43 45 53
Sortiranje ljuske tako djeluje kao ogroman napredak u odnosu na sortiranje umetanja i ne poduzima čak pola koraka za sortiranje niza.
Sortiranje po hrpi
Heapsort je tehnika u kojoj se za sortiranje popisa koristi struktura podataka hrpe (min-heap ili max-heap). Prvo gradimo hrpu s nesortiranog popisa i također koristimo hrpu za sortiranje niza.
Heapsort je učinkovit, ali nije tako brz ili sortiranje spajanjem.
Kao što je prikazano na gornjoj ilustraciji, prvo konstruiramo maksimalnu hrpu od elemenata niza koji će se sortirati. Zatim prelazimo hrpu i zamijenimo posljednji i prvi element. Trenutno je posljednji element već sortiran. Zatim iz preostalih elemenata opet konstruiramo maksimalnu hrpu.
Opet pređite hrpu i zamijenite prvi i zadnji element i dodajte zadnji element na sortirani popis. Taj se postupak nastavlja sve dok u hrpi ne ostane samo jedan element koji postaje prvi element razvrstanog popisa.
Primijenimo sada Heap Sort koristeći 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 Izlaz:
Ulazni niz
4 17 3 12 9
Sortirani niz
3 4 9 12 17
Do sada smo ukratko razgovarali o svim glavnim tehnikama sortiranja s ilustracijom. Svaku ćemo od ovih tehnika detaljno naučiti u našim sljedećim vodičima, zajedno s raznim primjerima kako bismo razumjeli svaku tehniku.
Zaključak
Sortiranje je potrebno kako bi podaci bili sortirani i u pravilnom redoslijedu. Pristup nesortiranim i neurednim može potrajati dulje, što može utjecati na izvedbu cijelog programa. Dakle, za sve operacije povezane s podacima poput pristupa, pretraživanja, manipulacije itd., Trebamo podatke sortirati.
U programiranju se koristi mnogo tehnika sortiranja. Svaka se tehnika može koristiti, ovisno o strukturi podataka koju koristimo ili vremenu koje algoritam uzima za sortiranje podataka ili memorijski prostor koji algoritam uzima za sortiranje podataka. Tehnika koju koristimo također ovisi o tome koju strukturu podataka sortiramo.
Tehnike sortiranja omogućuju nam razvrstavanje struktura podataka u određenom redoslijedu i raspoređivanje elemenata u rastućem ili silaznom redoslijedu. Vidjeli smo tehnike sortiranja poput Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort i Heap sort. Razvrstavanje mjehurića i sortiranje odabirom jednostavnije je i jednostavnije za primjenu.
U našim sljedećim vodičima detaljno ćemo vidjeti svaku od gore spomenutih tehnika sortiranja.
=> Kliknite ovdje za besplatni tečaj C ++.
Preporučena literatura
- Razvrstavanje hrpe u C ++ s primjerima
- Spoji sortiranje u C ++ s primjerima
- Sortiranje umetanja u C ++ s primjerima
- JMeter Video 1: Uvod, JMeter Preuzimanje i instaliranje
- Uvod u programski jezik Java - Video vodič
- Postupak uvođenja i instalacije Pythona
- Unix naredba za sortiranje sa sintaksom, opcijama i primjerima
- MongoDB metoda sortiranja () s primjerima
