Video: Quick Sort (Hızlı Sıralama Algoritması) Veri Yapıları 13 2025
Burada, Java'da en çok kullanılan sıralama tekniklerinden birinin nasıl çalıştığını bulacaksınız. Bu teknik, Quicksort, olarak adlandırılır ve özyinelemenin çok zekice bir kullanımıdır.
Çoğumuz için, Quicksort çalışması gibi sıralama algoritmalarının yalnızca entelektüel bir alıştırma olduğunu bulmak. Java API zaten yerleşik sıralamaya sahiptir.
Quicksort tekniği özyineleme kullanarak bir dizi değer sıralar. Temel adımları şu şekildedir:
-
Dizideki değer aralığı içinde bulunan keyfi bir değeri seçin.
Bu değer pivot noktası 'dır. Pivot noktasını seçmenin en yaygın yolu, dizideki ilk değeri seçmektir. Milletvekilleri, daha hızlı sıralama için pivot noktası seçmek için daha sofistike yollarla doktora derecesi yazmışlardır. Dizideki ilk öğeyi kullanarak yapışın.
-
Pivot noktasından daha küçük olan tüm değerlerin dizinin sol tarafında bulunması ve pivot noktasına eşit veya daha büyük olan tüm değerlerin sağ tarafında olacağı şekilde dizideki değerleri yeniden düzenleyin. dizi.
pivot değeri , dizinin sol ve sağ kenarı arasındaki sınırı belirtir. Muhtemelen ölü bir yer olmayacak, fakat bu önemli değil. Bu adıma bölümlendirme, ve dizilerin sol ve sağ tarafları bölümleri olarak adlandırılır.
-
Şimdi, dizinin iki bölümünün her birini ayrı bir dizi olarak ele alalım ve o bölüm için 1. Adımdan başlayın.
Bu, algoritmanın ardışık kısmıdır.
Quicksort algoritmasının en zor kısmı, pivot noktasından daha küçük olan tüm değerlerin soldaki ve pivot noktasından daha büyük olan tüm öğelerin bulunması için bölümün yeniden düzenlenmesi gereken bölümleme adımdır. nokta sağ tarafta. Dizinin şu on değeri olduğunu varsayalım:
38 17 58 22 69 31 88 28 86 12
Burada pivot noktası 38'dir ve bölme adımının görevi, diziyi şu şekilde yeniden düzenlemektir: < 17 12 22 28 31 38 88 69 86 58
Değerlerin hala bozulduğuna dikkat edin. Ancak dizi 38 değerine bölünmüştür: 38'den küçük olan tüm değerler 38'in solundadır ve 38'den büyük olan tüm değerler 38'in sağındadır.
Şimdi bölünebilir dizisini 38 değerinde iki bölüme yerleştirin ve işlemi her iki taraf için tekrarlayın. Pivot değerinin kendisi sol bölme ile birlikte gider, bu nedenle sol bölüm şu şekildedir:
17 12 22 28 31 38
Bu sefer bölme basamağı pivot noktası olarak 17'yi seçer ve elemanları aşağıdaki gibi düzenler: > 12 17 22 28 31 38
Gördüğünüz gibi, dizinin bu kısmı şimdi sıralanmıştır.Maalesef, Quicksort bu noktada bunu bilmiyor, bu nedenle emin olmak için birkaç tekrarlama daha gerekiyor. Fakat temel süreç budur.
