twitter
Google Plus
tumblr
rss

Reklamlar Hakkında - Duyuru

Ilginiz icin teşekkürler

14 Mart 2011 Pazartesi

Quicksort nasil yapilir? How to Quicksort in C++, Java

Okulda ders alırken görmüştük bu sorting methodları.Kıyıda bir köşede bulunsun diye ekliyorum bloguma.Ara sıra lazım oluyor.Şu siteden alıntıdır.Metin ingilizce, sormak istediğiniz bir yer olursa, yorumlarınızda belirtin,elimden geldiği kadar yardım ederim .

Quicksort

Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can write quicksort as fast as bubble sort.

Algorithm

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
  1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.
  2. Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
  3. Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.

Partition algorithm in detail

There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array and j points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1). Algorithm stops, when i becomes greater than j.
After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.
Example. Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort. Quicksort example
Notice, that we show here only the first recursion step, in order not to make example too long. But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.

Why does it work?

On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ b inequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated above, the whole array is sorted.

Complexity analysis

On the average quicksort has O(n log n) complexity, but strong proof of this fact is not trivial and not presented here. Still, you can find the proof in . In worst case, quicksort runs O(n2) time, but on the most "practical" data it works just fine and outperforms other O(n log n) sorting algorithms.

Code snippets

Partition algorithm is important per se, therefore it may be carried out as a separate function. The code for C++ contains solid function for quicksort, but Java code contains two separate functions for partition and sort, accordingly.

Java

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
         return i;
}
void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

C++

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

0 yorum:

Yorumlar Hakkında:


Yorum yapmaktan çekinmeyin, Yorumlar hem benim için teşvik, sizin içinde kendinizi ifade edebileceğiniz bir ortam! İyi veya kötü her türlü yoruma açığım. Ha bu arada unutmadan, yaptığınız yorumda bana cevap vermemi beklediğiniz birşey yazdıysanız, lütfen verdiğim cevabı okumak için 1-2 içinde blogumu tekrar kontrol edin.

Yorum Gönder

Etiketgiller

.NET (1) .nomedia (1) .torrent uzantılı (1) *#0228# quick start (1) *#0228# Quick Start ne işe yarıyor (1) 2019 Yeni Kasa Toyota Auris (MK3) (1) 8 mart nedir (1) a/an ve the Kullanımı (1) açamıyorum (1) android dns adresi değiştirme (1) android dosya gizleme hesap makinesi (1) android gizli klasör (1) android market (2) android porno (1) android yasakli site acma programi (1) araba (6) arkadaş ekleme (1) ayrılık şiirleri (1) ayrılık yazıları (1) ayrılıkla ilgili (1) Battle Royale 0xc000007b hatası (1) bedava internete girmek (1) Bedelli askerlik (1) Beyaz Ekran Sorunu (1) Blog güncellemeleri (1) blog tema değişimi (2) bowling oyunları (1) bowling skor (1) bowling strike (1) bowlingde skor (1) bozuluyor (1) Bu ağa bağlanamıyor (1) bu ağa bağlanılamıyor windows 8 (1) Bu öğe bulunamadı (1) Call of Duty (1) Cd key already in use (1) clash royale (1) clash royale deste (1) core_ets2mp.dll Hatası (1) counter strike cd key sorunu (1) cs 1.6 (1) cs cd key değiştirme işlemi (1) çalışma prensibi (1) çalışmayı durdurdu (2) çalışmıyor (2) çalıştırma (1) çözüldü (1) çözüm (4) Çözümü (7) ders notu (1) deyimler (2) disk temizleme (1) dll (2) dll dosyası (1) dll hatası (2) DNS (1) DNS adresleri (1) dns ayarları (3) DNS listesi (1) dosya gizleme (1) dosya silinmiyor (1) Dosya Şifreleme (1) dowland (1) dünya kadınlar günü (1) e-devlet (1) En Hızlı DNS (1) English Proverbs (1) ets 2 hava basıncı sorunu (1) ets2 (3) ets2 düşük hava basıncı (1) euro truck simulator 2 (2) euro truck simulator 2 multiplayer (1) face hackleme (1) facebook filmi (1) facebook giremiyorum (3) Facebook Hesabım kapatıldı (1) facebook hesabıma ulaşamıyorum (1) facebook neden açılmıyor (1) facebookta bakım (1) facede profiline kimler bakmış (1) FIFA 18 (1) FIFA 18 DirectX Function Sorunu (1) filtrenize göre iş bulunmuyor (1) fiyat listesi (1) fiyatı ne kadar (1) FM 2018 (1) Football Manager 2018 (1) Fortnite (1) Fortnite Battle Royale (1) giremiyorum (1) Google (8) google güvenlik (1) google hatası (1) göremiyorum (1) görünmesin (1) gösterimi (1) göstermek (1) göstermiyor (2) gözükmesin (1) gözükmesini engellemek (1) GTA 5 (2) GTA 5 Açılmama Sorunu (1) Gta 5 Online bağlantı sorunu (1) GTA 5 yükleme Sorunu (1) GTA v donma sorunu (1) gta v kasma sorunu (1) güncelleme (2) güncelleme duraklatıldı (1) haberi (1) haberleri (3) hack (2) happy new year (1) Hata Kodu: -130 Sayfa yüklenemedi (bilinmeyen hata) (1) hata veriyor (1) hatası (3) hatchback (1) Hayat Hikayesi (1) Ingilizce fillerin 2. ve 3. halleri (1) ie7 (1) ie8 (1) ilginç (1) ilişki durumu (1) ilk kim (1) inanılmaz evlenme teklifi (1) inceleme (5) indir (8) indirim kodu (1) ingilizce ders (1) ingilizce sözler (1) instagram (3) instagram durduruldu (1) instagram geçiçi olarak engellendin (1) instagram güncelleme (1) instagram hatası (1) internet explorer (1) ios (6) ios 11 (1) ios 11 şarj sorunu çözümü (1) istanbul (3) istatistikler (1) iş takip programı (1) javascript (1) kadın (1) kaldırır mı (1) Kamera Sorunu (1) kapandı (1) karakter problemi (1) karakter sorunu (1) kentsel dönüşüm (1) kentsel dönüşüm kira yardımı (1) kentsel dönüşüm laboratuvarı (1) kız arkadaş (1) kız arkadaşı (1) kız tavlama (1) kilitleniyor (1) Kilo Almak icin (1) kim 500 milyar ister (1) kim milyoner olmak ister (15) kimdir (10) klasör gizleme (1) komik resimler (1) korkunç (1) kredi hesaplama (1) kredi notu düşmeyen bankalar (1) kumanda (1) kurucusu kim (1) kurulumu (2) library (1) mantığı nedir (1) Masterchef (1) Masterchef Türkiye (1) Mazda 3 2018 (1) mazda 3 inceleme (1) mp3 (4) mp3 açılımı nedir (1) MSVCR100.DLL (1) Mukemmel Sayı (1) Mustafa (1) mükemmel sayı nedir (1) müslüm gürses kimdir (1) nasıl (23) nasıl çalışır (3) nasıl girerim (1) nasıl gizlenir (1) nasıl kaldırılır (1) nasıl kapatılır (1) nasıl oynanır (1) nasıl silinir (1) nasıl yaparım (6) ne (7) ne demek (11) ne işe yarar (10) ne kadar (1) ne zaman (11) ne zaman kuruldu (1) neden (4) neden açılmıyor (1) neden hata veriyor (1) Need for Speed (5) Need for Speed hatası (1) Need For Speed Payback (1) Need For Speed The Run (1) nfs (5) nfs hot pursuit (2) nfs the run (1) niçin (1) niye (8) oyun (27) oyun hilesi (1) öğe bulunamadı hatası konumunu doğrulayıp yeniden deneyin win 10 (1) örneği (1) örnek proje (1) özellikleri (2) pes 2011 (1) PES 2017 PES 2018 (1) philips tv (1) php (4) PLAYERUNKNOWN'S BATTLEGROUNDS (1) porna (1) programı (3) pugb (3) QR Kod Nedir (1) resimleri (1) RISK: Global Domination (1) s-voice dil değiştirme (1) s6 özellikleri (1) samsung (8) seditio (6) Seditio eklenti (4) Serel Yereli (1) Sevgili (2) sevgilim (1) sevk tarihi ne demek (1) sistem gereksinimleri (4) sorun (3) sorun çözümü (24) sorunları (1) sorunu (7) sosyal medya (3) sözleri (4) steam (9) steam hatası (4) strike nedir (1) şarj sorunu (1) tavsiye android uygulamaları (1) tavsiye edilen android uygulamaları (1) teknoloji (2) telefon (16) the game malfunctioned hatası (1) Toyota Auris (2) Trackmania Nations Forever (1) troubleshoot3r (2) troubleshooter (21) truckersMP (1) türkçe (3) türkçe yama (2) update (2) update hatası (1) video (2) videoları (2) web dizayn (1) web tasarım (1) web tasarım adana (1) win 10 (1) win10 (3) win7 (4) windows (6) windows 10 (6) windows 7 (5) xinput1_3.dll (1) yasaklı sitelere girmek (2) zaman (1)