insertion sort c with examples
Una mirada en profunditat sobre la classificació per inserció amb exemples clàssics.
L’ordenació per inserció és una tècnica d’ordenació que es pot visualitzar de la manera que es juga a les cartes. La manera com inserim qualsevol carta en una baralla o la retirem, la classificació de la inserció funciona de manera similar.
La tècnica d’algoritme d’ordenació per inserció és més eficient que les tècniques d’ordenació Bubble i Selection, però és menys eficaç que la resta de tècniques com l’ordenació Quicksort i Merge.
=> Consulteu aquí els millors tutorials de formació en C ++.
Què aprendreu:
- Visió general
- Algorisme general
- Pseudocodi
- Il·lustració
- Exemple C ++
- Exemple de Java
- Anàlisi de complexitat de l'algorisme d'ordenació per inserció
- Conclusió
- Lectura recomanada
Visió general
A la tècnica d’ordenació per inserció, partim del segon element i el comparem amb el primer element i el situem en un lloc adequat. A continuació, realitzem aquest procés per als elements posteriors.
Comparem cada element amb tots els elements anteriors i posem o inserim l’element en la seva posició adequada. La tècnica d'ordenació per inserció és més factible per a matrius amb un nombre menor d'elements. També és útil per ordenar llistes enllaçades.
què és la gestió de dades de prova en proves de programari
Les llistes enllaçades tenen un punter cap a l'element següent (en el cas d'una llista enllaçada individualment) i també un punter cap a l'element anterior (en cas d'una llista doblement enllaçada). Per tant, es fa més fàcil implementar la classificació d'inserció per a una llista enllaçada.
Anem a explorar tot sobre el tipus d'inserció en aquest tutorial.
Algorisme general
Pas 1 : Repetiu els passos 2 a 5 per K = 1 a N-1
Pas 2 : set temp = A (K)
Pas 3 : conjunt J = K - 1
Pas 4 : Repetiu mentre estigui la temp<=A(J)
conjunt A (J + 1) = A (J)
conjunt J = J - 1
(final del bucle intern)
Pas 5 : conjunt A (J + 1) = temp
(final del bucle)
Pas 6 : sortir
Així, en la tècnica d'ordenació per inserció, partim del segon element ja que suposem que el primer element sempre està ordenat. Després, del segon element a l’últim element, comparem cada element amb tots els seus elements anteriors i posem aquest element en la posició adequada.
Pseudocodi
A continuació es dóna el pseudo codi per ordenar la inserció.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedureA continuació, es dóna el pseudocodi per a la classificació per inserció; a continuació, il·lustrarem aquesta tècnica a l'exemple 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í doncs, a la primera passada, comencem pel segon element.
Per tant, necessitem N nombre de passades per ordenar completament una matriu que contingui N nombre d'elements.
La il·lustració anterior es pot resumir en una forma tabular:
| Passar | Llista no classificada | comparació | Llista ordenada |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12,3} | {3,12,5,10,8,1} |
| 2 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
Com es mostra a la il·lustració anterior, comencem per la 2ndelement ja que suposem que el primer element sempre està ordenat. Comencem doncs, comparant el segon element amb el primer i canviant la posició si el segon element és inferior al primer.
Aquest procés de comparació i intercanvi situa dos elements al lloc adequat. A continuació, comparem el tercer element amb els elements anteriors (primer i segon) i realitzem el mateix procediment per situar el tercer element al lloc adequat.
D’aquesta manera, per a cada passada, posem un element al seu lloc. Per a la primera passada, situem el segon element al seu lloc. Així, en general, per col·locar N elements al seu lloc adequat, necessitem passos N-1.
com obrir fitxers de dades a Windows
A continuació, demostrarem la implementació de la tècnica de classificació per inserció en llenguatge C ++.
Exemple C ++
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < Sortida:
La llista d’entrada és
12 4 3 1 15 45 33 21 10 feb
La llista ordenada és
1 2 3 4 10 12 15 21 33 45
A continuació, veurem la implementació de Java de la tècnica de classificació per inserció.
Exemple de Java
public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } Sortida:
Llista d'entrada d'elements ...
12 4 3 1 15 45 33 21 10 feb
llista ordenada d'elements ...
1 2 3 4 10 12 15 21 33 45
quina és la meva clau de seguretat de xarxa
En ambdues implementacions, podem veure que comencem a ordenar a partir de la 2ndelement de la matriu (variable de bucle j = 1) i compareu repetidament l’element actual amb tots els seus elements anteriors i, a continuació, ordeneu l’element per situar-lo en la posició correcta si l’element actual no està en ordre amb tots els seus elements anteriors.
La classificació per inserció funciona millor i es pot completar en menys passades si la matriu està ordenada parcialment. Però a mesura que la llista es fa més gran, el seu rendiment disminueix. Un altre avantatge del tipus d'inserció és que és un tipus estable, cosa que significa que manté l'ordre d'elements iguals a la llista.
Anàlisi de complexitat de l'algorisme d'ordenació per inserció
A partir del pseudocodi i de la il·lustració anterior, la classificació per inserció és l'algorisme eficient en comparació amb la classificació per bombolles o la selecció. En lloc d’utilitzar el bucle i les condicions actuals, utilitza un bucle while que no realitza cap pas addicional quan s’ordena la matriu.
Tanmateix, fins i tot si passem la matriu ordenada a la tècnica de classificació per inserció, seguirà executant el bucle extern per a la qual cosa requereix n nombre de passos per ordenar una matriu ja ordenada. Això fa que la millor complexitat temporal de la inserció sigui una funció lineal de N on N sigui el nombre d'elements de la matriu.
Per tant, les diverses complexitats de la tècnica de classificació per inserció es donen a continuació:
La pitjor complexitat temporal del cas O (n 2) Complexitat en el millor dels casos O (n) Complexitat temporal mitjana O (n 2) Complexitat espacial O (1)
Malgrat aquestes complexitats, encara podem concloure que la classificació per inserció és l'algorisme més eficient en comparació amb les altres tècniques d'ordenació com la classificació per bombolla i la selecció.
Conclusió
L’ordenació per inserció és la més eficient de les tres tècniques comentades fins ara. Aquí, suposem que el primer element està ordenat i, a continuació, comparem cada element repetidament amb tots els elements anteriors i, a continuació, posem l’element actual a la seva posició correcta a la matriu.
En aquest tutorial, mentre discutíem el tipus d'inserció, hem observat que comparem els elements amb un increment d'1 i que també són contigus. Aquesta funció fa que es requereixin més passades per obtenir la llista ordenada.
Al nostre proper tutorial, parlarem de 'Classificació de Shell', que és una millora respecte a la classificació Selection.
En la classificació de shell, introduïm una variable coneguda com a 'increment' o 'gap' mitjançant la qual dividim la llista en sublistes que contenen elements no contigus que 'gap' separen. L’ordenació de shell requereix menys passades en comparació amb la classificació per inserció i també és més ràpida.
En els nostres futurs tutorials, coneixerem dues tècniques d'ordenació, 'Quicksort' i 'Mergesort', que utilitzen l'estratègia 'Dividir i conquerir' per ordenar les llistes de dades.
=> Mireu aquí la guia de formació per a principiants C ++.
Lectura recomanada
- Ordenació de shell en C ++ amb exemples
- Selecció Ordena en C ++ amb exemples
- MongoDB Sort () Mètode amb exemples
- Ordre d'ordenació Unix amb sintaxi, opcions i exemples
- Classificació de bombolles en C ++ amb exemples
- Ordena en pila en C ++ amb exemples
- Combina l’ordenació en C ++ amb exemples
- Ordena ràpidament en C ++ amb exemples