introduction sorting techniques c
Liste over forskjellige sorteringsteknikker i C ++.
Sortering er en teknikk som implementeres for å ordne dataene i en bestemt rekkefølge. Sortering er nødvendig for å sikre at dataene vi bruker er i en bestemt rekkefølge, slik at vi enkelt kan hente den nødvendige informasjonen fra bunken med data.
Hvis dataene er uskikkede og usorterte, når vi ønsker en bestemt del av informasjonen, må vi søke den en etter en hver gang for å hente dataene.
=> Les gjennom Easy C ++ Training Series.
Derfor er det alltid tilrådelig at vi holder dataene ordnet i en bestemt rekkefølge, slik at informasjonsinnhenting, så vel som andre operasjoner utført på dataene, kan gjøres enkelt og effektivt.
Vi lagrer data i form av poster. Hver post består av ett eller flere felt. Når hver post har en unik verdi av et bestemt felt, kaller vi det et nøkkelfelt. For eksempel, i en klasse kan rull nr være et unikt felt eller nøkkelfelt.
operativsystemer som kjører Windows-programmer
Vi kan sortere dataene i et bestemt nøkkelfelt og deretter ordne dem i stigende / økende rekkefølge eller i en fallende / synkende rekkefølge.
På samme måte, i en telefonordbok, består hver post av navnet på en person, adresse og telefonnummer. I dette er telefonnummeret et unikt felt eller nøkkelfelt. Vi kan sortere dataene i ordboken på dette telefonfeltet. Alternativt kan vi også sortere data enten numerisk eller alfanumerisk.
Når vi kan justere dataene som skal sorteres i selve hovedminnet uten behov for et annet hjelpeminne, kaller vi det som Intern sortering .
På den annen side, når vi trenger hjelpeminne for lagring av mellomdata under sortering, kaller vi teknikken som Ekstern sortering .
I denne opplæringen vil vi lære de forskjellige sorteringsteknikkene i C ++ i detalj.
Hva du vil lære:
Sorteringsteknikker i C ++
C ++ støtter forskjellige sorteringsteknikker som er oppført nedenfor.
Boblesortering
Boblesortering er den enkleste teknikken der vi sammenligner hvert element med dets tilstøtende element og bytter elementene hvis de ikke er i orden. På denne måten på slutten av hver iterasjon (kalt pass) blir det tyngste elementet boblet opp på slutten av listen.
Nedenfor er et eksempel på boblesortering.
Array som skal sorteres:
Som det er sett ovenfor, siden det er et lite utvalg og nesten var sortert, klarte vi å få et helt sortert utvalg i noen få passeringer.
La oss implementere Bubble Sort-teknikk i 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 < Produksjon:
Inngangsliste ...
10 2 0 43 12
Sortert elementliste ...
0 2 10 12 43
Som vist fra utdataene, i boblesorteringsteknikk, blir det tyngste elementet boblet opp til slutten av matrisen med hvert pass, og dermed sorterer matrisen helt.
Valg Sorter
Det er enkelt, men likevel enkelt å implementere teknikk der vi finner det minste elementet i listen og setter det på riktig sted. Ved hvert pass velges det neste minste elementet og plasseres i riktig posisjon.
La oss ta den samme matrisen som i forrige eksempel og utføre Selection Sort for å sortere denne matrisen.
Som vist i illustrasjonen ovenfor, for N antall elementer tar vi N-1 passerer for å fullstendig sortere matrisen. På slutten av hvert pass, plasseres det minste elementet i matrisen på riktig plassering i den sorterte matrisen.
La oss deretter implementere Selection Sort ved hjelp av 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< Produksjon:
Inngangsliste over elementer som skal sorteres
12 45 8 15 33
Sortert liste over elementer er
8 12 15 33 45
I utvalgssortering, med hvert pass, plasseres det minste elementet i matrisen i riktig posisjon. Derfor på slutten av sorteringsprosessen får vi et helt sortert utvalg.
Sortering av innsetting
Innsettingssortering er en teknikk der vi starter fra det andre elementet i listen. Vi sammenligner det andre elementet med det forrige (1St.) element og plasser det på riktig sted. I neste pass, for hvert element, sammenligner vi det med alle de tidligere elementene og setter det inn på riktig sted.
Ovenstående tre sorteringsteknikker er enkle og enkle å implementere. Disse teknikkene fungerer bra når listestørrelsen er mindre. Siden listen vokser i størrelse, utfører disse teknikkene ikke så effektivt.
Teknikken vil være tydelig ved å forstå følgende illustrasjon.
Matrisen som skal sorteres er som følger:
Nå for hvert pass, sammenligner vi det nåværende elementet med alle dets tidligere elementer. Dermed i første omgang starter vi med det andre elementet.
Så vi krever N antall passeringer for å fullstendig sortere en matrise som inneholder N antall elementer.
La oss implementere Insertion Sort-teknikken ved hjelp av 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 < Produksjon:
Inngangslisten er
12 4 3 1 15
Sortert liste er
1 3 4 12 15
Ovennevnte utgang viser hele den sorterte matrisen ved hjelp av innsettingssortering.
Rask sortering
Quicksort er den mest effektive algoritmen som kan brukes til å sortere dataene. Denne teknikken bruker 'divide and conquer' -strategien der problemet er delt inn i flere delproblemer, og etter å ha løst disse delproblemene, blir de samlet sammen for en komplett sortert liste.
I kviksort deler vi først listen rundt pivotelementet og plasserer deretter de andre elementene i riktig posisjon i henhold til pivotelementet.
Som vist i illustrasjonen ovenfor, deler vi i Quicksort-teknikken matrisen rundt et dreieelement slik at alle elementene som er mindre enn dreietappen, er til venstre, hvilke av de som er større enn tappen er til høyre. Så tar vi opp disse to matriser uavhengig og sorterer dem, og blir deretter med eller erobrer dem for å få et resulterende sortert utvalg.
Nøkkelen til Quicksort er valget av dreieelementet. Det kan være første, siste eller midtre element i matrisen. Det første trinnet etter å ha valgt dreieelementet er å plassere dreietappen i riktig posisjon slik at vi kan dele opp arrayet riktig.
La oss implementere Quick Sort-teknikken ved hjelp av 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< Produksjon:
Inndata matrise
12 23 3 43 51
Array sortert med Quicksort
3 12 23 43 51
I quicksort-implementeringen ovenfor har vi en partisjonsrutine som brukes til å partisjonere inngangsmatrisen rundt et pivotelement som er det siste elementet i matrisen. Deretter kaller vi quicksort-rutinen rekursivt for individuelt å sortere underarrayene som vist i illustrasjonen.
Slå sammen Sorter
Dette er en annen teknikk som bruker 'Divide and conquer' -strategien. I denne teknikken deler vi listen først i like halvdeler. Deretter utfører vi flette sorteringsteknikk på disse listene uavhengig slik at begge listene blir sortert. Til slutt fletter vi begge listene for å få en komplett sortert liste.
Flette sortering og rask sortering er raskere enn de fleste andre sorteringsteknikker. Deres ytelse forblir intakt selv når listen blir større.
La oss se en illustrasjon av Merge Sort-teknikken.
I illustrasjonen ovenfor ser vi at fusjonssorteringsteknikken deler den opprinnelige matrisen i underarrayer gjentatte ganger til det bare er ett element i hver underarray. Når dette er gjort, sorteres underarrangementene uavhengig og flettes sammen for å danne en komplett sortert matrise.
La oss deretter implementere Merge Sort ved hjelp av C ++ språk.
#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< Produksjon:
Angi antall elementer som skal sorteres: 5
Skriv inn 5 elementer som skal sorteres: 10 21 47 3 59
Sortert utvalg
3 10 21 47 59
Shell Sort
Skalsortering er en utvidelse av teknikken for sortering. I Insertion sort behandler vi bare det neste elementet, mens vi i shell sort gir en økning eller et gap der vi lager mindre lister fra foreldrelisten. Elementene i underlistene trenger ikke være sammenhengende, men de er vanligvis 'gap_value' fra hverandre.
Skalsortering utfører raskere enn innsettingssorteringen og krever færre trekk enn for innsettingssorteringen.
Hvis vi gir et gap på, vil vi ha følgende underlister med hvert element som er 3 elementer fra hverandre.
Vi sorterer deretter disse tre underlistene.
Ovenstående matrise som vi har oppnådd etter sammenslåing av de sorterte underarrayene, er nesten sortert. Nå kan vi utføre innsettingssortering på denne matrisen for å sortere hele matrisen.
Dermed ser vi at når vi deler opp matrisen i underlister ved hjelp av riktig økning og deretter slår dem sammen, får vi den nesten sorterte listen. Innsettingssorteringsteknikken på denne listen kan utføres, og matrisen sorteres i færre trekk enn den opprinnelige innsettingssorteringen.
Nedenfor er implementeringen av Shell Sort i 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 Produksjon:
Array som skal sorteres:
45 23 53 43 18
Array after shell sort:
18 23 43 45 53
Skalsortering fungerer således som en enorm forbedring i forhold til innsettingssortering og tar ikke engang halvparten av trinnene for å sortere matrisen.
Haugsortering
Heapsort er en teknikk der heap-datastruktur (min-heap eller max-heap) brukes til å sortere listen. Vi konstruerer først en haug fra den usorterte listen og bruker også dyngen til å sortere matrisen.
Heapsort er effektivt, men ikke så raskt eller Merge sort.
Som vist i illustrasjonen ovenfor, konstruerer vi først en maks bunke ut av matriseelementene som skal sorteres. Så krysser vi haugen og bytter ut det siste og første elementet. På dette tidspunktet er det siste elementet allerede sortert. Så konstruerer vi igjen en maks haug av de gjenværende elementene.
Igjen kryss haugen og bytt det første og siste elementet og legg til det siste elementet i den sorterte listen. Denne prosessen fortsetter til det bare er ett element igjen i dyngen som blir det første elementet i den sorterte listen.
La oss nå implementere Heap Sort ved hjelp av 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 Produksjon:
Inndata matrise
4 17 3 12 9
Sortert utvalg
3 4 9 12 17
Så langt har vi kort diskutert alle de viktigste sorteringsteknikkene med en illustrasjon. Vi vil lære hver av disse teknikkene i detalj i de påfølgende veiledningene sammen med forskjellige eksempler for å forstå hver teknikk.
Konklusjon
Sortering er nødvendig for å holde dataene sortert og i riktig rekkefølge. Usortert og unkempt kan ta lengre tid å få tilgang til og kan dermed treffe ytelsen til hele programmet. Derfor, for alle operasjoner relatert til data som tilgang, søk, manipulering, etc., trenger vi at dataene sorteres.
Det er mange sorteringsteknikker som brukes i programmering. Hver teknikk kan brukes avhengig av datastrukturen vi bruker, eller tiden det tar av algoritmen å sortere dataene eller minneplassen som algoritmen tar for å sortere dataene. Teknikken vi bruker, avhenger også av hvilken datastruktur vi sorterer.
Sorteringsteknikkene lar oss sortere datastrukturene våre i en bestemt rekkefølge og ordne elementene enten i stigende eller synkende rekkefølge. Vi har sett sorteringsteknikkene som Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort og Heap sort. Boblesortering og Seleksjonssortering er enklere og enklere å implementere.
I våre påfølgende opplæringer vil vi se hver av de ovennevnte sorteringsteknikkene i detalj.
=> Klikk her for gratis C ++ kurs.
Anbefalt lesing
- Haugsortering i C ++ med eksempler
- Flett sortering i C ++ med eksempler
- Innsettingssortering i C ++ med eksempler
- JMeter Video 1: Introduksjon, JMeter Last ned og installer
- Introduksjon til Java Programming Language - Video Tutorial
- Python Introduksjon og installasjonsprosess
- Unix sorteringskommando med syntaks, alternativer og eksempler
- MongoDB Sort () Metode med eksempler
