quick sort c with examples
Çizim ile C ++ 'da Hızlı Sıralama.
Quicksort, 'pivot' adı verilen belirli bir öğeyi seçen ve sıralanacak diziyi veya listeyi, pivottan daha küçük öğelerin listenin solunda olduğu ve bu pivot s0'a göre iki parçaya ayıran, yaygın olarak kullanılan bir sıralama algoritmasıdır. pivottan daha büyük olanlar listenin sağındadır.
Böylece liste iki alt listeye bölünmüştür. Aynı boyut için alt listeler gerekli olmayabilir. Ardından Quicksort, bu iki alt listeyi sıralamak için kendini yinelemeli olarak çağırır.
=> Mükemmel C ++ Eğitim Kılavuzuna Buradan Bakabilirsiniz.
Ne öğreneceksin:
- Giriş
- Genel Algoritma
- Quicksort İçin Sözde Kod
- İllüstrasyon
- C ++ Örneği
- Java Örneği
- Quicksort Algoritmasının Karmaşıklık Analizi
- 3 yönlü Hızlı Sıralama
- Randomize Hızlı Sıralama
- Hızlı Sıralama ve Birleştirme Sıralaması
- Sonuç
- Önerilen Kaynaklar
Giriş
Quicksort, daha büyük diziler veya listeler için bile verimli ve daha hızlı çalışır.
Bu eğitimde, Quicksort algoritmasının bazı programlama örnekleriyle birlikte Quicksort'un çalışması hakkında daha fazla bilgi edineceğiz.
Bir pivot değer olarak ilk, son veya orta değer veya herhangi bir rastgele değer seçebiliriz. Genel fikir, sonuçta pivot değerinin dizideki diğer öğeleri sola veya sağa hareket ettirerek dizideki uygun konumuna yerleştirilmesidir.
Genel Algoritma
Quicksort için genel algoritma aşağıda verilmiştir.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Şimdi Quicksort tekniğinin sözde koduna bir göz atalım.
Quicksort İçin Sözde Kod
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Bölümleme algoritmasının çalışması bir örnek kullanılarak aşağıda açıklanmıştır.
Bu çizimde, son öğeyi pivot olarak alıyoruz. Dizide tek bir eleman elde edene kadar dizinin pivot eleman etrafında art arda bölündüğünü görebiliriz.
Şimdi, konsepti daha iyi anlamak için aşağıda Quicksort'un bir resmini sunuyoruz.
İllüstrasyon
Hızlı sıralama algoritmasının bir örneğini görelim. Pivot olarak son elemanı olan aşağıdaki diziyi düşünün. Ayrıca, ilk öğe düşük olarak etiketlenir ve son öğe yüksektir.
işlevlerde c ++ dizileri
Resimden, işaretçileri dizinin her iki ucunda da yukarı ve aşağı hareket ettirdiğimizi görebiliriz. Alçak, pivottan daha büyük öğeyi işaret ettiğinde ve yüksek, pivottan daha küçük öğeyi işaret ettiğinde, bu öğelerin konumlarını değiştirir ve alçak ve yüksek işaretçileri ilgili yönlerde ilerletiriz.
Bu, alçak ve yüksek işaretçiler birbirini geçene kadar yapılır. Birbirlerini geçtiklerinde, pivot eleman uygun pozisyonuna yerleştirilir ve dizi ikiye bölünür. Daha sonra, bu alt dizilerin her ikisi de hızlı sıralama kullanılarak birbirlerinden bağımsız olarak sıralanır.
C ++ Örneği
Aşağıda, Quicksort algoritmasının C ++ 'da uygulanması verilmiştir.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Çıktı:
Giriş dizisi
12 23 3 43 51 35 19 45
Hızlı sıralama ile sıralanmış dizi
3 12 19 23 35 43 45 51
Burada, diziyi bölümlemek ve bölümü sıralamak için hızlı sıralamayı yinelemeli olarak çağırmak için kullanılan birkaç rutinimiz var, temel hızlı sıralama işlevi ve dizi içeriğini görüntülemek ve iki öğeyi buna göre değiştirmek için yardımcı işlevler.
İlk olarak, girdi dizisi ile hızlı sıralama işlevini çağırıyoruz. Quicksort işlevinin içinde, bölümleme işlevi diyoruz. Bölüm işlevinde, dizinin pivot öğesi olarak son öğeyi kullanırız. Pivot karar verildikten sonra, dizi iki parçaya bölünür ve ardından her iki alt diziyi de bağımsız olarak sıralamak için hızlı sıralama işlevi çağrılır.
Hızlı sıralama işlevi döndüğünde, dizi, pivot öğesi doğru konumunda ve pivottan daha küçük öğeler pivotun solunda ve pivottan daha büyük öğeler pivotun sağında olacak şekilde sıralanır.
Daha sonra, hızlı sıralama algoritmasını Java'da uygulayacağız.
Java Örneği
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Çıktı:
Giriş dizisi
12 23 3 43 51 35 19 45
Quicksort ile sıraladıktan sonra dizi
3 12 19 23 35 43 45 51
Java uygulamasında da C ++ uygulamasında kullandığımız mantığı kullandık. Pivot elemanını uygun konumuna yerleştirmek için pivot ve quicksort işlemi dizi üzerinde gerçekleştirilirken dizideki son elemanı kullandık.
yazılım test örneklerindeki test senaryoları
Quicksort Algoritmasının Karmaşıklık Analizi
Quicksort tarafından bir diziyi sıralamak için geçen süre, girdi dizisine ve bölümleme stratejisine veya yöntemine bağlıdır.
K, pivottan daha az öğe sayısı ise ve n toplam öğe sayısı ise, hızlı sıralama tarafından alınan genel süre aşağıdaki gibi ifade edilebilir:
T (n) = T (k) + T (n-k-1) + O (n)
Burada, T (k) ve T (n-k-1) özyinelemeli çağrılar tarafından alınan zamandır ve O (n) çağrıyı bölümlendirerek geçen zamandır.
Hızlı sıralama için bu zaman karmaşıklığını ayrıntılı olarak analiz edelim.
# 1) En kötü durum : Hızlı sıralama tekniğindeki en kötü durum, çoğunlukla dizideki en düşük veya en yüksek elemanı pivot olarak seçtiğimizde ortaya çıkar. (Yukarıdaki çizimde pivot olarak en yüksek öğeyi seçtik). Böyle bir durumda en kötü durum, sıralanacak dizi zaten artan veya azalan sırada sıralandığında ortaya çıkar.
Dolayısıyla, alınan toplam süre için yukarıdaki ifade şu şekilde değişir:
T (n) = T (0) + T (n-1) + O (n) çözülür O (niki)
# 2) En iyi durum: Hızlı sıralama için en iyi durum her zaman, seçilen pivot öğesi dizinin ortası olduğunda ortaya çıkar.
Dolayısıyla, en iyi durum için tekrarlama şudur:
en iyi sabit disk klonlama yazılımı Windows 10
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Ortalama durum: Hızlı sıralama için ortalama durumu analiz etmek için, tüm dizi permütasyonlarını göz önünde bulundurmalı ve sonra bu permütasyonların her biri için geçen zamanı hesaplamalıyız. Özetle, hızlı sıralama için ortalama süre de O (nlogn) olur.
Aşağıda, Quicksort tekniği için çeşitli karmaşıklıklar verilmiştir:
En kötü durum zaman karmaşıklığı O (n 2) istikrar Aynı değerlere sahip iki öğe aynı sıraya yerleştirilmeyeceğinden kararlı değildir. Kararlı - sıralı çıktıda aynı değerlere sahip iki öğe aynı sırada görünecektir. En iyi vaka süresi karmaşıklığı O (n * günlük n) Ortalama zaman karmaşıklığı O (n * günlük n) Uzay karmaşıklığı O (n * günlük n)
Çabuk sıralamayı yalnızca pivot öğesinin seçimini (orta, ilk veya son) değiştirerek birçok farklı şekilde uygulayabiliriz, ancak en kötü durum, hızlı sıralama için nadiren ortaya çıkar.
3 yönlü Hızlı Sıralama
Orijinal hızlı sıralama tekniğinde, genellikle bir pivot öğesi seçeriz ve ardından diziyi bu pivot etrafında alt dizilere böleriz, böylece bir alt dizi pivot'tan daha küçük öğelerden ve diğeri pivot'tan daha büyük öğelerden oluşur.
Peki ya bir pivot öğesi seçersek ve dizide pivot'a eşit birden fazla öğe varsa?
Örneğin, şu diziyi düşünün {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Bu dizide basit bir hızlı sıralama gerçekleştirirsek ve pivot öğesi olarak 4'ü seçersek, o zaman öğe 4'ün yalnızca bir oluşumunu düzeltiriz ve geri kalanı diğer öğelerle birlikte bölümlenir.
Bunun yerine, 3 yollu hızlı sıralama kullanırsak, (l… r) dizisini aşağıdaki gibi üç alt diziye böleriz:
- Dizi (l… i) - Burada, i pivottur ve bu dizi, pivot'tan daha az öğeler içerir.
- Dizi (i + 1… j-1) - Pivot'a eşit olan öğeleri içerir.
- Dizi (j… r) - Pivottan daha büyük öğeler içerir.
Böylece, dizide birden fazla yedek elemanımız olduğunda 3 yollu hızlı sıralama kullanılabilir.
Randomize Hızlı Sıralama
Hızlı sıralama tekniği, pivot öğesini seçmek için rasgele sayılar kullandığımızda rasgele hızlı sıralama tekniği olarak adlandırılır. Rastgele hızlı sıralamada, buna 'merkezi pivot' denir ve diziyi, her iki tarafta en az ¼ eleman olacak şekilde böler.
Rastgele hızlı sıralama için sözde kod aşağıda verilmiştir:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureYukarıdaki 'randomQuickSort' kodunda, 2. adımda merkezi pivotu seçiyoruz. 2. adımda, seçilen öğenin merkezi pivot olma olasılığı ½'dir. Bu nedenle, 2. adımdaki döngünün 2 kez çalışması beklenir. Böylelikle randomize hızlı sıralamada adım 2 için zaman karmaşıklığı O (n) 'dir.
Merkezi pivotu seçmek için bir döngü kullanmak, randomize hızlı sıralama uygulamak için ideal bir yol değildir. Bunun yerine, rastgele bir eleman seçebilir ve ona merkezi pivot diyebiliriz veya dizi elemanlarını yeniden karıştırabiliriz. Randomize hızlı sıralama algoritması için beklenen en kötü durum zaman karmaşıklığı O (nlogn).
Hızlı Sıralama ve Birleştirme Sıralaması
Bu bölümde, Hızlı sıralama ve Birleştirme sıralaması arasındaki temel farkları tartışacağız.
Karşılaştırma Parametresi Hızlı sıralama Sıralamayı birleştir bölümleme Dizi, bir pivot öğesi etrafında bölümlenir ve her zaman iki yarıya bölünmesi gerekmez. Herhangi bir oranda bölümlenebilir. Dizi iki yarıya bölünmüştür (n / 2). En kötü durum karmaşıklığı O (n 2) - en kötü durumda çok sayıda karşılaştırma yapılması gerekir. O (nlogn) - ortalama durumla aynı Veri setleri kullanımı Daha büyük veri kümeleriyle iyi çalışamaz. Boyuttan bağımsız olarak tüm veri kümeleriyle iyi çalışır. Ek alan Yerinde - ek alana ihtiyaç duymaz. Yerinde değil - yardımcı diziyi depolamak için ek alana ihtiyaç duyar. Sıralama yöntemi Dahili - veriler ana bellekte sıralanır. Harici - veri dizilerini depolamak için harici bellek kullanır. Verimlilik Küçük boyutlu listeler için daha hızlı ve verimli. Daha büyük listeler için hızlı ve verimli. Diziler / bağlantılı listeler Diziler için daha çok tercih edilir. Bağlantılı listeler için iyi çalışır.
Sonuç
Adından da anlaşılacağı gibi, hızlı sıralama, listeyi diğer sıralama algoritmalarından daha hızlı sıralayan algoritmadır. Tıpkı birleştirme sıralaması gibi, hızlı sıralama da bir bölme ve yönetme stratejisi benimser.
Daha önce gördüğümüz gibi, hızlı sıralamayı kullanarak listeyi pivot elemanını kullanarak alt dizilere böleriz. Daha sonra bu alt diziler bağımsız olarak sıralanır. Algoritmanın sonunda tüm dizi tamamen sıralanır.
Quicksort daha hızlıdır ve veri yapılarını sıralamak için verimli bir şekilde çalışır. Quicksort, popüler bir sıralama algoritmasıdır ve bazen birleştirme sıralama algoritmasına göre tercih edilir.
Bir sonraki eğitimimizde, Shell sıralaması hakkında daha ayrıntılı olarak tartışacağız.
=> Burada Basit C ++ Eğitim Serisine Dikkat Edin.
Önerilen Kaynaklar
- MongoDB Sort () Yöntemi Örneklerle
- Sözdizimi, Seçenekler ve Örneklerle Unix Sıralama Komutu
- C ++ 'da Sıralamayı Örneklerle Birleştirme
- Örneklerle C ++ 'da Yığın Sıralama
- Örneklerle C ++ 'da Kabuk Sıralama
- Örneklerle C ++ 'da Seçim Sırala
- Örneklerle C ++ 'da Kabarcık Sıralama
- Örneklerle C ++ 'da Ekleme Sıralaması
