BubbleSort - Bublinkové řazení

Algoritmus opakovaně prochází seznam(pole) a porovnává každé dva sousedící prvky. Pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků se opakuje dokud není seznam(pole) seřazený(é).

Asymptotická složitost bublinkového řazení je O(n²).

V poli se posunuje největší prvek na jeho konec, při opakování zkracujeme průchod polem odzadu. Pracujeme s prvkem na pozici i a i+1.

static void BubbleSort1 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=npole.length-1;i>0;i--)   //vnejsi smycka
        {
            for(j=0;j<i;j++)   //vnitrni smycka
            {
                if (npole[j]>npole[j+1])    // prohodime prvky?
                {
                    pom = npole[j];
                    npole[j]=npole[j+1];
                    npole[j+1]=pom;
                }
            }
        }
 
   }

V poli se posunuje nejmenší prvek na jeho začátek, při opakování zkracujeme průchod polem odpředu. Pracujeme s prvkem na pozici i a i+1.

static void BubbleSort2 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=0;i<npole.length-1;i++)   //vnejsi smycka
        {
            for(j=npole.length-2;j>=i;j--)   //vnitrni smycka
            {
                if (npole[j]>npole[j+1])    // prohodime prvky?
                {
                    pom = npole[j];
                    npole[j]=npole[j+1];
                    npole[j+1]=pom;
                }
            }
        }
    }

V poli se posunuje nejmenší prvek na jeho začátek, při opakování zkracujeme průchod polem odpředu. Pracujeme s prvkem na pozici i-1 a i.

static void BubbleSort3 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=0;i<npole.length-1;i++)   //vnejsi smycka
        {
            for(j=npole.length-1;j>i;j--)   //vnitrni smycka
            {
                if (npole[j-1]>npole[j])    // prohodime prvky?
                {
                    pom = npole[j-1];
                    npole[j-1]=npole[j];
                    npole[j]=pom;
                }
            }
        }
    }

package trideni;
 
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 - nejvetsi nakonec");
        BubbleSort1(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
        System.out.println();
        System.out.println("Trideni - nejmensi na zacatek, varianta 1 ");
        pole = {4,3,2,1};
        BubbleSort2(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
        System.out.println();
        System.out.println("Trideni - nejmensi na zacatek, varianta 2 ");
        pole = {4,3,2,1};
        BubbleSort3(pole);
        for (index=0;index<pole.length;index++)
        {
            System.out.print(pole[index]+" ");
        }
 
    }
    static void BubbleSort1 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=npole.length-1;i>0;i--)   //vnejsi smycka
        {
            for(j=0;j<i;j++)   //vnitrni smycka
            {
                if (npole[j]>npole[j+1])    // prohodime prvky?
                {
                    pom = npole[j];
                    npole[j]=npole[j+1];
                    npole[j+1]=pom;
                }
            }
        }
    }
 
    static void BubbleSort2 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=0;i<npole.length-1;i++)   //vnejsi smycka
        {
            for(j=npole.length-2;j>=i;j--)   //vnitrni smycka
            {
                if (npole[j]>npole[j+1])    // prohodime prvky?
                {
                    pom = npole[j];
                    npole[j]=npole[j+1];
                    npole[j+1]=pom;
                }
            }
        }
    }
    static void BubbleSort3 (int[] npole)
    {
        int i;                  //pocet opakovani probublavani
        int j;                  //index v poli
        int pom;                //pomocna promenna pro vymenu
 
        for(i=0;i<npole.length-1;i++)   //vnejsi smycka
        {
            for(j=npole.length-1;j>i;j--)   //vnitrni smycka
            {
                if (npole[j-1]>npole[j])    // prohodime prvky?
                {
                    pom = npole[j-1];
                    npole[j-1]=npole[j];
                    npole[j]=pom;
                }
            }
        }
    }
}