introduction sorting techniques c
Lista över de olika sorteringsteknikerna i C ++.
Sortering är en teknik som implementeras för att ordna data i en specifik ordning. Sortering krävs för att säkerställa att de data som vi använder är i en viss ordning så att vi enkelt kan hämta den information som krävs från högen av data.
Om uppgifterna är okorrigerade och osorterade, när vi vill ha en viss information, måste vi söka i den en efter en varje gång för att hämta informationen.
=> Läs igenom Easy C ++ Training Series.
Det är därför alltid tillrådligt att vi håller våra data ordnade i en specifik ordning så att informationshämtning, liksom andra operationer som utförs på data, kan göras enkelt och effektivt.
Vi lagrar data i form av register. Varje post består av ett eller flera fält. När varje post har ett unikt värde för ett visst fält, kallar vi det ett nyckelfält. Till exempel, i en klass kan Roll No vara ett unikt eller nyckelfält.
operativsystem som kör Windows-program
Vi kan sortera data i ett visst nyckelfält och sedan ordna dem i stigande / ökande ordning eller i fallande / minskande ordning.
På samma sätt, i en telefonbok består varje post av namnet på en person, adress och telefonnummer. I detta är telefonnumret ett unikt eller nyckelfält. Vi kan sortera ordlistans data i det här telefonfältet. Alternativt kan vi också sortera data antingen numeriskt eller alfanumeriskt.
När vi kan justera data som ska sorteras i själva huvudminnet utan att behöva ytterligare ett extra minne, kallar vi det som Intern sortering .
Å andra sidan, när vi behöver hjälpminne för lagring av mellanliggande data under sortering, då kallar vi tekniken som Extern sortering .
I denna handledning lär vi oss de olika sorteringsteknikerna i C ++ i detalj.
Vad du kommer att lära dig:
Sorteringsteknik i C ++
C ++ stöder olika sorteringstekniker enligt listan nedan.
Bubblesortering
Bubblesortering är den enklaste tekniken där vi jämför varje element med dess intilliggande element och byter element om de inte är i ordning. På det här sättet i slutet av varje iteration (kallas ett pass) blir det tyngsta elementet bubblat i slutet av listan.
Nedan ges ett exempel på Bubble Sort.
Array som ska sorteras:
Som det ses ovan eftersom det är en liten grupp och nästan sorterades lyckades vi få en helt sorterad matris på några få pass.
Låt oss implementera Bubble Sort-teknik 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 < Produktion:
Inmatningslista ...
10 2 0 43 12
Sorterad elementlista ...
0 2 10 12 43
Som framgår av utdata, i bubblasorteringsteknik, bubblas det tyngsta elementet vid varje passering upp till slutet av arrayen och därigenom sorterar arrayen helt.
Urvalssortering
Det är enkelt men ändå enkelt att implementera teknik där vi hittar det minsta elementet i listan och placerar det på rätt plats. Vid varje pass väljs nästa minsta element och placeras i rätt läge.
Låt oss ta samma array som i föregående exempel och utföra Selection Sort för att sortera denna array.
Som visas i illustrationen ovan tar vi N-1-pass för N-antal element för att helt sortera matrisen. I slutet av varje pass placeras det minsta elementet i matrisen på rätt plats i den sorterade matrisen.
Låt oss sedan implementera Selection Sort med 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< Produktion:
Inmatningslista över element som ska sorteras
12 45 8 15 33
Sorterad lista med element är
8 12 15 33 45
I valssortering placeras det minsta elementet i matrisen vid varje passering i rätt position. Därför får vi i slutet av sorteringsprocessen en helt sorterad matris.
Insättningssortering
Insättningssortering är en teknik där vi börjar från det andra elementet i listan. Vi jämför det andra elementet med dess tidigare (1st) element och placera det på rätt plats. I nästa pass, för varje element, jämför vi det med alla dess tidigare element och infogar det på rätt plats.
Ovanstående tre sorteringstekniker är enkla och lätta att implementera. Dessa tekniker fungerar bra när liststorleken är mindre. Eftersom listan växer i storlek fungerar dessa tekniker inte så effektivt.
Tekniken kommer att vara tydlig genom att förstå följande illustration.
Matrisen som ska sorteras är som följer:
Nu för varje pass jämför vi det aktuella elementet med alla dess tidigare element. Således i det första passet börjar vi med det andra elementet.
Så vi kräver N antal passeringar för att helt sortera en matris som innehåller N antal element.
Låt oss implementera Insertion Sort-tekniken med 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 < Produktion:
Ingångslistan är
12 4 3 1 15
Sorterad lista är
1 3 4 12 15
Ovanstående utdata visar den fullständiga sorterade matrisen med insättningssortering.
Snabb sortering
Quicksort är den mest effektiva algoritmen som kan användas för att sortera data. Denna teknik använder 'dela och erövra' -strategin där problemet delas in i flera delproblem och efter lösning av dessa delproblem slås samman varandra för en komplett sorterad lista.
I quicksort delar vi först listan runt pivotelementet och placerar sedan de andra elementen i sina rätta positioner enligt pivotelementet.
Som visas i illustrationen ovan delar vi i Quicksort-tekniken arrayen runt ett svängelement så att alla element som är mindre än svängen är till vänster vilka av de som är större än svängningen är till höger. Sedan tar vi upp dessa två matriser oberoende och sorterar dem och går sedan med eller erövrar dem för att få en resulterande sorterad matris.
Nyckeln till Quicksort är valet av pivotelementet. Det kan vara första, sista eller mittelementet i matrisen. Det första steget efter att ha valt pivotelementet är att placera pivoten i rätt läge så att vi kan dela upp arrayen på rätt sätt.
Låt oss implementera Quick Sort-tekniken med 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< Produktion:
Inmatningsmatris
12 23 3 43 51
Array sorterad med Quicksort
3 12 23 43 51
I quicksortimplementeringen ovan har vi en partitionsrutin som används för att partitionera inmatningsmatrisen runt ett pivotelement som är det sista elementet i matrisen. Sedan kallar vi quicksort-rutinen rekursivt för att individuellt sortera underarrayerna enligt bilden.
Slå ihop sortering
Detta är en annan teknik som använder 'Divide and conquer' -strategin. I denna teknik delar vi listan först i lika stora halvor. Sedan utför vi sammanslagningssorteringsteknik på dessa listor oberoende så att båda listorna sorteras. Slutligen slår vi samman båda listorna för att få en komplett sorterad lista.
Slåssortering och snabbsortering är snabbare än de flesta andra sorteringstekniker. Deras prestanda förblir intakt även när listan blir större.
Låt oss se en illustration av Merge Sort-teknik.
I ovanstående illustration ser vi att sammanslagningssorteringstekniken delar upp den ursprungliga matrisen i underarrayer upprepade gånger tills det bara finns ett element i varje underarray. När detta är gjort sorteras underarrayerna oberoende och slås ihop för att bilda en komplett sorterad matris.
Låt oss sedan implementera Merge Sort med 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< Produktion:
Ange antalet element som ska sorteras: 5
Ange 5 element som ska sorteras: 10 21 47 3 59
Sorterad matris
3 10 21 47 59
Skalsortering
Skalsortering är en förlängning av insättningssorteringstekniken. I insättningssortering hanterar vi bara nästa element medan vi i skalsortering ger ett steg eller ett mellanrum där vi skapar mindre listor från överordnadslistan. Elementen i underlistorna behöver inte vara sammanhängande utan de är vanligtvis ”gap_value”.
Shell-sortering utför snabbare än insättningssorteringen och kräver färre drag än för insättningssortering.
Om vi ger ett mellanrum på kommer vi att ha följande underlistor med varje element som är 3 element från varandra.
Vi sorterar sedan dessa tre underlistor.
Ovanstående array som vi har fått efter sammanslagning av de sorterade undergrupperna är nästan sorterad. Nu kan vi utföra insättningssortering på denna array för att sortera hela arrayen.
Således ser vi att när vi delar upp matrisen i underlistor med lämpligt steg och sedan slår ihop dem får vi den nästan sorterade listan. Insättningssorteringstekniken i den här listan kan utföras och matrisen sorteras i färre drag än den ursprungliga insättningssorteringen.
Nedan följer 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 Produktion:
Array som ska sorteras:
45 23 53 43 18
Array after shell sort:
18 23 43 45 53
Skalsortering fungerar alltså som en enorm förbättring jämfört med insättningssortering och tar inte ens hälften av antalet steg för att sortera matrisen.
Heap Sort
Heapsort är en teknik där heapdatastruktur (min-heap eller max-heap) används för att sortera listan. Vi konstruerar först en hög från den osorterade listan och använder också högen för att sortera matrisen.
Heapsort är effektivt men inte lika snabbt eller merge sorten.
Som visas i illustrationen ovan konstruerar vi först en maxhöjd av de arrayelement som ska sorteras. Sedan korsar vi högen och byter ut det sista och första elementet. För närvarande är det sista elementet redan sorterat. Sedan konstruerar vi igen en maxhög av de återstående elementen.
Återigen korsa högen och byt ut det första och det sista elementet och lägg till det sista elementet i den sorterade listan. Denna process fortsätter tills det bara finns ett element kvar i högen som blir det första elementet i den sorterade listan.
Låt oss nu implementera Heap Sort med 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 Produktion:
Inmatningsmatris
4 17 3 12 9
Sorterad matris
3 4 9 12 17
Hittills har vi kort diskuterat alla viktiga sorteringstekniker med en illustration. Vi kommer att lära oss var och en av dessa tekniker i detalj i våra efterföljande handledning tillsammans med olika exempel för att förstå varje teknik.
Slutsats
Sortering krävs för att data ska sorteras och i rätt ordning. Osorterat och otrevligt kan ta längre tid att komma åt och kan därmed drabbas av hela programmets prestanda. För alla operationer relaterade till data som åtkomst, sökning, manipulation etc. behöver vi alltså informationen sorteras.
Det finns många sorteringstekniker som används vid programmering. Varje teknik kan användas beroende på vilken datastruktur vi använder eller den tid det tar av algoritmen att sortera data eller minnesutrymme som tagits av algoritmen för att sortera data. Den teknik som vi använder beror också på vilken datastruktur vi sorterar.
Sorteringsteknikerna gör det möjligt för oss att sortera våra datastrukturer i en specifik ordning och ordna elementen antingen i stigande eller fallande ordning. Vi har sett sorteringsteknikerna som Bubblesortering, Selektionssortering, Insättningssortering, Snabbsortering, Skalsortering, Sammanfogningssortering och Högsortering. Bubblesortering och urvalssortering är enklare och enklare att implementera.
I våra efterföljande handledning kommer vi att se var och en av de ovan nämnda sorteringsteknikerna i detalj.
=> Klicka här för gratis C ++ kurs.
Rekommenderad läsning
- Heapsortering i C ++ med exempel
- Slå ihop sortering i C ++ med exempel
- Insättningssortering i C ++ med exempel
- JMeter Video 1: Introduktion, JMeter Ladda ner och installera
- Introduktion till Java-programmeringsspråk - Videohandledning
- Python introduktions- och installationsprocess
- Unix Sorteringskommando med syntax, alternativ och exempel
- MongoDB Sort () -metod med exempel
