Oferty pracy dla inżynierów
  • STREFA INŻYNIERA (current)
  • Oferty pracy
  • Metale
    • Obróbka metali
    • CAD
    • CATIA
    • Autodesk Inventor
  • Automatyka
    • Uprawnienia elektryczne SEP
    • Elektrotechnika
    • Elektronika
    • Automatyka
    • Robotyka
  • Przemysł
    • Przemysł
    • Obróbka metali
  • IT
    • JAVA
    • C++
    • Sieci
  • Publikacje
  • Firmy
  • Dla firm
    • Rejestracja - profil firmy
    • Dodaj ofertę pracy - bezpłatnie
    • Publikacja artykułów
    • Kontakt
  • Zaloguj się
  • STREFA INŻYNIERA
  • Oferty pracy
  • Metale
    • CAD
    • CATIA
    • Autodesk Inventor
  • IT
    • JAVA
    • C++
    • Sieci
  • Automatyka
    • Uprawnienia elektryczne SEP
    • Elektrotechnika
    • Elektroniki
    • Automatyki
    • Robotyka
  • Przemysł
    • Przemysł
    • Obróbka metali
  • Publikacje
  • Firmy
  • Dla firm
    • Rejestracja - profil firmy
    • Dodaj ofertę pracy - bezpłatnie
    • Publikacja artykułów
    • Kontakt
  • Logowanie
  • Zaloguj się
Algorytm Quicksort w JAVA
Categories

Algorytm Quicksort w JAVA

W tym przykładzie zaimplementujemy wersję jednego z najlepszych algorytmów: Quicksort. Twórcą algorytmu i jego nazwy jest C.A.R. Hoare. Quicksort jest obecnie najlepszym z dostępnych uniwersalnych algorytmów sortowania. Nie mogłem jednak przedstawić go w rozdziale 5., ponieważ najlepsze jego implementacje wykorzystują rekurencję. Wersja, którą zaimplementujemy w tym rozdziale, będzie sortować tablicę znaków, ale tę samą logikę możesz zastosować dla dowolnych obiektów.

Algorytm Quicksort bazuje na idei podziału. Ogólna procedura polega na wybraniu pewnej wartości, a następnie podziale tablicy na dwie części. W jednej umieszczamy elementy, których wartość jest równa bądź większa od wybranej wartości, a w drugiej te, których wartość jest mniejsza. Proces ten powtarzamy dla każdej części tablicy, aż uzyskamy całkowicie posortowaną tablicę. Na przykład dla tablicy fedacb możemy wybrać wartość d, wtedy wynikiem pierwszego przebiegu algorytmu Quicksort będzie tablica bcadef.

Zawartość początkowa f e d a c b
Pierwszy przebieg b c a d e f

Następnie powtarzamy proces dla każdej części tabeli, czyli dla bca i def. Jak łatwo zauważyć, proces ten jest z natury rekurencyjny i rzeczywiście najlepsza jego implementacja wykorzystuje rekurencję.

Wartość, z którą porównujemy pozostałe elementy tablicy, możemy wybrać na dwa sposoby. Albo w sposób losowy, albo jako średnią z pewnego podzbioru wartości tablicy. Optymalne działanie algorytmu wymaga wybrania wartości znajdującej się dokładnie pośrodku zakresu. Jednak dokonanie takiego wyboru nie jest łatwe dla większości sortowanych zbiorów danych. W najgorszym przypadku musimy liczyć się z wyborem wartości będącej ekstremum sortowanego zbioru. Jednak nawet w takim przypadku algorytm Quicksort nadal działa poprawnie. W naszej wersji algorytmu Quicksort będziemy wybierać element leżący pośrodku tabeli.

1. Utwórz plik o nazwie QSDemo.java.
2. Najpierw utwórz klasę Quicksort pokazaną poniżej:

// Prosta wersja algorytmu Quicksort.
class Quicksort {
  // Konfiguruje wywołanie właściwej metody algorytmu Quicksort.
  static void qsort(char items[]) {
    qs(items, 0, items.length-1);
  }
  // Rekurencyjna wersja Quicksort sortująca tablicę znaków.
  private static void qs(char items[], int left, int right)
  {
    int i, j;
    char x, y;
    i = left; j = right;
    x = items[(left+right)/2];
    do {
      while((items[i] < x) && (i < right)) i++;
      while((x < items[j]) && (j > left)) j--;
      if(i <= j) {
        y = items[i];
        items[i] = items[j];
        items[j] = y;
        i++; j--;
      }
    } while(i <= j);
    if(left < j) qs(items, left, j);
    if(i < right) qs(items, i, right);
  }
}

Aby uprościć interfejs, klasa Quicksort dostarcza metodę qsort(), która konfiguruje wywołanie metody qs() stanowiącej właściwą implementację algorytmu. Dzięki temu można wywołać algorytm, dostarczając jedynie nazwy tablicy do posortowania bez konieczności wstępnego jej podziału na części. Ponieważ metoda qs() jest używana tylko wewnątrz klasy Quicksort,
została zadeklarowana jako private.

3. Aby wykonać sortowanie, wystarczy wywołać metodę Quicksort.qsort(). Ponieważ została ona zadeklarowana jako static, to wywołujemy ją z nazwą klasy. Zwróć więc uwagę, że użycie algorytmu sortowania nie wymaga utworzenia obiektu klasy Quicksort. Po wywołaniu metody qsort() tablica zostanie posortowana. Ta wersja algorytmu sortuje jedynie tablice znaków, ale możesz zaadaptować ją dla tablic dowolnego typu.

4. Na listingu 6.20 przedstawiłem program demonstrujący użycie algorytmu Quicksort.

Listing 6.20. QSDemo.java

// Prosta wersja algorytmu Quicksort.
class Quicksort {
  // Konfiguruje wywołanie właściwej metody algorytmu Quicksort.
  static void qsort(char items[]) {
    qs(items, 0, items.length-1);
  }
  // Rekurencyjna wersja Quicksort sortująca tablicę znaków.
  private static void qs(char items[], int left, int right)
  {
    int i, j;
    char x, y;
    i = left; j = right;
    x = items[(left+right)/2];
    do {
      while((items[i] < x) && (i < right)) i++;
      while((x < items[j]) && (j > left)) j--;
      if(i <= j) {
        y = items[i];
        items[i] = items[j];
        items[j] = y;
        i++; j--;
      }
   } while(i <= j);
   if(left < j) qs(items, left, j);
   if(i < right) qs(items, i, right);
  }
}
class QSDemo {
  public static void main(String args[]) {
    char a[] = { 'd', 'x', 'a', 'r', 'p', 'j', 'i' };
    int i;
    System.out.print("Tablica przed posortowaniem: ");
    for(i=0; i < a.length; i++)
      System.out.print(a[i]);
    System.out.println();
    // sortuje tablicę
    Quicksort.qsort(a);
    System.out.print("Tablica posortowana: ");
    for(i=0; i < a.length; i++)
    System.out.print(a[i]);
  }
}

Java. Przewodnik dla początkujących. Wydanie VI, Autor: Herbert Schildt, Wydawnictwo: Helion
Zaloguj się aby dodać komentarz

Podobne artykuły

« Przesłanianie metodSłowo kluczowe static »

Podziel się ze znajomymi tym artykułem - udostępnij na FB lub wyślij e-maila korzystając z poniższych opcji:

MARS
Angielski techniczny
Oferty pracy dla inżynierów

SERWISANT - inżynier - zabezpieczenia techniczne

Gunnebo Polska Sp. z o.o.
Kalisz, dowolny Region
5000-10000 PLN

Pracownik działu wsparcia systemów Comarch ERP XL

GRH Polska
Rzeszów, podkarpackie

Monter maszyn

Zatoka-Tech Sp. z o.o.
Łebcz, pomorskie
3000 - 4000 PLN

Operator instalacji rafineryjnych

Grupa Lotos S.A.
Gdańsk, pomorskie
4300 PLN brutto na start

Automatyk w dziale Utrzymania Ruchu

Tarczyński S.A.
Ujeździec Mały, dolnośląskie

Programista IT Fullstack Developer

Zatoka-Tech Sp. z o.o.
Łebcz, pomorskie
3650 - 5550 PLN

wszystkie oferty
Praca dla inżyniera - grupa na FB

Dołącz do grupy i otrzymuj powiadomienia o nowych ofertach pracy


Mapa ofert pracy dla inżynierów

Strefainzyniera.pl - rynek, praca, rozwój - wszystko co ważne dla inżynierów

  • Dla pracodawcy
  • Artykuły
  • Praca
  • Popularne stanowiska
  • Offer in English
  • Regulamin
  • Regulamin dla klientów
  • Polityka prywatności
  • Polityka cookies
  • Kontakt

© 2011-2019 NetPortal

Mapa strony Domokonkret