SelectSort - řazení výběrem

1. nalezneme prvek s nejmenší hodnotou v seznamu(poli)
2. zaměníme jej s prvkem na první pozici
3. na první pozici je nyní správný prvek, zbytek seznamu(pole) se uspořádá opakováním kroků 1 a 2 pro zbylé prvky

Asymptotická složitost SelectSort je O(n²).

SelectSort s postupem popsaným v princip, tj. hledám nejmenší prvek a přesunuji jej na první pozici a celé opakuji pro pole zkrácené odpředu.

static void SelectSort1 (int[] npole)
    {
        int i;                  //pocet opakovani vyberu
        int j;                  //index v poli
        int pozNejm;            //pozice nejmensiho prvku
        int pom;                //pomocna promenna pro vymenu
 
        for (i=0;i<npole.length-1;i++)          //vnejsi smycka
        {
            pozNejm = i;
            for(j=i;j<npole.length;j++)         //vnitrni smycka - hledani nejmensiho
            {
                if (npole[j]<npole[pozNejm])pozNejm = j;
 
            }
            if (i!=pozNejm)
            {
                pom=npole[i];
                npole[i]=npole[pozNejm];
                npole[pozNejm]=pom;
            }
        }
    }

SelectSort s obráceným postupem, tj. hledám největší prvek a přesunuji jej nakonec a celé opakuji pro pole zkrácené odzadu.

static void SelectSort2 (int[] npole)
    {
        int i;                  //pocet opakovani vyberu
        int j;                  //index v poli
        int pozNejv;            //pozice nejvetsiho prvku
        int pom;                //pomocna promenna pro vymenu
 
        for (i=npole.length-1;i<0;i--)          //vnejsi smycka
        {
            pozNejv = i;
            for(j=i;j<npole.length;j++)         //vnitrni smycka - hledani nejmensiho
            {
                if (npole[j]>npole[pozNejv])pozNejv = j;
 
            }
            if (i!=pozNejv)
            {
                pom=npole[i];
                npole[i]=npole[pozNejv];
                npole[pozNejv]=pom;
            }
        }
    }

package trideniS;
 
public class Main {
    public static void main(String[] args) {
        int[] pole = {4,3,2,1};         //nestridene pole
        int index;                      //index pro pruchod pri vypisu
 
        System.out.println("Trideni - nejmensi nazacatek");
        SelectSort1(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
        System.out.println();
        System.out.println("Trideni - nejvetsi nakonec ");
        pole = {4,3,2,1};         
        SelectSort2(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
 
 
    }
    static void SelectSort1 (int[] npole)
    {
        int i;                  //pocet opakovani vyberu
        int j;                  //index v poli
        int pozNejm;            //pozice nejmensiho prvku
        int pom;                //pomocna promenna pro vymenu
 
        for (i=0;i<npole.length-1;i++)          //vnejsi smycka
        {
            pozNejm = i;
            for(j=i;j<npole.length;j++)         //vnitrni smycka - hledani nejmensiho
            {
                if (npole[j]<npole[pozNejm])pozNejm = j;
 
            }
            if (i!=pozNejm)
            {
                pom=npole[i];
                npole[i]=npole[pozNejm];
                npole[pozNejm]=pom;
            }
        }
    }
    static void SelectSort2 (int[] npole)
    {
        int i;                  //pocet opakovani vyberu
        int j;                  //index v poli
        int pozNejv;            //pozice nejvetsiho prvku
        int pom;                //pomocna promenna pro vymenu
 
        for (i=npole.length-1;i<0;i--)          //vnejsi smycka
        {
            pozNejv = i;
            for(j=i;j<npole.length;j++)         //vnitrni smycka - hledani nejmensiho
            {
                if (npole[j]>npole[pozNejv])pozNejv = j;
 
            }
            if (i!=pozNejv)
            {
                pom=npole[i];
                npole[i]=npole[pozNejv];
                npole[pozNejv]=pom;
            }
        }
    }
 
}