email tisk

2008-01-25 15:03:38 | zobrazeno: 9697x
Ukázka řazení metodou Bubble sort.

Bubble sort (v překladu bublinkové řazení, též řazení záměnou) je implementačně jednoduchý řadicí algoritmus. Algoritmus opakovaně prochází seznam, přičemž porovnává každé dva sousedící prvky. Pokud nejsou ve správném pořadí, prohodí je. Porovnávání prvků běží do té doby, dokud není seznam seřazený. Pro praktické účely je neefektivní, využívá se hlavně pro výukové účely a pro řazení kratších posloupností.

Algoritmus je stabilní a univerzální. Patří mezi přirozené řadicí algoritmy (částečně seřazený seznam zpracuje rychleji než neseřazený).

Název vyjadřuje průběh zpracování řady. Při řazení vzestupně prvky s vyšší hodnotou „probublávají“ na konec seznamu.

Začátek programu:


import java.io.*;

public class bubblesort2{
	public static int PocetVymen;

Nejdříve se musí zjistit počet řazených prvků a vytvořit pole dané velikosti:


public static void main(String args[]){
     int[] rada;
     int i,j,n,pom;
     boolean nalezeno;
		
     System.out.print("\n\n\tZadej pocet prvku rady:\t");
     n=ctiInt();
     rada = new int[n];

Nyní můžeme v cyklu zadávat jednotlivé hodnoty pole, nebo můžeme použít generátor náhodné řady. Volání Rady.nesetridena(rada,10); zajistí napojení na třídu Rady a požádá o vygenerování nesetříděné řady velikosti 10. Vybenerované pole uloží pro proměnné rada.

Vygenerování náhodné řady a její vypsání do konzole.


Rady.nesetridena(rada,10);
		
System.out.println("\n\tProgram bude radit nasledujici radu
pomoci algoritmu Bubble Sort.");
for(i=0; i < rada.length; i++)
	System.out.print(" "+rada[i]+"\t");
System.out.println("\n\n");

Nyní musíme seřadit data metodou Bubble sort. V základním řešení používáme dva vnořené cykly for. Složitost pro seřazení této posloupnosti je však O(n2).

Pokud však vnější cyklus bude do-while, tak v momentě, kdy něco prohodím, mohu začít opět od začátku a nemusím procházet až do konce řady. Tímto postupem si ušetříme poměrně hodně práce u posloupností, které jsou jen částečně seřazené. Případně u posloupností, které obsahují jen drobné chyby v přehození dvou sousedních čísel.

Vylepšené řazení metodou Bubble sort:


nalezeno=false;

// vlastni vylepsene razeni Bubble sort
do{
     for(i=0;irada[i])
        {
		pom=rada[i-1];
		rada[i-1]=rada[i];
		rada[i]=pom;
		PocetVymen++;
	}		
     }					
}while(nalezeno);	

NEBO


nalezeno=false;

// zakladni verze razeni Bubble sort
for(i=0;ii;j--)
    {	
          if(rada[j-1]>rada[j])
          {
              pom=rada[j-1];
              rada[j-1]=rada[j];
              rada[j]=pom;
              PocetVymen++;
	  }		
     }
}

Nyní už jen vypíšeme seřazenou řadu a počet záměn dvou prvků.


System.out.println("\n\tSerazena rada je:");

for(i=0; i < rada.length; i++)
    System.out.print(" "+rada[i]+"\t");
		
System.out.println("\n\tPocet vymen pri razeni je:"+PocetVymen);	
	} // od main	
} // od class