Menú

Selecció Ordena en C ++ amb exemples

selection sort c with examples

Proveu El Nostre Instrument Per Eliminar Problemes

Una mirada en profunditat de la selecció Ordenar en C ++ amb exemples.

Com el seu propi nom indica, la tècnica d'ordenació de selecció selecciona primer l'element més petit de la matriu i l'intercanvia amb el primer element de la matriu.

A continuació, canvia el segon element més petit de la matriu amb el segon element, etc. Així, per a cada passada, se selecciona l'element més petit de la matriu i es posa a la seva posició correcta fins que s'ordena tota la matriu.

=> Consulteu aquí la guia d’entrenament perfecta de C ++.

Selecció Ordena

Què aprendreu:

Introducció

L’ordenació per selecció és una tècnica d’ordenació força senzilla, ja que la tècnica només consisteix a trobar l’element més petit de cada passada i situar-lo a la posició correcta.

L'ordenació de selecció funciona de manera eficient quan la llista que es vol ordenar és de mida petita, però el seu rendiment es veu afectat greument a mesura que la llista a ordenar creix en mida.

Per tant, podem dir que no es recomana la selecció per a llistes de dades més grans.

Algorisme general

A continuació es mostra l’algorisme general per a la selecció:

neteja i reparació de registres de Windows gratuïts

Ordre de selecció (A, N)

Pas 1 : Repetiu els passos 2 i 3 per K = 1 a N-1
Pas 2 : Rutina de trucades més petita (A, K, N, TPV)
Pas 3 : Canvia A (K) amb A (POS)
(Final del bucle)
Pas 4 : SORTIR

La rutina més petita (A, K, N, TPV)

  • Pas 1 : (inicialitzar) set smallestElem = A (K)
  • Pas 2 : (inicialitzar) establir POS = K
  • Pas 3 : per a J = K + 1 a N -1, repeteix
    if smallestElem> A (J)
    set smallestElem = A (J)
    set POS = J
    (si final)
    (Final del bucle)
  • Pas 4 : tornar TPV

Pseudocodi per ordenar la selecció

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

A continuació es mostra un exemple per il·lustrar aquest algorisme d’ordenació de selecció.

Il·lustració

Selecció Ordenar il·lustració

Pass2

Passa3

Passa4

A continuació es mostra la representació tabular d’aquesta il·lustració:

Llista no classificadaElement mínimLlista ordenada
{18,10,7,20,2}2{}
{18,10,7,20}7{2}
{18,10,20}10{2,7}
{18,20}18{2,7,10)
{20}20{2,7,10,18}
{}{2,7,10,18,20}

A la il·lustració, veiem que amb cada passada, el següent element més petit es posa en la seva posició correcta a la matriu ordenada. A partir de la il·lustració anterior, veiem que per ordenar una matriu de 5 elements, es necessitaven quatre passades. Això vol dir, en general, que per ordenar una matriu de N elements, necessitem N-1 passades en total.

A continuació es mostra la implementació de l’algorisme d’ordenació de selecció en C ++.

Exemple C ++

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Sortida:

Llista d'entrada d'elements a ordenar

11 5 2 20 42 53 23 34.101 22

La llista ordenada d'elements és

2 5 11 20 22 23 34 42 53 101

Nombre de passades necessàries per ordenar la matriu: 10

Com es mostra al programa anterior, comencem a ordenar la selecció comparant el primer element de la matriu amb tots els altres elements de la matriu. Al final d'aquesta comparació, l'element més petit de la matriu es col·loca a la primera posició.

Al següent pas, utilitzant el mateix enfocament, el següent element més petit de la matriu es col·loca a la seva posició correcta. Això continua fins a N elements o fins que s'ordena tota la matriu.

Exemple de Java

A continuació, implementem la tècnica de classificació de selecció en el llenguatge Java.

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Sortida:

S'ha d'ordenar la llista d'entrada ...

11 5 2 20 42 53 23 34.101 22

imprimint elements ordenats ...

2 5 11 20 22 23 34 42 53 101

A l'exemple de Java anterior, també apliquem la mateixa lògica. Trobem repetidament l’element més petit de la matriu i el posem a la matriu ordenada fins que tota la matriu estigui completament ordenada.

Per tant, l’ordenació de selecció és l’algoritme més senzill d’implementar, ja que només hem de trobar repetidament el següent element més petit de la matriu i canviar-lo amb l’element a la seva posició adequada.

Anàlisi de complexitat de la selecció

Com es veu al pseudocodi anterior per a la selecció, sabem que la selecció requereix dos per a bucles imbricats entre si per completar-se. Un per als passos del bucle a través de tots els elements de la matriu i trobem l’índex mínim d’elements mitjançant un altre bucle for que està niat dins del bucle extern.

Per tant, donada la mida N de la matriu d'entrada, l'algorisme d'ordenació de selecció té els següents valors de temps i complexitat.

La pitjor complexitat temporal del casO (n 2); O (n) permutes
Complexitat en el millor dels casosO (n 2); O (n) permutes
Complexitat temporal mitjanaO (n 2); O (n) permutes
Complexitat espacialO (1)

La complexitat temporal d'O ( n 2) es deu principalment a l’ús de dos per a bucles. Tingueu en compte que la tècnica d'ordenació de selecció no necessita mai més que O (n) swaps i és beneficiosa quan l'operació d'escriptura de memòria resulta costosa.

Conclusió

L’ordenació per selecció és una altra tècnica d’ordenació més senzilla que es pot implementar fàcilment. L’ordenació de selecció funciona millor quan es coneix l’interval dels valors a ordenar. Per tant, pel que fa a l’ordenació d’estructures de dades mitjançant selecció, només podem ordenar estructures de dades lineals i de mida finita.

Això significa que podem ordenar de manera eficient estructures de dades com ara matrius mitjançant la selecció.

En aquest tutorial, hem analitzat detalladament el tipus de selecció, inclosa la implementació del tipus de selecció mitjançant llenguatges C ++ i Java. La lògica darrere de la classificació de selecció és trobar l’element més petit de la llista repetidament i situar-lo a la posició adequada.

Al següent tutorial, aprendrem detalladament sobre el tipus d’inserció, que es diu que és una tècnica més eficient que les altres dues tècniques que hem comentat fins ara, és a dir, el tipus de bombolles i el de selecció.

=> Consulteu aquí per veure aquí els tutorials de formació A-Z de C ++.

Lectura recomanada

^