Meni

Sortiranje odabira na C ++ s primjerima

selection sort c with examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Dubinski pogled na sortiranje odabira na C ++ s primjerima.

Kao što i samo ime govori, tehnika sortiranja odabirom prvo odabire najmanji element u polju i zamjenjuje ga s prvim elementom u polju.

Dalje, zamjenjuje drugi najmanji element u nizu s drugim elementom i tako dalje. Tako se za svaki prolaz odabire najmanji element u nizu i stavlja u svoj odgovarajući položaj dok se cijeli niz ne sortira.

=> Ovdje pogledajte Savršeni vodič za obuku za C ++.

Sortiranje odabira

Što ćete naučiti:

Uvod

Odabir sortiranja prilično je jednostavna tehnika sortiranja jer tehnika uključuje samo pronalaženje najmanjeg elementa u svakom dodavanju i postavljanje u točan položaj.

Razvrstavanje odabira djeluje učinkovito kada je popis za sortiranje male veličine, ali na njegovu izvedbu to loše utječe jer popis za sortiranje raste.

Stoga možemo reći da sortiranje odabira nije poželjno za veće popise podataka.

Opći algoritam

Opći algoritam za sortiranje odabira dan je u nastavku:

.net pitanja i odgovori za iskusne

Sortiranje odabira (A, N)

Korak 1 : Ponovite korake 2 i 3 za K = 1 do N-1
Korak 2 : Rutina poziva najmanji (A, K, N, POS)
3. korak : Zamijenite A (K) s A (POS)
(Kraj petlje)
4. korak : IZLAZ

Rutinski najmanji (A, K, N, POS)

  • Korak 1 : (inicijaliziraj) postavi najmanjiElem = A (K)
  • Korak 2 : (inicijalizacija) postavite POS = K
  • 3. korak : za J = K + 1 do N -1, ponovite
    ako je najmanjiElem> A (J)
    postavi najmanjiElem = A (J)
    postavite POS = J
    (ako kraj)
    (Kraj petlje)
  • 4. korak : povrat POS

Pseudocode za sortiranje odabira

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)

Primjer koji ilustrira ovaj algoritam sortiranja odabira prikazan je u nastavku.

Ilustracija

Ilustracija sortiranja odabira

Prolaz2

Pass3

Pass4

Tabelarni prikaz za ovu ilustraciju prikazan je u nastavku:

Nesortirani popisNajmanje elementaPoredani popis
{18,10,7,20,2}dva{}
{18,10,7,20}7{dva}
{18,10,20}10{2,7}
{18.20}18{2,7,10)
{dvadeset}dvadeset{2,7,10,18}
{}{2,7,10,18,20}

Iz ilustracije vidimo da se sa svakim prolazom sljedeći najmanji element stavlja u ispravni položaj u razvrstanom nizu. Iz gornje ilustracije vidimo da su za sortiranje niza od 5 elemenata bila potrebna četiri prolaza. To općenito znači da nam je za sortiranje niza od N elemenata potrebno ukupno N-1 prolaza.

Slijedi implementacija algoritma sortiranja odabira u C ++.

Primjer 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<

Izlaz:

Popis ulaznih elemenata za sortiranje

11 5 2 20 42 53 23 34 101 22

Sortirani popis elemenata je

2 5 11 20 22 23 34 42 53 101

Broj prolaza potrebnih za sortiranje niza: 10

Kao što je prikazano u gornjem programu, započinjemo sortiranje odabira uspoređivanjem prvog elementa u nizu sa svim ostalim elementima u nizu. Na kraju ove usporedbe najmanji element u nizu postavljen je na prvo mjesto.

U sljedećem prolazu, koristeći isti pristup, sljedeći najmanji element u nizu postavlja se u točan položaj. To se nastavlja sve dok N elemenata ili dok se cijeli niz ne sortira.

Primjer Java

Dalje, implementiramo tehniku ​​sortiranja odabira na jeziku 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)

Izlaz:

Popis ulaza koji će se sortirati ...

11 5 2 20 42 53 23 34 101 22

ispis sortiranih elemenata ...

2 5 11 20 22 23 34 42 53 101

I u gornjem primjeru Java primjenjujemo istu logiku. U više navrata pronalazimo najmanji element u polju i stavljamo ga u razvrstani niz dok se cijeli niz potpuno ne sortira.

Stoga je sortiranje odabira najjednostavniji algoritam za primjenu jer jednostavno moramo uzastopno pronaći sljedeći najmanji element u nizu i zamijeniti ga s elementom na odgovarajućem položaju.

Analiza složenosti sortiranja odabira

Kao što se vidi u pseudokodu gore za sortiranje odabira, znamo da za odabir sortiranja trebaju dvije međusobno ugniježđene petlje da bi se dovršilo. Jedan za petlju korača kroz sve elemente u nizu i pronalazimo minimalni indeks elemenata pomoću drugog for petlje koji je ugniježđen unutar vanjske petlje for.

Stoga, s obzirom na veličinu N ulaznog niza, algoritam sortiranja odabira ima sljedeće vrijednosti vremena i složenosti.

Najgora vremenska složenostO (n2); O (n) zamjene
Najbolja vremenska složenostO (n2); O (n) zamjene
Prosječna vremenska složenostO (n2); O (n) zamjene
Složenost prostoraO (1)

Vremenska složenost O ( n dva) je uglavnom zbog upotrebe dva za petlje. Imajte na umu da tehnika sortiranja odabira nikad ne uzima više od O (n) zamjena i korisna je kad se operacija upisivanja u memoriju pokaže kao skupa.

Zaključak

Selekcijsko sortiranje je još jedna najjednostavnija tehnika sortiranja koja se lako može primijeniti. Odabir sortiranja najbolje funkcionira kada je poznat raspon vrijednosti koje se sortiraju. Što se tiče sortiranja struktura podataka pomoću selekcijskog sortiranja, možemo sortirati samo podatke koji su linearni i konačne veličine.

To znači da možemo učinkovito sortirati podatkovne strukture poput nizova pomoću selekcijskog sortiranja.

U ovom uputstvu detaljno smo razgovarali o sortiranju odabira, uključujući provedbu sortiranja odabira korištenjem jezika C ++ i Java. Logika razvrstavanja odabira je ponavljano pronalaženje najmanjeg elementa na popisu i postavljanje na pravi položaj.

U sljedećem uputstvu detaljno ćemo naučiti sortiranje umetanja za koje se kaže da je učinkovitija od ostalih dviju tehnika o kojima smo do sada razgovarali, tj. Sortiranje mjehurića i odabir.

=> Ovdje pogledajte kako biste ovdje vidjeli A-Z of C ++ Tutorials Training.

Preporučena literatura

^