Sortowanie szybkie - QuickSort

Sortowanie szybkie działa na zasadzie podziału tablicy na dwie części. Jedna z nich zawiera elementy o wartościach mniejszych, a druga elementy o wartościach większych od wartości elementu dzielącego (ang. pivot). Jako element dzielący można wybrać element środkowy, element pierwszy lub element ostatni. Każda z części tak podzielonej tablicy jest poddawana od nowa algorytmowi sortowania szybkiego.

pokaż źródło

drukujpomoc

01./**

02. * Sortowanie szybkie - QuickSort

03. * @author kodatnik.blogspot.com

04. */

05.public class SortowanieSzybkie {

06. // metoda zamienia miejscami elementy o indeksach i oraz j

07. // w tablicy przekazanej jako parametr

08. private static void zamien(int[] wejscie, int i, int j) {

09.  int temp = wejscie[i];

10.  wejscie[i] = wejscie[j];

11.  wejscie[j] = temp;

12. } 

13.  

14. // metoda dzieli tablicę (od indeksu p do indeksu k) na dwie części

15. // - elementy mniejsze od wybranego elementu

16. // - elementy większe od wybranego elementu

17. private static int podzial(int[] wejscie, int p, int k) {

18.  

19.  // wybieramy element wg którego będziemy dzielić

20.  // np. element ostatni

21.  int element = wejscie[k];

22.   

23.  // ustalamy zakres na którym będziemy operować

24.  int i = p;

25.  int j = k - 1;

26.   

27.  // pętla wyszukuje kolejne elementy większe i mniejsze od

28.  // elementu dzielącego (zmienna element)

29.  while(i <= j) {

30.   while (wejscie[i] <= element && i < k) i++;

31.   while (wejscie[j] > element && j > p) j--;

32.    

33.   // jeśli elementy są na niewłaściwych pozycjach zamieniamy je

34.   if (i < j) zamien(wejscie, i, j);

35.   // jeśli indeksy się zrównają kończymy pętlę

36.   if (i == j) break;

37.  }

38.    

39.  // na końcu wstawiamy element dzielący na właściwą pozycję

40.  zamien(wejscie, i, k);

41.     

42.  // i zwracamy tę pozycję

43.  return i;

44. }

45.  

46. // metoda sortuje elementy tablicy przekazanej jako parametr

47. // dodatkowo w jej wywołaniu podajemy indeks pierwszego i ostatniego elementu

48. public static void sortowanieSzybkie(int[] wejscie, int i, int j) {

49. 

50.  // jeśli indeksy są równe lub niepoprawne zakończ działanie

51.  if ( j <= i ) return;

52. 

53.  // dzielimy tablicę na części, indeks miejsca podziału zapisujemy w zmiennej os (oś)

54.  int os = podzial(wejscie, i, j);

55.   

56.  // rekurencyjnie dokonujemy posortowania lewej i prawej części naszej tablicy

57.  sortowanieSzybkie(wejscie, i, os-1);

58.  sortowanieSzybkie(wejscie, os+1, j); 

59. }  

60.  

61. // metoda wyświetla zawartość tablicy przekazanej jako parametr na ekranie

62. public static void pokazTablice(int[] wejscie) {

63.  // każdy element znajdujący się w tablicy wyświetlamy na ekranie

64.  for(int x : wejscie) System.out.print (x + " ");

65.  System.out.println ();

66. }

67. 

68. public static void main(String[] args) {

69.  // tworzymy tablicę wypełniając ją od razu danymi

70.  int[] tablica = {4, 6, 1, 2, 3, 8, 7, 9, 5};

71.   

72.  // wyświetlamy tablicę na ekranie

73.  pokazTablice(tablica);

74.  // sortujemy tablicę

75.  sortowanieSzybkie(tablica, 0, tablica.length-1);

76.  // wyświetlamy posortowaną tablicę na ekranie

77.  pokazTablice(tablica); 

78. }

79.}

Optymalizacja algorytmu polega na właściwym doborze elementu dzielącego. Najczęściej dokonuje się tego poprzez jego losowy wybór, bądź też wyznaczenie mediany z rozpatrywanych elementów.

Uruchomiona aplikacja:

4 6 1 2 3 8 7 9 5 
1 2 3 4 5 6 7 8 9