Algoritem za navadno izbiranje

Algoritem za navadno izbiranje (Straight selection) je sortirni algoritem.

Deluje tako, da tabelo razdeli na urejeni in neurejeni del. Iz neurejenega dela tabele izbere najmanjši element in ga zamenja z elementom, ki se nahaja takoj za urejenim delom tabele ter urejeni del razširi za en element (zato, da obsega še novi element). Tako se urejen seznam gradi na začetku. Če je najmanjši element že na primernem mestu se zamenjava ne izvede temveč se samo razširi urejeni del tabele tako, da ga zajema.

Alternativna (obratna) varianta algoritma je, da izbiramo največji element in ga dodamo na začetek urejenega dela tabele, katera se gradi na koncu seznama.

Algoritem

for (int i=0; i<=a.length-2;++i)
{
  a[k] naj bo min objekt med a[i] do a[a.length-1];
  zamenjaj a[i] in a[k]
}

Časovna zahtevnost

Čas je neodvisen od vhodnega zaporedja. Računamo ka ceno(Cost)

opis po korakih

• prečešemo (preiščemo) vsa števila desno od naslednjega elementa, ki ga obdelujemo. Najdemo minimalno število ter ga zamenjamo z tem naslednjim številom katerega obdelujemo; ostale pustimo pri miru.
• dveh enakih števil se ne zamenja.

Algoritem v Javi

public static void straightselection(Element[] a,int atr) //navadno izbiranje manjsi
  {
    int iMin;
    Element vMin;
    for (int i=0; i<=a.length-2; ++i)
    {
      iMin=i;
      vMin=a[i];
      for (int j=i+1; j<=a.length-1; ++j)
      	if(a[j].manjsi(vMin,atr))
      	{
      		iMin=j;
      		vMin=a[j];
      	}
        a[iMin]=a[i];
      	a[i]=vMin;
      	a[0].izpisiTabelo(a,atr);
    } 
  }

Primer

Zamenjujeta se vedno i in min element. (če je i < min, i ostane na istem mestu).

8 7 3 5 0 4 2 1 3 0
i       min
0|7 3 5 8 4 2 1 3 0
  i               min
0 0|3 5 8 4 2 1 3 7
    i         min
0 0 1|5 8 4 2 3 3 7
0 0 1 2|8 4 5 3 3 7
0 0 1 2 3|4 5 8 3 7
0 0 1 2 3 3|5 8 4 7
0 0 1 2 3 3 4|8 5 7
0 0 1 2 3 3 4 5|8 7
0 0 1 2 3 3 4 5 7|8

Analiza kompleksnosti

Primerjave

c_i = (n − i − 1)

Premiki

Povezave

• Java simulacija (psevdokoda, tabela) (Selection Sort)
• The Animator (Selection Sort)
• xSortLab Applet (Selection Sort)