twitter
Google Plus
tumblr
rss

Yorumlar Hakkında - Duyuru

Yorumlarda lütfen sallama da olsa bir isim yazın. "Adsız" olarak yazıyorsunuz, sonra birçok kişi adsız olarak birşey soruyor. cevap verirken "@adsız (15 ekim 13:08)'de yazan kişi" diye yazıyorum. Hoş olmuyor :) Eminim isminiz çok güzeldir deyip, sizi konuyla baş başa bırakıyorummm.

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

.dll (2) .NET (1) #googleplus (1) +1 butonu (1) 9gag (1) a ve an neye göre belirlenir (1) açıklama (2) Adsense (1) Adtech (1) Afrikalı zenci bir çocuğun bu şiiri (1) algorithm (1) antivirüs (1) Apaci (1) apple (4) arkadaş ekleme (1) Arkadaş-Sevgili Şiiri (1) Arkadaşın Olmayan Kişilerin Resimlerini Görmek (1) asus notebook menteşe kırıldı (1) aşk tesadüfleri sever (1) azize nur (1) bakmak (2) balcali hastanesi (1) basit (3) Basit Css Ornegi (1) basit örnek (3) bedava (2) bedava internete girmek (1) bilgisayar mühendisi (1) bilinçaltı (1) biyografisi (2) blogda değişiklikler (1) blogger kod çevirici (1) blogger temaları (1) blogspot için widgetler (1) boost hack (2) bot yapma (1) bozuk zil sesi (1) btk yasağı (1) c de fonksiyonlar (1) c programlama dili (1) C++ hesap makinesi kodları (1) c++ sayı tahmin oyunu (basit) (1) Cd key already in use (1) CD key değiştirme (1) counter strike cd key sorunu (1) crack (2) cs cd key değiştirme işlemi (1) Css dersleri (1) cyprus flights (1) cyprus travel (1) database (2) ders notu (1) developer (1) directtraveller (1) dns ayarları (1) doğum günü (1) dowland (1) download (12) e-ticaret (1) Eklentisi (18) ekran kararıyor (1) en son bölüm (1) engeli kaldırmak (1) english grammar (1) English Proverbs (1) error (1) Ezel dizisi (1) f8 konferansı (1) facebook (8) facebook giremiyorum (2) Facebook Hesabım kapatıldı (1) facebook hesabıma ulaşamıyorum (1) facebook istatistik (1) facebook neden açılmıyor (1) facebook tarzı (1) facede ilginç profil resmi (1) file_get_contents (1) film müzikleri (1) filmin konusu (1) flash etiket bulutu (1) Follower Bug (1) Friend Requests Blocked (1) full (3) galaxy s3 (2) galaxy s3 ayarları (1) galaxy s3 flash apk (1) galaxy s3 flash player (1) Galaxy S3 Zil Sesi Değiştirme (1) gau (1) girne amerikan (1) gizem doğan facebook (1) go to imageshack.us to register (1) Google (6) Google +1 buton (1) google plus (1) google projeleri (2) göğüslü (1) haberleri (3) hack (6) harici harddisk açılmıyor (1) Hayat Hikayesi (1) hepsiniseninicinyaptim.tumblr.com (1) Hesaba Ulaşılamıyor (1) hileleri (2) how to InnoDB (1) html alt satıra geçme kodu (1) html kod çeviriçi (1) html kodu (1) html5 (1) Ingilizce fillerin 2. ve 3. halleri (1) InnoDB (1) ilginç resimler (1) ilk apple bilgisayar (1) imhatimi (2) imhatimi.org (3) inci sözlük (1) ingilizce sözler (1) ingilizcede (1) iphone (2) iphone 5 (2) iş takip (1) iş takip programı (1) iş takip programı full (1) iş takip programı ücretsiz (1) iş takip programları (1) java (2) karakter sorunu (1) kıbrıs (2) kız arkadaş (1) kimdir (5) kimler oynuyor (3) klasör gizleme (1) kpss (1) kpss çalındı mı (1) kpss soruları (1) Marika Fruscio (1) Mark Zuckerberg (3) mp3 (4) mp3 kesme programı (1) msn hack (3) mysql (2) nasıl açılır (2) nasıl çalışır (3) nasıl kurulur (2) nasıl yapılır (4) nasil (3) ne (7) ne demek (11) ne işe yarar (10) ne zaman (9) neden (4) nedir (16) Need For Speed World Update Sorunu (1) nfs (3) nfs world (1) Nikola Tesla (1) no bra january (1) online izle (4) orucu bozan haller (1) öss (2) ösym (3) Photoshop dosyalarinda psd onizleme (1) php (4) programı (3) resimli anlatım (2) resmi (3) samsung (5) samsung galaxy s3 (4) samsung galaxy s3 sorunları (1) Samsung Galaxy S3 Zil Sesi Değiştirme (1) seditio (7) seditio corehacks (1) seditio destek sitesi (1) Seditio eklenti (4) Seditio Flash Etiket Bulutu (2) seo (1) seo nedir (1) serial (4) sistem gereksinimleri (3) sorunu (8) sözler (2) sözleri (4) sql server 2008 kurulumu (1) Steve Jobs (2) Steve Jobs kimdir (1) survivor taner (1) şiirleri (2) şişmanlama (1) şuuraltı mesajları (1) tavsiye (3) telefon (7) torrent (3) troubleshoot3r (2) troubleshooter (28) türkçe (3) Türkçe Altyazı (1) twitter (2) utf-8 (2) virüs bulaştı (1) web tasarım (1) web tasarım adana (1) windows 7 (3) Yılmaz ilker şahin (2) zend framework (1)