introduction sorting techniques c
Llista de les diverses tècniques d'ordenació en C ++.
L’ordenació és una tècnica que s’implementa per ordenar les dades en un ordre específic. Cal ordenar per assegurar-nos que les dades que fem servir estan en un ordre concret, de manera que puguem recuperar fàcilment la informació necessària de la pila de dades.
Si les dades són desordenades i no classificades, quan volem una informació concreta, haurem de buscar-les una a una cada vegada per recuperar-les.
=> Llegiu la sèrie de formació Easy C ++.
Per tant, sempre és aconsellable que mantinguem les nostres dades ordenades en un ordre específic perquè la recuperació de la informació, així com altres operacions realitzades amb les dades, es puguin fer de manera fàcil i eficient.
Emmagatzemem dades en forma de registres. Cada registre està format per un o més camps. Quan cada registre té un valor únic d'un camp concret, l'anomenem camp clau. Per exemple, en una classe, Roll No pot ser un camp únic o clau.
avantatges i desavantatges de la base de dades relacional vs no relacional
Podem ordenar les dades en un camp clau concret i, a continuació, ordenar-les en ordre ascendent / creixent o en ordre descendent / decreixent.
De la mateixa manera, en un diccionari telefònic, tots els registres consisteixen en el nom d'una persona, l'adreça i el número de telèfon. En aquest cas, el número de telèfon és un camp únic o clau. Podem ordenar les dades del diccionari en aquest camp telefònic. Alternativament, també podem ordenar les dades numèricament o alfanumèricament.
Quan podem ajustar les dades que s’ordenaran a la pròpia memòria principal sense necessitat d’una altra memòria auxiliar, l’anomenem com Ordenació interna .
D'altra banda, quan necessitem memòria auxiliar per emmagatzemar dades intermèdies durant la classificació, anomenem la tècnica com Ordenació externa .
En aquest tutorial, aprendrem detalladament les diverses tècniques d’ordenació en C ++.
Què aprendreu:
Tècniques d'ordenació en C ++
C ++ admet diverses tècniques d’ordenació tal i com s’enumeren a continuació.
Sort de bombolles
L’ordenació de bombolles és la tècnica més senzilla en què comparem tots els elements amb els elements adjacents i els intercanviem si no estan en ordre. D’aquesta manera, al final de cada iteració (anomenada passada), l’element més pesat apareix al final de la llista.
A continuació es mostra un exemple de classificació de bombolles.
Matriu per ordenar:
Com es va veure més amunt, ja que és una matriu petita i estava gairebé ordenada, hem aconseguit obtenir una matriu totalment ordenada en unes poques passades.
Implantem la tècnica de Bubble Sort a 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 < Sortida:
Llista d'entrada ...
10 2 0 43 12
Llista d'elements ordenats ...
0 2 10 12 43
Com es veu a la sortida, en la tècnica de classificació de bombolles, amb cada passada, l'element més pesat es bombolla fins al final de la matriu, ordenant així la matriu completament.
Selecció Ordena
És senzill però fàcil d’implementar una tècnica en què trobem l’element més petit de la llista i el situem al lloc adequat. A cada passada, se selecciona l'element més petit següent i es col·loca a la seva posició correcta.
Agafem la mateixa matriu que a l'exemple anterior i realitzem Ordre de selecció per ordenar aquesta matriu.
Com es mostra a la il·lustració anterior, per a N nombre d'elements prenem passades N-1 per ordenar completament la matriu. Al final de cada passada, l'element més petit de la matriu es col·loca a la seva posició correcta a la matriu ordenada.
A continuació, implementem l'ordenació de selecció mitjançant 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< Sortida:
Llista d'entrada d'elements a ordenar
12 45 8 15 33
La llista ordenada d'elements és
8 12 15 33 45
En l'ordenació de selecció, amb cada passada, l'element més petit de la matriu es col·loca a la seva posició correcta. Per tant, al final del procés d’ordenació, obtenim una matriu totalment ordenada.
Ordenació per inserció
L’ordenació per inserció és una tècnica en què partim del segon element de la llista. Comparem el segon element amb el seu anterior (1c) i col·loqueu-lo al lloc adequat. Al següent pas, per a cada element, el comparem amb tots els elements anteriors i inserim aquest element al lloc adequat.
Les tres tècniques d’ordenació anteriors són senzilles i fàcils d’implementar. Aquestes tècniques tenen un bon rendiment quan la mida de la llista és més petita. A mesura que la llista creix en mida, aquestes tècniques no funcionen de manera eficient.
La tècnica serà clara comprenent la següent il·lustració.
La matriu que cal ordenar és la següent:
Ara, per a cada passada, comparem l’element actual amb tots els seus elements anteriors. Així, en el primer pas, comencem pel segon element.
Per tant, necessitem N nombre de passades per ordenar completament una matriu que contingui N nombre d’elements.
Implantem la tècnica d’ordenació per inserció amb 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 < Sortida:
La llista d’entrada és
12 4 3 1 15
La llista ordenada és
1 3 4 12 15
La sortida anterior mostra la matriu ordenada completa mitjançant la classificació per inserció.
Classificació ràpida
Quicksort és l’algorisme més eficient que es pot utilitzar per ordenar les dades. Aquesta tècnica utilitza l'estratègia de 'dividir i conquerir' en què el problema es divideix en diversos subproblemes i, després de resoldre aquests subproblemes, es combinen individualment per obtenir una llista ordenada completa.
A quicksort, dividim primer la llista al voltant de l’element pivot i després situem els altres elements a les seves posicions adequades segons l’element pivot.
Com es mostra a la il·lustració anterior, en la tècnica Quicksort dividim la matriu al voltant d’un element pivotant de manera que tots els elements menors que el pivot queden a la seva esquerra quins dels majors que el pivot es troben a la seva dreta. A continuació, agafem aquestes dues matrius de forma independent i les ordenem i després les unim o les conquistem per obtenir una matriu ordenada resultant.
La clau de Quicksort és la selecció de l’element pivot. Pot ser el primer, l'últim o l'element mitjà de la matriu. El primer pas després de seleccionar l'element pivot és col·locar el pivot a la seva posició correcta de manera que puguem dividir la matriu adequadament.
Implantem la tècnica d’ordenació ràpida mitjançant 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< Sortida:
Matriu d’entrada
12 23 3 43 51
Matriu ordenada amb Quicksort
3 12 23 43 51
A la implementació quicksort anterior, tenim una rutina de partició que s’utilitza per particionar la matriu d’entrada al voltant d’un element pivot que és l’últim element de la matriu. A continuació, anomenem la rutina quicksort recursivament per ordenar individualment les sub-matrius tal com es mostra a la il·lustració.
Combina la classificació
Aquesta és una altra tècnica que utilitza l'estratègia 'Dividir i conquerir'. En aquesta tècnica, dividim la llista primer en meitats iguals. A continuació, realitzem tècniques de classificació per combinació en aquestes llistes de manera independent, de manera que les dues llistes s’ordenin. Finalment, combinem les dues llistes per obtenir una llista ordenada completa.
La combinació i l’ordenació ràpida són més ràpides que la majoria d’altres tècniques d’ordenació. El seu rendiment es manté intacte fins i tot quan la llista creix en mida.
Vegem una il·lustració de la tècnica Merge Sort.
A la il·lustració anterior, veiem que la tècnica d'ordenació de combinació divideix la matriu original en subarrays repetidament fins que només hi ha un element a cada subarray. Un cop fet això, els subarrays s'ordenen independentment i es combinen per formar una matriu ordenada completa.
A continuació, implementem Merge Sort mitjançant llenguatge 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< Sortida:
Introduïu el nombre d'elements a ordenar: 5
Introduïu 5 elements per ordenar: 10 21 47 3 59
Matriu ordenada
3 10 21 47 59
Ordenació de Shell
La classificació de shell és una extensió de la tècnica de classificació per inserció. A la classificació per inserció, només tractem l’element següent, mentre que, en la classificació de shell, proporcionem un increment o un buit mitjançant el qual creem llistes més petites de la llista pare. Els elements de les sublistes no han de ser contigus, sinó que solen estar separats de ‘gap_value’.
L'ordenació de shell funciona més ràpidament que l'ordenació d'inserció i requereix menys moviments que el d'ordenació d'inserció.
Si proporcionem un buit de, tindrem les subllistes següents amb cada element que es troba a 3 elements.
A continuació, classifiquem aquestes tres llistes.
La matriu anterior que hem obtingut després de combinar les sub-matrius ordenades està gairebé ordenada. Ara podem realitzar una classificació per inserció en aquesta matriu per ordenar tota la matriu.
Així veiem que un cop dividim la matriu en subllistes mitjançant l’increment adequat i després les combinem, obtindrem la llista gairebé ordenada. Es pot realitzar la tècnica d'ordenació per inserció d'aquesta llista i la matriu s'ordena en menys moviments que l'ordenació d'inserció original.
A continuació es mostra la implementació del Shell Sort en 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 Sortida:
Matriu per ordenar:
45 23 53 43 18
Matriu després de la classificació de l'intèrpret d'ordres:
18 23 43 45 53
Per tant, la classificació de Shell actua com una gran millora respecte a la classificació per inserció i no fa ni la meitat del nombre de passos per ordenar la matriu.
Ordena en pila
Heapsort és una tècnica en què s’utilitza l’estructura de dades de pila (min-heap o max-heap) per ordenar la llista. Primer construïm un munt a partir de la llista sense classificar i també el fem servir per ordenar la matriu.
Heapsort és eficient, però no és tan ràpid ni el tipus Merge.
Com es mostra a la il·lustració anterior, primer construïm un munt màxim dels elements de la matriu a ordenar. A continuació, recorrem el munt i intercanviem l'últim i el primer element. En aquest moment, l'últim element ja està ordenat. Després tornem a construir un munt màxim dels elements restants.
Torneu a recórrer el munt i canvieu el primer i l'últim element i afegiu l'últim element a la llista ordenada. Aquest procés es continua fins que només queda un element al munt que es converteix en el primer element de la llista ordenada.
Implantem ara Heap Sort mitjançant 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 Sortida:
Matriu d’entrada
4 17 3 12 9
Matriu ordenada
3 4 9 12 17
Fins ara hem comentat breument totes les principals tècniques de classificació amb una il·lustració. Aprendrem cadascuna d’aquestes tècniques en detall als nostres tutorials posteriors juntament amb diversos exemples per entendre cada tècnica.
Conclusió
Cal ordenar-les per mantenir les dades ordenades i en l’ordre adequat. Les accions sense classificar o descuidades poden trigar més a accedir-hi i, per tant, poden afectar el rendiment de tot el programa. Per tant, per a qualsevol operació relacionada amb dades com l'accés, la cerca, la manipulació, etc., necessitem ordenar les dades.
Hi ha moltes tècniques d’ordenació emprades en la programació. Cada tècnica es pot utilitzar en funció de l'estructura de dades que estem utilitzant o del temps que l'algorisme triga a ordenar les dades o l'espai de memòria que pren l'algorisme per ordenar les dades. La tècnica que fem servir també depèn de l'estructura de dades que estiguem ordenant.
Les tècniques d’ordenació ens permeten ordenar les nostres estructures de dades en un ordre específic i disposar els elements en ordre ascendent o descendent. Hem vist tècniques d’ordenació com ara l’ordenació Bubble, la selecció, la inserció, la Quicksort, la Shell, la combinació i la classificació Heap. El tipus de bombolla i el de selecció són més senzills i fàcils d’implementar.
En els nostres tutorials posteriors, veurem detalladament cadascuna de les tècniques d’ordenació esmentades anteriorment.
=> Feu clic aquí per obtenir el curs gratuït de C ++.
Lectura recomanada
- Ordena en pila en C ++ amb exemples
- Combina l’ordenació en C ++ amb exemples
- Ordre d'inserció a C ++ amb exemples
- Vídeo JMeter 1: Introducció, descàrrega i instal·lació de JMeter
- Introducció al llenguatge de programació Java: vídeo tutorial
- Introducció i procés d’instal·lació de Python
- Ordre d'ordenació Unix amb sintaxi, opcions i exemples
- MongoDB Sort () Mètode amb exemples
