Java'da Hızlı Sıralama Açıklaması

Yarılanma Sözleşmesi

Bir listedeki öğelerin sayısı çift olduğunda, listeyi ikiye bölmek, listenin gerçek ilk yarısının ilk yarısı olduğu ve listenin tam anlamıyla ikinci yarısının ikinci yarısı olduğu anlamına gelir. Tüm listenin orta (orta) öğesi, ilk listenin son öğesidir. Bu, indeks sayımı sıfırdan başladığı için orta indeksin uzunluk / 2 – 1 olduğu anlamına gelir. Uzunluk, listedeki öğelerin sayısıdır. Örneğin, eleman sayısı 8 ise, listenin ilk yarısında 4 eleman, listenin ikinci yarısında da 4 eleman vardır. Bu iyi. İndeks sayımı 0'dan başladığı için ortadaki indeks 3 = 8 / 2 – 1'dir.

Listedeki veya alt listedeki öğelerin sayısı tek olduğunda durum ne olacak? Başlangıçta uzunluk hala 2'ye bölünmüştür. Geleneksel olarak, bu bölümün ilk yarısındaki eleman sayısı uzunluk / 2 + 1/2'dir. Endeks sayımı sıfırdan başlar. Orta indeks uzunluk / 2 – 1/2 olarak verilir. Bu, konvansiyonel olarak orta terim olarak kabul edilir. Örneğin, bir listedeki eleman sayısı 5 ise, ortadaki indeks 2 = 5/2 – 1/2'dir. Ve listenin ilk yarısında üç, ikinci yarısında iki unsur var. Tüm listenin orta öğesi, dizin sayımı 0'dan başladığı için orta dizin olan dizin 2'deki üçüncü öğedir.

Bu şekilde bölme, tamsayı aritmetiğine bir örnektir.

Üç Değerin Ortancası

Soru: Dizinin medyanı nedir:

CBA

Çözüm:
Listeyi artan sırada düzenleyin:

bir B C

Orta terim, B, medyandır. Diğer iki büyüklük arasında kalan büyüklüktür.

Bir listede medyan aramak o tür değil. Örneğin, sıralanmamış 19 öğeden oluşan bir listede, ilk öğe, orta öğe ve son öğe için medyan gerekli olabilir. Bu üç değer artan sırada olmayabilir; ve bu nedenle, endeksleri dikkate alınmalıdır.

Hızlı Sıralama ile tüm liste ve alt listeler için medyan gereklidir. Bir listede (dizi) aralıklı üç değerin medyanını aramak için sözde kod:

Arr terimi dizi anlamına gelir. Bu kod segmenti medyanı arar ve ayrıca bazı sıralamalar yapar. Bu kod bölümü basit görünüyor, ancak oldukça kafa karıştırıcı olabilir. Bu nedenle, aşağıdaki açıklamaya dikkat edin:

Bu öğreticideki sıralama, ilk değerin en küçük değer olduğu ve son değerin en büyük değer olduğu bir liste üretecektir. Alfabe ile A, Z'den küçüktür.

Burada pivot, elde edilen medyandır. Düşük, listenin veya alt listenin en düşük indeksidir (en düşük değer için olması gerekmez); yüksek, listenin veya alt listenin en yüksek endeksidir (en yüksek değer için zorunlu değildir) ve orta, geleneksel orta dizindir (tüm listenin orta değeri için zorunlu değildir).

Yani elde edilecek medyan, en düşük indeks değeri, orta indeks değeri ve en yüksek indeks değeri arasındadır.

Kodda, önce geleneksel orta dizin elde edilir. Bu başlangıçta, liste sıralanmamıştır. Üç değerin artan düzeninde karşılaştırma ve bazı yeniden düzenlemeler aynı anda gerçekleşecektir. İlk if ifadesi, en düşük indeks ile orta indeksin değerini karşılaştırır. Orta endeksinki en düşük endeksinkinden küçükse, o zaman iki değer pozisyon değiştirir. Bu, sıralamaya başlar ve listedeki veya alt listedeki değerlerin düzenini değiştirir. İkinci if-ifadesi, en yüksek indeksin değerini ve en düşük indeksin değerini karşılaştırır. En yüksek endeksin değeri en düşük endeksinkinden küçükse, iki değer pozisyon değiştirir. Bu, listedeki veya alt listedeki değerlerin düzeninin bazı sıralamasını ve değiştirilmesini sağlar. Üçüncü if-ifadesi, orta indeksin değerini ve en yüksek indeksin değerini karşılaştırır. En yüksek endeksin değeri ortadaki endeksten küçükse, iki değer pozisyon değiştirir. Bazı sıralama veya yeniden düzenleme burada da meydana gelebilir. Bu üçüncü if-koşulu önceki ikisine benzemez.

Bu üç takasın sonunda, söz konusu üç değerin orta değeri, orijinal içeriği kod segmentinde değiştirilmiş olabilecek A[yüksek] olacaktır. Örneğin, sıralanmamış diziyi düşünün:

CBA

Medyanın B olduğunu zaten biliyoruz. Ancak bunun kanıtlanması gerekiyor. Buradaki amaç, yukarıdaki kod segmentini kullanarak bu üç değerin medyanını elde etmektir. İlk if ifadesi B ve C'yi karşılaştırır. B, C'den küçükse, B ve C'nin konumları değiştirilmelidir. B, C'den küçüktür, dolayısıyla yeni düzenleme şöyle olur:

BCA

Dikkat edin, en düşük dizin ve orta dizin için değerler değişmiştir. İkinci if ifadesi A ve B'yi karşılaştırır. A, B'den küçükse, A ve B'nin konumları değiştirilmelidir. A, B'den küçüktür, dolayısıyla yeni düzenleme şöyle olur:

bir C B

Dikkat edin, en yüksek dizin ve en düşük dizin değerleri değişmiştir. Üçüncü if-ifadesi C ve B'yi karşılaştırır. Eğer C, B'den küçükse, o zaman C ve B'nin konumları değiştirilmelidir. C, B'den küçük değildir, dolayısıyla takas gerçekleşmez. Yeni düzenleme öncekiyle aynı kalır, yani:

bir C B

B medyandır, yani A[yüksek] ve pivottur. Böylece pivot, listenin veya alt listenin en sonunda doğar.

Değiştirme İşlevi

Hızlı Sıralama'nın ihtiyaç duyduğu bir diğer özellik de takas işlevidir. Takas işlevi, iki değişkenin değerlerini değiştirir. Değiştirme işlevinin sözde kodu:

Burada x ve y, kopyaları değil gerçek değerleri ifade eder.

Bu makaledeki sıralama, ilk değerin en küçük değer olduğu ve son değerin en büyük değer olduğu bir liste üretecektir.

Makale İçeriği

• Hızlı Sıralama Algoritması
• Bir Bölüm Sözde Kodu
• Hızlı Sıralamanın Resmi
• Java Kodlama
• Çözüm

Hızlı Sıralama Algoritması

Sıralanmamış bir listeyi sıralamanın normal yolu, ilk iki değeri dikkate almaktır. Sıralı değillerse, sıraya koyun. Ardından, ilk üç değeri göz önünde bulundurun. Üçüncü değerin nereye uyduğunu ve uygun şekilde sığdırdığını görmek için ilk ikisini tarayın. Ardından, ilk dört değeri göz önünde bulundurun. Dördüncü değerin nereye uyduğunu ve uygun şekilde sığdırdığını görmek için ilk üç değeri tarayın. Tüm liste sıralanana kadar bu prosedüre devam edin.

Bilgisayar programlama dilinde kaba kuvvet sıralaması olarak da bilinen bu prosedür çok yavaştır. Hızlı Sıralama algoritması çok daha hızlı bir prosedürle gelir.

Hızlı sıralama algoritmasının adımları aşağıdaki gibidir:

1. Sıralanmamış listede sıralanacak en az 2 sayı olduğundan emin olun.
2. Pivot adı verilen liste için tahmini bir merkezi değer elde edin. Medyan, yukarıda açıklandığı gibi, pivotu elde etmenin bir yoludur. Avantajları ve dezavantajları ile farklı yollar gelir. - Daha sonra bakın.
3. Listeyi bölümlere ayırın. Bu, pivotu listeye yerleştirin. Bu şekilde, soldaki tüm öğeler pivot değerinden küçük, sağdaki tüm öğeler pivot değerinden büyük veya ona eşittir. Bölmenin farklı yolları vardır. Her bölme yöntemi, avantajları ve dezavantajları ile birlikte gelir. Bölümleme, böl ve yönet paradigmasında bölünmektir.
4. Tüm liste sıralanana kadar ortaya çıkan yeni alt liste çiftleri için 1, 2 ve 3. adımları yinelemeli olarak tekrarlayın. Bu, böl ve yönet paradigmasında galip gelmektir.

Hızlı Sıralama sözde kodu:

Bir Bölüm Sözde Kodu

Bu öğreticide kullanılan bölüm sözde kodu:

Aşağıdaki Hızlı Sıralama çiziminde bu kod kullanılmıştır:

Hızlı Sıralamanın Resmi

Aşağıdaki alfabetik harflerin sıralanmamış listesini (dizisini) göz önünde bulundurun:

Q W E R T Y U I O P

İncelemeye göre, sıralanmış liste:

E I O P Q R U W Y

Sıralanan liste şimdi, sıralanmamış listeden yukarıdaki algoritma ve sözde kod segmentleri kullanılarak kanıtlanacaktır:

Q W E R T Y U I O P

İlk pivot arr[0]=Q, arr[4]=T ve arr[9]=P'den belirlenir ve Q olarak tanımlanır ve listenin en sağına yerleştirilir. Böylece, herhangi bir pivot işlevi sıralamasına sahip liste şöyle olur:

P W E R T Y U I O Q

Mevcut pivot Q'dur. Pivot prosedürü bazı küçük sıralamalar yaptı ve P'yi ilk konuma yerleştirdi. Ortaya çıkan liste yeniden düzenlenmeli (bölümlere ayrılmalı), öyle ki soldaki tüm elemanlar değer olarak daha küçük, o zaman pivot ve pivotun sağındaki tüm elemanlar pivota eşit veya ondan daha büyük. Bilgisayar inceleme ile bölümleme yapamaz. Böylece, dizinleri ve yukarıdaki bölüm algoritmasını kullanarak yapar.

Düşük ve yüksek indeksler şimdi 0 ve 9'dur. Böylece bilgisayar, değeri pivota eşit veya ondan daha büyük olan bir indekse ulaşana kadar indeks 0'dan taramaya başlayacak ve geçici olarak orada duracaktır. Ayrıca, değeri pivottan küçük veya ona eşit olan bir dizine ulaşana ve geçici olarak orada durana kadar üst (sağ) uçtan, dizin 9'dan aşağı doğru tarama yapacaktır. Bu, iki durma konumu anlamına gelir. Eğer i, düşükten artımlı indeks değişkeni, yüksekten j, azalan indeks değişkenine eşit veya ondan büyük değilse, bu iki değer değiştirilir. Mevcut durumda, W ve O'da her iki uçtan tarama durduruldu. Böylece liste şöyle olur:

P O E R Y U I W Q

Pivot hala Q'dur. Zıt yönlerde tarama devam eder ve buna göre durur. i henüz j'ye eşit veya ondan büyük değilse, her iki uçtan taramanın durduğu iki değer değiştirilir. Bu sefer, R ve I'de her iki uçtan tarama durduruldu. Böylece, listenin düzeni şöyle olur:

P O E I T Y U R W Q

Pivot hala Q'dur. Zıt yönlerde tarama devam eder ve buna göre durur. i henüz j'ye eşit veya ondan büyük değilse, taramanın durduğu iki değer değiştirilir. Bu sefer, her iki uçtan tarama, i için T'de ve j için I'de durduruldu. i ve j tanıştık veya geçtik. Yani takas söz konusu olamaz. Liste aynı kalır:

P O E I T Y U R W Q

Bu noktada, pivot Q, sıralamadaki son konumuna yerleştirilmelidir. Bu, arr[i]'yi arr[high] ile değiştirerek, T ve Q'yu değiştirerek yapılır. Liste şöyle olur:

P O E I Q Y U R W T

Bu noktada, tüm liste için bölümleme sona erdi. Pivot = Q rolünü oynamıştır. Şimdi üç alt liste var:

P O E I Q Y U R W T

Bölme, paradigmada bölme ve fethetmedir (sıralamadır). Q, doğru sıralama konumunda. Q'nun solundaki her öğe Q'dan küçüktür ve Q'nun sağındaki her öğe Q'dan büyüktür. Ancak soldaki liste hala sıralanmamıştır; ve doğru liste hala sıralanmadı. Sol alt listeyi ve sağ alt listeyi sıralamak için tüm Hızlı Sıralama işlevinin yinelemeli olarak çağrılması gerekir. Bu Hızlı Sıralamanın geri çağrılması devam etmelidir; tüm orijinal liste tamamen sıralanana kadar yeni alt listeler gelişecektir. Hızlı Sıralama işlevinin her geri çağrılması için, ilgili sağ alt listeye katılmadan önce sol alt listeye başvurulur. Her alt liste için yeni bir pivot elde edilmelidir.

Alt liste için:

P O E I

P, O ve I için pivot (medyan) belirlenir. Pivot O olacaktır. Bu alt liste için ve tam listeyle ilgili olarak, yeni dizi[düşük] dizi[0] ve yeni dizi[yüksek] son ​​dizi[i-1] = dizi[ 4-1] = arr[3], burada i önceki bölümün son pivot indeksidir. pivot() işlevi çağrıldıktan sonra, yeni pivot değeri, pivot = O. Pivot işlevi ile pivot değeri arasında karıştırmayın. Pivot işlevi bazı küçük sıralamalar yapabilir ve pivotu alt listenin en sağına yerleştirebilir. Bu alt liste,

ben P E O

Bu şema ile pivot, fonksiyon çağrısından sonra her zaman alt listenin veya listenin sağ ucunda biter. Her iki uçtan tarama, arr[0] ve arr[3] ile başlar, i ve j buluşana veya kesişene kadar. Karşılaştırma pivot = O ile yapılır. İlk duraklar P ve E'dedir. Bunlar değiştirilir ve yeni alt liste şöyle olur:

ben E P O

Her iki uçtan tarama devam eder ve yeni duraklar i için P'de ve j için E'dedir. Şimdi i ve j tanıştık ya da geçtiler. Böylece alt liste aynı kalır:

ben E P O

Bir alt listenin veya listenin bölümlenmesi, pivot son konumuna getirildiğinde sona erer. Böylece arr[i] ve arr[high] için yeni değerler değiştirilir. Yani, P ve O değiştirilir. Yeni alt liste şöyle olur:

ben E O P

O şimdi tüm liste için son konumunda. Pivot rolü sona erdi. Alt liste şu anda üç listeye daha bölünmüştür, bunlar:

ben E O P

Bu noktada ilk sağ alt listenin Hızlı Sıralaması çağrılmalıdır. Ancak çağrılmayacak. Bunun yerine, daha sonra aranmak üzere not edilecek ve rezerve edilecektir. Bölümleme işlevinin ifadeleri yürütülürken, işlevin en üstünden, şimdi çağrılması gereken sol alt liste için Hızlı Sıralamadır (pivot() çağrıldıktan sonra). Liste için çağrılacak:

ben

I ve E'nin medyanını arayarak başlayacaktır. Burada arr[düşük] = I, arr[mid] = I ve arr[yüksek] = E. Dolayısıyla medyan, pivot, pivot algoritması tarafından şu şekilde belirlenmelidir. , I. Ancak, yukarıdaki pivot sözde kodu, pivotu E olarak belirleyecektir. Bu hata, yukarıdaki sözde kodun iki değil üç öğe için olması nedeniyle burada oluşur. Aşağıdaki uygulamada, kodda bazı ayarlamalar vardır. Alt liste olur,

ben

Pivot, işlev çağrısından sonra her zaman alt listenin veya listenin sağ ucunda biter. Her iki uçtan tarama, arr[0] ve arr[1] hariçten başlar, i ve j buluşana veya kesişene kadar. Karşılaştırma pivot = I ile yapılır. İlk ve tek duraklar I ve E'de: i için I'de ve j için E'de. Şimdi ben ve j tanıştık ya da geçtik. Böylece, alt liste şu şekilde kalır:

ben

Bir alt listenin veya listenin bölümlenmesi, pivot son konumuna getirildiğinde sona erer. Böylece arr[i] ve arr[high] için yeni değerler değiştirilir. Burada arr[i] = I ve arr[high] = I olur. Yani aynı değer kendisiyle değiştirilir. Yeni alt liste şöyle olur:

ben

Şimdi tüm liste için son konumundayım. Pivot rolü sona erdi. Alt liste şimdi iki listeye daha bölünmüştür;

ben

Şimdi, pivotlar şimdiye kadar Q, O ve I olmuştur. Pivotlar son konumlarında sona erer. Yukarıdaki P gibi tek bir öğenin alt listesi de son konumunda biter.

Bu noktada, ilk sol alt liste tamamen sıralanmıştır. Ve sıralama prosedürü şu anda:

E I O P Q Y U R W T

İlk sağ alt liste:

Y U R W T

hala sıralanması gerekiyor.

İlk Sağ Alt Listeyi Fethetmek
İlk sağ alt liste için Hızlı Sıralama çağrısının yürütülmek yerine not edildiğini ve ayrıldığını unutmayın. Bu noktada, yürütülecektir. Ve böylece, yeni dizi[düşük] = dizi[5] = dizi[QPivotIndex+1] ve yeni dizi[yüksek] dizi[9] olarak kalır. İlk sol alt liste için gerçekleşen benzer bir dizi etkinlik burada da gerçekleşecek. Ve bu ilk sağ alt liste şu şekilde sıralanır:

R T U W Y

Ve orijinal sıralanmamış liste şu şekilde sıralandı:

E I O P Q R U W Y

Java Kodlama

Algoritmayı Java'ya koymak, yukarıdaki tüm sözde kod parçalarını tek bir sınıftaki Java yöntemlerine koymaktır. Sınıfta, sıralanmamış diziyle quicksort() işlevini çağıracak bir main() yönteminin olması gerektiğini unutmayın.

pivot() Yöntemi

Pivot değerini döndüren Java pivot() yöntemi şöyle olmalıdır:

takas() Yöntemi

swap() yöntemi şöyle olmalıdır:

Quicksort() Yöntemi

quicksort() yöntemi şöyle olmalıdır:

partition() Yöntemi

partition() yöntemi şöyle olmalıdır:

main() Yöntemi

main() yöntemi şunlar olabilir:

Yukarıdaki yöntemlerin tümü bir sınıfa yerleştirilebilir.

Çözüm

Hızlı Sıralama, böl ve yönet paradigmasını kullanan bir sıralama algoritmasıdır. Sıralanmamış bir listeyi iki veya üç alt listeye bölerek başlar. Bu öğreticide, Hızlı Sıralama, bir listeyi üç alt listeye bölmüştür: sol alt liste, tek bir öğenin orta listesi ve sağ alt liste. Hızlı Sıralamada fethetmek, bir özet değeri kullanarak bir listeyi veya alt listeyi sıralarken bölmektir. Bu öğretici, Java bilgisayar dilinde Hızlı Sıralamanın bir uygulamasını açıklamaktadır.

Yazar hakkında

kasımpatı

İlk İlkeler ve ilgili serilerden matematik entegrasyonunun kaşifi. Teknik Eğitimde Yüksek Lisans Derecesi, Elektronik ve Bilgisayar Yazılımı konusunda uzmanlaşmıştır. Lisans Elektronik. Ayrıca Bilgisayar ve Telekomünikasyon alanında Yüksek Lisans düzeyinde bilgi ve deneyime sahibim. 20.000 yazar arasında devarticles.com'un en iyi 37. yazarıydım. 10 yılı aşkın süredir bu alanlarda çalışıyorum.

İLGİLİ LINUX İPUCU YAYINLARI

• Java'da Dizeleri Karşılaştırma
• Java'da HashMap nasıl kullanılır
• Java'da Hızlı Sıralama Açıklaması
• Java'da İkili Ağaç Ön Sipariş Geçişi
• Java'da Birleştirme Sıralaması Açıklaması
• Java'da Tarayıcı nasıl kullanılır
• Java dosyaya yazma