introduction sorting techniques c
Liste over de forskellige sorteringsteknikker i C ++.
Sortering er en teknik, der implementeres for at arrangere dataene i en bestemt rækkefølge. Sortering er påkrævet for at sikre, at de data, vi bruger, er i en bestemt rækkefølge, så vi let kan hente det krævede stykke information fra bunken af data.
Hvis dataene er uskadelige og usorterede, når vi ønsker et bestemt stykke information, bliver vi nødt til at søge det en efter en hver gang for at hente dataene.
=> Læs gennem Easy C ++ træningsserien.
Således er det altid tilrådeligt, at vi holder vores data arrangeret i en bestemt rækkefølge, så informationshentning såvel som andre operationer, der udføres på dataene, kan udføres let og effektivt.
Vi gemmer data i form af optegnelser. Hver post består af et eller flere felter. Når hver post har en unik værdi af et bestemt felt, kalder vi det et nøglefelt. For eksempel, i en klasse kan rulle nr. være et unikt eller nøglefelt.
program til at kopiere dvd til computer
Vi kan sortere dataene i et bestemt nøglefelt og derefter arrangere dem i stigende / stigende rækkefølge eller i en faldende / faldende rækkefølge.
På samme måde består en post i en telefonordbog af navnet på en person, adresse og telefonnummer. I dette er telefonnummeret et unikt eller nøglefelt. Vi kan sortere dataene i ordbogen i dette telefonfelt. Alternativt kan vi også sortere data enten numerisk eller alfanumerisk.
Når vi kan justere de data, der skal sorteres i selve hovedhukommelsen uden behov for en anden ekstrahukommelse, kalder vi det som Intern sortering .
På den anden side, når vi har brug for hjælpehukommelse til lagring af mellemdata under sortering, kalder vi teknikken som Ekstern sortering .
I denne vejledning lærer vi de forskellige sorteringsteknikker i C ++ i detaljer.
Hvad du lærer:
Sorteringsteknikker i C ++
C ++ understøtter forskellige sorteringsteknikker som angivet nedenfor.
Boblesortering
Boblesortering er den enkleste teknik, hvor vi sammenligner hvert element med dets tilstødende element og bytter elementerne, hvis de ikke er i orden. På denne måde i slutningen af hver iteration (kaldet et pas) bliver det tungeste element boblet op i slutningen af listen.
Nedenfor er et eksempel på boblesortering.
Array, der skal sorteres:
Som det ses ovenfor, da det er et lille array og næsten blev sorteret, lykkedes det os at få et helt sorteret array i nogle få passager.
Lad os implementere 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:
Indtastningsliste ...
10 2 0 43 12
Sorteret elementliste ...
0 2 10 12 43
Som det ses af output, i boblesorteringsteknik bobles det tungeste element op til slutningen af arrayet ved hver pasning, hvorved arrayet sorteres fuldstændigt.
Valg Sort
Det er simpelt, men alligevel let at implementere teknik, hvor vi finder det mindste element på listen og sætter det på det rette sted. Ved hvert pas vælges det næste mindste element og placeres i sin rette position.
Lad os tage det samme array som i det foregående eksempel og udføre Selection Sort for at sortere dette array.
Som vist i ovenstående illustration tager vi N-1-passager for N-antal elementer for at sortere arrayet fuldstændigt. I slutningen af hvert pass placeres det mindste element i arrayet i sin rette position i det sorterede array.
Lad os derefter implementere Selection Sort ved hjælp af 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:
Inputliste over elementer, der skal sorteres
12 45 8 15 33
Sorteret liste over elementer er
8 12 15 33 45
I valgsortering placeres det mindste element i arrayet med hver pasning i sin rette position. Derfor i slutningen af sorteringsprocessen får vi et helt sorteret array.
Indsats sortering
Indsorteringssortering er en teknik, hvor vi starter fra det andet element på listen. Vi sammenligner det andet element med dets forrige (1St.) element og placere det på det rette sted. I det næste pass, for hvert element, sammenligner vi det med alle dets tidligere elementer og indsætter elementet på det rette sted.
Ovenstående tre sorteringsteknikker er enkle og lette at implementere. Disse teknikker fungerer godt, når listen er mindre. Da listen vokser i størrelse, fungerer disse teknikker ikke så effektivt.
Teknikken vil være klar ved at forstå følgende illustration.
Det array, der skal sorteres, er som følger:
Nu for hvert pas sammenligner vi det aktuelle element med alle dets tidligere elementer. Således i det første pass, starter vi med det andet element.
Så vi kræver N antal passeringer for fuldstændigt at sortere en matrix, der indeholder N antal elementer.
Lad os implementere Insertion Sort-teknikken ved hjælp af 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:
Input listen er
12 4 3 1 15
Sorteret liste er
1 3 4 12 15
Ovenstående output viser det komplette sorterede array ved hjælp af indsættelsessortering.
Hurtig sortering
Quicksort er den mest effektive algoritme, der kan bruges til at sortere dataene. Denne teknik bruger strategien 'opdele og erobre', hvor problemet er opdelt i flere underproblemer, og efter løsning af disse underproblemer flettes hver for sig for at få en komplet sorteret liste.
I quicksort opdeler vi først listen omkring drejelementet og placerer derefter de andre elementer i deres rette positioner i henhold til drejelementet.
Som vist i ovenstående illustration opdeler vi i Quicksort-teknikken arrayet omkring et pivotelement, så alle elementerne, der er mindre end pivot, er til venstre, hvilke af dem der er større end pivot er til højre. Derefter tager vi disse to arrays uafhængigt af hinanden og sorterer dem og slutter os til eller erobrer dem for at få et resulterende sorteret array.
Nøglen til Quicksort er valget af drejelementet. Det kan være det første, sidste eller det midterste element i arrayet. Det første trin efter valg af drejelementet er at placere drejetappen i sin korrekte position, så vi kan opdele arrayet korrekt.
Lad os implementere Quick Sort-teknikken ved hjælp af 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:
Input array
12 23 3 43 51
Array sorteret med Quicksort
3 12 23 43 51
I quicksort-implementeringen ovenfor har vi en partitionsrutine, der bruges til at opdele input-arrayet omkring et pivot-element, som er det sidste element i arrayet. Derefter kalder vi quicksort-rutinen rekursivt for individuelt at sortere underarrayerne som vist i illustrationen.
Flet sortering
Dette er en anden teknik, der bruger strategien 'Opdel og erobre'. I denne teknik opdeler vi listen først i lige store halvdele. Derefter udfører vi flettesorteringsteknik på disse lister uafhængigt, så begge lister sorteres. Endelig fletter vi begge listerne for at få en komplet sorteret liste.
Flettsortering og hurtig sortering er hurtigere end de fleste andre sorteringsteknikker. Deres præstationer forbliver intakte, selv når listen bliver større.
Lad os se en illustration af Merge Sort-teknik.
I ovenstående illustration ser vi, at flettsorteringsteknikken opdeler den oprindelige matrix i underarrays gentagne gange, indtil der kun er et element i hvert underarray. Når dette er gjort, sorteres subarrays derefter uafhængigt og flettes sammen for at danne et komplet sorteret array.
Lad os derefter implementere Merge Sort ved hjælp af C ++ sprog.
#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:
Indtast antallet af elementer, der skal sorteres: 5
Indtast 5 elementer, der skal sorteres: 10 21 47 3 59
Sorteret matrix
3 10 21 47 59
Shell Sort
Skalsortering er en udvidelse af indsættelsessorteringsmetoden. I Insertion-sortering beskæftiger vi os kun med det næste element, mens vi i shell-sortering giver et trin eller et hul, hvor vi opretter mindre lister fra forældrelisten. Elementerne i underlisterne behøver ikke at være sammenhængende, men de er normalt 'gap_value' fra hinanden.
Shell-sortering udfører hurtigere end indsættelsessorteringen og kræver færre bevægelser end indsættelsessorteringen.
Hvis vi giver et hul på, vil vi have følgende underlister med hvert element, der er 3 elementer fra hinanden.
Vi sorterer derefter disse tre underlister.
Ovenstående array, som vi har opnået efter sammenlægning af de sorterede underarrays, er næsten sorteret. Nu kan vi udføre indsættelsessortering på dette array for at sortere hele arrayet.
Således ser vi, at når vi deler arrayet i underlister ved hjælp af den passende forøgelse og derefter fletter dem sammen, får vi den næsten sorterede liste. Indsætningssorteringsteknikken på denne liste kan udføres, og matrixen sorteres i færre træk end den oprindelige indsættelsessortering.
Nedenfor er implementeringen af 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, der skal sorteres:
45 23 53 43 18
Array efter shell sortering:
18 23 43 45 53
Shell-sortering fungerer således som en enorm forbedring i forhold til indsætningssortering og tager ikke engang halvdelen af antallet af trin for at sortere arrayet.
Heap Sort
Heapsort er en teknik, hvor bunke-datastruktur (min-bunke eller max-bunke) bruges til at sortere listen. Vi konstruerer først en bunke fra den usorterede liste og bruger også bunken til at sortere arrayet.
Heapsort er effektivt, men ikke så hurtigt eller flet sort.
Som vist i ovenstående illustration konstruerer vi først en maksimal bunke ud af matrixelementerne, der skal sorteres. Derefter krydser vi bunken og bytter det sidste og første element. På dette tidspunkt er det sidste element allerede sorteret. Så konstruerer vi igen en maksimal bunke ud af de resterende elementer.
Igen krydser dyngen og bytt det første og sidste element og tilføj det sidste element til den sorterede liste. Denne proces fortsættes, indtil der kun er et element tilbage i bunken, der bliver det første element på den sorterede liste.
Lad os nu implementere Heap Sort ved hjælp af 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:
Input array
4 17 3 12 9
Sorteret matrix
3 4 9 12 17
Indtil videre har vi kort diskuteret alle de vigtigste sorteringsteknikker med en illustration. Vi lærer hver af disse teknikker i detaljer i vores efterfølgende tutorials sammen med forskellige eksempler for at forstå hver teknik.
Konklusion
Sortering er påkrævet for at holde dataene sorteret og i korrekt rækkefølge. Usorteret og ukontrolleret kan tage længere tid at få adgang til og kan således ramme udførelsen af hele programmet. Således for alle operationer relateret til data som adgang, søgning, manipulation osv. Skal vi sortere dataene.
Der er mange sorteringsteknikker, der anvendes i programmeringen. Hver teknik kan anvendes afhængigt af den datastruktur, vi bruger, eller den tid, det tager af algoritmen at sortere data eller hukommelsesplads, som algoritmen tager for at sortere dataene. Den teknik, vi bruger, afhænger også af, hvilken datastruktur vi sorterer.
Sorteringsteknikkerne giver os mulighed for at sortere vores datastrukturer i en bestemt rækkefølge og arrangere elementerne enten i stigende eller faldende rækkefølge. Vi har set sorteringsteknikker som Bubblesortering, Selektionssortering, Indsætningssortering, Quicksort, Shell-sortering, Flettsortering og Heap-sortering. Boblesortering og Selektionssortering er enklere og lettere at implementere.
I vores efterfølgende tutorials vil vi se hver af de ovennævnte sorteringsteknikker i detaljer.
=> Klik her for det gratis C ++ kursus.
Anbefalet læsning
- Heapsortering i C ++ med eksempler
- Flet sortering i C ++ med eksempler
- Indsats sortering i C ++ med eksempler
- JMeter Video 1: Introduktion, JMeter Download og installer
- Introduktion til Java-programmeringssprog - Videovejledning
- Python introduktion og installationsproces
- Unix sorteringskommando med syntaks, indstillinger og eksempler
- MongoDB Sort () metode med eksempler
