Menü

Java'da QuickSort - Algoritma, İllüstrasyon ve Uygulama

  • Ana
  • Diğer
  • Java'da QuickSort - Algoritma, İllüstrasyon ve Uygulama

quicksort java algorithm

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Bu Öğretici, Java'daki Quicksort Algoritmasını, resimlerini, Java'da QuickSort Uygulamasını Kod Örnekleri yardımıyla Açıklar:

Quicksort sıralama tekniği, yazılım uygulamalarında yaygın olarak kullanılmaktadır. Quicksort, birleştirme sıralaması gibi bir böl ve yönet stratejisi kullanır.

Hızlı sıralama algoritmasında, ilk olarak 'pivot' adlı özel bir öğe seçilir ve söz konusu dizi veya liste iki alt gruba bölünür. Bölümlendirilmiş alt kümelerin boyutu eşit olabilir veya olmayabilir.

=> Kolay Java Eğitim Serisini Okuyun.

Java

Bölmeler, pivot öğesinden daha küçük tüm öğeler pivotun soluna doğru olacak ve pivottan daha büyük öğeler pivotun sağında olacak şekildedir. Quicksort rutini, iki alt listeyi yinelemeli olarak sıralar. Quicksort, daha büyük diziler veya listeler için bile verimli ve daha hızlı çalışır.

Ne öğreneceksin:

Quicksort Partition Java

Bölümleme, Quicksort tekniğinin temel sürecidir. Öyleyse bölümleme nedir?

Bir dizi A verildiğinde, pivot adında bir x değeri seçeriz, öyle ki x'ten küçük olan tüm elemanlar x'ten önce ve x'ten büyük tüm elemanlar x'ten sonra olur.

Bir pivot değeri aşağıdakilerden herhangi biri olabilir:

  • Dizideki ilk öğe
  • Dizideki son öğe
  • Dizideki orta eleman
  • Dizideki herhangi bir rastgele öğe

Bu pivot değeri daha sonra dizi bölümlenerek dizideki uygun konumuna yerleştirilir. Dolayısıyla, 'bölümleme' sürecinin çıktısı, uygun pozisyonundaki pivot değeridir ve solda pivot'tan küçük olan öğeler ve sağdaki pivottan büyük öğelerdir.

Bölümleme sürecini açıklayan aşağıdaki diyagramı düşünün.

bölümleme süreci

Yukarıdaki diyagram, dizideki son öğeyi bir pivot olarak tekrar tekrar seçerek diziyi bölümleme sürecini göstermektedir. Her seviyede, pivotu doğru konumuna yerleştirerek diziyi iki alt diziye böldüğümüze dikkat edin.

Daha sonra, bölümleme rutinini de içeren hızlı sıralama tekniği için algoritmayı ve sözde kodu listeliyoruz.

.dat dosyası nasıl açılır

Quicksort Algorithm Java

Hızlı sıralama için genel algoritma aşağıda verilmiştir.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Aşağıda, hızlı sıralama tekniği için sözde kod verilmiştir.

Hızlı Sıralama İçin Sözde Kod

Aşağıda, hızlı sıralama sıralama tekniği için sözde kod verilmiştir. Hızlı sıralama ve bölümleme rutini için sözde kod sağladığımızı unutmayın.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

İllüstrasyon

Hızlı sıralama algoritmasının resmine bakalım. Aşağıdaki diziyi örnek olarak alalım. Burada son elemanı pivot olarak seçtik.

Gösterildiği gibi, ilk öğe düşük olarak etiketlenir ve son öğe yüksektir.

Quicksort algoritmasının çizimi

Yukarıdaki çizimde açıkça görüldüğü gibi, sırasıyla dizinin son ve ilk elemanlarına işaret eden yüksek ve düşük iki işaretçi vardır. Hızlı sıralama ilerledikçe bu işaretçilerin her ikisi de taşınır.

Düşük işaretçinin işaret ettiği öğe pivot öğesinden daha büyük hale geldiğinde ve yüksek işaretçinin gösterdiği öğe pivot öğesinden daha küçük olduğunda, düşük ve yüksek işaretçinin gösterdiği öğeleri değiştiririz ve her işaretçi 1 konum ilerler.

Yukarıdaki adımlar, her iki işaretçi dizide birbiriyle kesişene kadar gerçekleştirilir. Pivot öğesi bir kez kesiştiğinde, dizideki uygun konumunu alır. Bu noktada, dizi bölümlenir ve şimdi her bir alt diziyi, alt dizilerin her birine özyinelemeli bir hızlı sıralama algoritması uygulayarak bağımsız olarak sıralayabiliriz.

Java'da Quicksort Uygulaması

QuickSort tekniği Java'da özyineleme veya yineleme kullanılarak uygulanabilir. Bu bölümde, bu iki tekniği de göreceğiz.

Yinelemeli Hızlı Sıralama

Yukarıda gösterilen temel hızlı sıralama tekniğinin diziyi sıralamak için özyinelemeyi kullandığını biliyoruz. Dizi bölümlendikten sonra özyinelemeli hızlı sıralamada, alt dizileri sıralamak için hızlı sıralama yordamı özyinelemeli olarak adlandırılır.

Aşağıdaki Uygulama, özyinelemeyi kullanan hızlı sıralama tekniğini göstermektedir.

import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Çıktı:

Orijinal Dizi: (4, -1, 6, 8, 0, 5, -3)
Sıralanmış Dizi: (-3, -1, 0, 4, 5, 6, 8)

Yinelemeli hızlı sıralama - çıktı

Yinelemeli Hızlı Sıralama

Yinelemeli hızlı sıralamada, özyineleme ve sıralama bölümleri kullanmak yerine ara parametreleri yerleştirmek için yardımcı yığını kullanırız.

Aşağıdaki Java programı yinelemeli hızlı sıralama uygular.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Çıktı:

Orijinal Dizi: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Sıralanmış Dizi: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Yinelemeli hızlı sıralama - çıktı

Sıkça Sorulan Sorular

S # 1) Quicksort nasıl çalışır?

Cevap: Quicksort bir bölme ve fethetme stratejisi kullanır. Hızlı sıralama ilk olarak, seçilen bir pivot öğesi etrafında bir diziyi bölümler ve özyinelemeli olarak sıralanan alt diziler oluşturur.

S # 2) Quicksort'un zaman karmaşıklığı nedir?

Cevap: Quicksort'un ortalama zaman karmaşıklığı O (nlogn). En kötü durumda, seçim sıralaması ile aynı O (n ^ 2) 'dir.

S # 3) Quicksort nerede kullanılır?

Cevap: Quicksort, çoğunlukla yinelemeli uygulamalarda kullanılır. Quicksort, C kütüphanesinin bir parçasıdır. Ayrıca, yerleşik sıralama kullanan neredeyse programlama dilleri hızlı sıralama uygular.

S # 4) Quicksort'un avantajı nedir?

Cevap:

  • Quicksort, verimli bir algoritmadır ve çok büyük bir öğe listesini bile kolayca sıralayabilir.
  • Yerinde sıralanır ve bu nedenle fazladan alana veya belleğe ihtiyaç duymaz.
  • Yaygın olarak kullanılır ve herhangi bir uzunluktaki veri kümelerini sıralamak için verimli bir yol sağlar.

S # 5) Quicksort neden birleştirme sıralamasından daha iyi?

Cevap: Hızlı sıralamanın birleştirme sıralamasından daha iyi olmasının ana nedeni, hızlı sıralamanın yerinde sıralama yöntemi olması ve ek bellek alanı gerektirmemesidir. Birleştirme sıralaması, ara sıralama için ek bellek gerektirir.

Sonuç

Quicksort, esasen O (nlogn) zamanında çok büyük bir veri kümesini bile sıralama etkinliği nedeniyle en iyi sıralama algoritması olarak kabul edilir.

Quicksort ayrıca yerinde bir sıralamadır ve ek bellek alanı gerektirmez. Bu eğitimde, quicksort'un özyinelemeli ve yinelemeli uygulamasını gördük.

Yaklaşan eğitimimizde, Java'da sıralama yöntemlerine devam edeceğiz.

=> Java Yeni Başlayanlar Kılavuzuna Bir Göz Atın.

Önerilen Kaynaklar

^