introduction sorting techniques c
Lista diferitelor tehnici de sortare în C ++.
Sortarea este o tehnică implementată pentru a aranja datele într-o anumită ordine. Sortarea este necesară pentru a ne asigura că datele pe care le folosim sunt într-o anumită ordine, astfel încât să putem extrage cu ușurință informațiile necesare din teancul de date.
Dacă datele sunt neîngrijite și nesortate, atunci când dorim o anumită informație, atunci va trebui să le căutăm una câte una de fiecare dată pentru a prelua datele.
=> Citiți seria Easy C ++ Training.
Astfel, este întotdeauna recomandabil să păstrăm datele aranjate într-o ordine specifică, astfel încât recuperarea informațiilor, precum și alte operațiuni efectuate pe date, să poată fi realizate cu ușurință și eficient.
Stocăm date sub formă de înregistrări. Fiecare înregistrare este alcătuită din unul sau mai multe câmpuri. Când fiecare înregistrare are o valoare unică a unui anumit câmp, îl numim câmp cheie. De exemplu, într-o clasă, Roll No poate fi un câmp unic sau cheie.
ce tipuri de teste te ajută să acopere castravetele?
Putem sorta datele pe un anumit câmp cheie și apoi să le aranjăm în ordine crescătoare / crescătoare sau în ordine descrescătoare / descrescătoare.
În mod similar, într-un dicționar telefonic, fiecare înregistrare constă în numele unei persoane, adresa și numărul de telefon. În aceasta, numărul de telefon este un câmp unic sau cheie. Putem sorta datele dicționarului pe acest câmp telefonic. Alternativ, putem sorta datele fie numeric, fie alfanumeric.
Când putem ajusta datele pentru a fi sortate în memoria principală, fără a mai fi nevoie de o altă memorie auxiliară, atunci o numim ca Sortare internă .
Pe de altă parte, atunci când avem nevoie de memorie auxiliară pentru stocarea datelor intermediare în timpul sortării, atunci numim tehnica ca Sortare externă .
În acest tutorial, vom învăța în detaliu diferitele tehnici de sortare în C ++.
Ce veți învăța:
Tehnici de sortare în C ++
C ++ acceptă diverse tehnici de sortare, așa cum sunt enumerate mai jos.
Sortare cu bule
Sortarea cu bule este cea mai simplă tehnică în care comparăm fiecare element cu elementul său adiacent și schimbăm elementele dacă nu sunt în ordine. În acest fel, la sfârșitul fiecărei iterații (numită trecere), cel mai greu element apare la sfârșitul listei.
Dat mai jos este un exemplu de sortare cu bule.
Matrice de sortat:
După cum s-a văzut mai sus, deoarece este un tablou mic și a fost aproape sortat, am reușit să obținem un tablou complet sortat în câteva pase.
Să implementăm tehnica Bubble Sort în 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 < Ieșire:
Lista de introducere ...
10 2 0 43 12
Lista elementelor sortate ...
0 2 10 12 43
După cum se vede din ieșire, în tehnica sortării cu bule, la fiecare trecere, cel mai greu element este barbotat până la capătul matricei, sortând astfel matricea complet.
Selecție Sortare
Este simplă, dar ușor de implementat o tehnică în care găsim cel mai mic element din listă și îl punem la locul potrivit. La fiecare trecere, următorul cel mai mic element este selectat și plasat în poziția corectă.
Să luăm aceeași matrice ca în exemplul anterior și să executăm Selecție Sortare pentru a sorta această matrice.
Așa cum se arată în ilustrația de mai sus, pentru N numărul de elemente luăm N-1 trece pentru a sorta complet matricea. La sfârșitul fiecărei treceri, cel mai mic element din matrice este plasat la poziția sa corectă în matricea sortată.
Apoi, să implementăm Sortarea selecției folosind 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< Ieșire:
Lista de intrare a elementelor de sortat
12 45 8 15 33
Lista sortată a elementelor este
8 12 15 33 45
În sortare de selecție, cu fiecare trecere, cel mai mic element din matrice este plasat în poziția corectă. Prin urmare, la sfârșitul procesului de sortare, obținem o matrice complet sortată.
Sortare prin inserție
Sortarea prin inserție este o tehnică în care pornim de la al doilea element al listei. Comparăm al doilea element cu cel anterior (1Sf) element și așezați-l la locul potrivit. În pasul următor, pentru fiecare element, îl comparăm cu toate elementele sale anterioare și îl inserăm la locul potrivit.
Cele trei tehnici de sortare de mai sus sunt simple și ușor de implementat. Aceste tehnici funcționează bine atunci când dimensiunea listei este mai mică. Pe măsură ce lista crește în dimensiune, aceste tehnici nu au o performanță atât de eficientă.
Tehnica va fi clară înțelegând următoarea ilustrație.
Matricea care trebuie sortată este după cum urmează:
Acum, pentru fiecare trecere, comparăm elementul curent cu toate elementele sale anterioare. Astfel, în prima trecere, începem cu al doilea element.
Deci, avem nevoie de N număr de treceri pentru a sorta complet o matrice care conține N număr de elemente.
Să implementăm tehnica Sortare prin inserție folosind 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 < Ieșire:
Lista de intrare este
12 4 3 1 15
Lista sortată este
1 3 4 12 15
Ieșirea de mai sus arată matricea sortată completă utilizând sortarea prin inserție.
Sortare rapida
Quicksort este cel mai eficient algoritm care poate fi folosit pentru sortarea datelor. Această tehnică folosește strategia „împarte și cucerește” în care problema este împărțită în mai multe subprobleme și după rezolvarea individuală a acestor subprobleme sunt îmbinate împreună pentru o listă completă sortată.
În quicksort, împărțim mai întâi lista în jurul elementului pivot și apoi plasăm celelalte elemente în pozițiile lor corespunzătoare în funcție de elementul pivot.
Așa cum se arată în ilustrația de mai sus, în tehnica Quicksort împărțim matricea în jurul unui element de pivotare astfel încât toate elementele mai mici decât pivotul să fie la stânga, care dintre cele mai mari decât pivotul să fie la dreapta. Apoi luăm aceste două matrice în mod independent și le sortăm și apoi le unim sau le cucerim pentru a obține o matrice sortată rezultată.
Cheia pentru Quicksort este selectarea elementului pivot. Poate fi primul, ultimul sau elementul de mijloc al matricei. Primul pas după selectarea elementului pivot este plasarea pivotului în poziția corectă, astfel încât să putem împărți matricea în mod corespunzător.
Să implementăm tehnica de sortare rapidă folosind 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< Ieșire:
Matrice de intrare
12 23 3 43 51
Array sortat cu Quicksort
3 12 23 43 51
În implementarea rapidă de mai sus, avem o rutină de partiție care este utilizată pentru partiționarea matricei de intrare în jurul unui element pivot care este ultimul element din matrice. Apoi apelăm rutina quicksort recursiv pentru a sorta individual sub-tablourile așa cum se arată în ilustrație.
Merge Sort
Aceasta este o altă tehnică care folosește strategia „Împarte și cucerește”. În această tehnică, împărțim lista mai întâi în jumătăți egale. Apoi executăm tehnica de sortare a combinării pe aceste liste în mod independent, astfel încât ambele liste să fie sortate. În cele din urmă, combinăm ambele liste pentru a obține o listă completă sortată.
Merge sort și sortare rapidă sunt mai rapide decât majoritatea celorlalte tehnici de sortare. Performanța lor rămâne intactă chiar și atunci când lista crește ca dimensiune.
Să vedem o ilustrare a tehnicii Merge Sort.
În ilustrația de mai sus, vedem că tehnica de sortare a îmbinării împarte matricea originală în subarrays în mod repetat până când există un singur element în fiecare subarray. Odată ce acest lucru este făcut, subarrays-urile sunt apoi sortate independent și îmbinate împreună pentru a forma o matrice sortată completă.
Apoi, să implementăm Sortare Merge folosind limbajul 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< Ieșire:
Introduceți numărul de elemente de sortat: 5
Introduceți 5 elemente de sortat: 10 21 47 3 59
Matricea sortată
3 10 21 47 59
Sortare Shell
Sortarea Shell este o extensie a tehnicii de sortare prin inserție. În sortarea prin inserție, ne ocupăm doar de următorul element, în timp ce, în sortarea shell, oferim un increment sau un spațiu folosind care creăm liste mai mici din lista părinte. Elementele din subliste nu trebuie să fie contigue, ci mai degrabă sunt separate de „gap_value”.
Sortarea Shell funcționează mai rapid decât sortarea Insertion și necesită mai puține mișcări decât cea a sortării Insertion.
Dacă oferim un decalaj de, atunci vom avea următoarele sub-liste cu fiecare element aflat la 3 elemente.
Apoi sortăm aceste trei subliste.
Matricea de mai sus pe care am obținut-o după îmbinarea sub-tablourilor sortate este aproape sortată. Acum putem efectua sortarea inserției pe această matrice pentru a sorta întreaga matrice.
Astfel vedem că odată ce împărțim matricea în subliste folosind incrementul corespunzător și apoi le îmbinăm, obținem lista aproape sortată. Tehnica de sortare a inserției din această listă poate fi realizată, iar matricea este sortată în mai puține mișcări decât sortarea de inserare originală.
Mai jos este implementarea sortării Shell în 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 Ieșire:
Matrice de sortat:
45 23 53 43 18
Matrice după sortare shell:
18 23 43 45 53
Sortarea Shell acționează astfel ca o îmbunătățire uriașă față de sortarea prin inserare și nici măcar nu ia jumătate din numărul de pași pentru a sorta matricea.
Sortare în grămadă
Heapsort este o tehnică în care structura datelor heap (min-heap sau max-heap) este utilizată pentru a sorta lista. Mai întâi construim o grămadă din lista nesortată și folosim, de asemenea, grămada pentru a sorta matricea.
Heapsort este eficient, dar nu la fel de rapid sau de tip Merge.
Așa cum se arată în ilustrația de mai sus, mai întâi construim un heap maxim din elementele matricei care urmează să fie sortate. Apoi traversăm grămada și schimbăm ultimul și primul element. În acest moment, ultimul element este deja sortat. Apoi, construim din nou un heap maxim din elementele rămase.
Treceți din nou grămada și schimbați primul și ultimul element și adăugați ultimul element la lista sortată. Acest proces este continuat până când rămâne un singur element în heap care devine primul element al listei sortate.
Să implementăm acum Sortare Heap folosind 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 Ieșire:
Matrice de intrare
4 17 3 12 9
Matricea sortată
3 4 9 12 17
Până acum am discutat pe scurt toate tehnicile majore de sortare cu o ilustrație. Vom învăța fiecare dintre aceste tehnici în detaliu în tutorialele noastre ulterioare, împreună cu diverse exemple pentru a înțelege fiecare tehnică.
Concluzie
Sortarea este necesară pentru a păstra datele sortate și în ordinea corectă. Nesortate și neîngrijite pot dura mai mult timp pentru a accesa și, prin urmare, pot afecta performanța întregului program. Astfel, pentru orice operațiuni legate de date cum ar fi accesarea, căutarea, manipularea etc., avem nevoie să fie sortate datele.
Există multe tehnici de sortare utilizate în programare. Fiecare tehnică poate fi utilizată în funcție de structura datelor pe care o folosim sau de timpul necesar algoritmului pentru a sorta datele sau spațiul de memorie luat de algoritm pentru a sorta datele. Tehnica pe care o folosim depinde și de structura datelor pe care o sortăm.
Tehnicile de sortare ne permit să sortăm structurile noastre de date într-o ordine specifică și să aranjăm elementele fie în ordine crescătoare, fie descendentă. Am văzut tehnici de sortare precum sortarea cu bule, sortarea prin selecție, sortarea prin inserție, sortirea rapidă, sortarea Shell, sortarea Merge și sortarea Heap. Sortarea cu bule și sortarea prin selecție sunt mai simple și mai ușor de implementat.
În tutorialele noastre ulterioare, vom vedea în detaliu fiecare dintre tehnicile de sortare menționate mai sus.
=> Faceți clic aici pentru cursul gratuit C ++.
Lectură recomandată
- Sortare în grămadă în C ++ cu exemple
- Merge Sortează în C ++ cu exemple
- Inserare Sortare în C ++ cu exemple
- JMeter Video 1: Introducere, descărcare și instalare JMeter
- Introducere în limbajul de programare Java - Video Tutorial
- Introducere și proces de instalare Python
- Comanda de sortare Unix cu sintaxă, opțiuni și exemple
- Metoda MongoDB Sort () cu exemple
