Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Hızlı sıralama (İngilizcesi: Quicksort), günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.
| Hızlı sıralama | |
|---|---|
 Hızlı sıralama'nın uygulanması sırasındaki davranışı. Yatay çizgiler seçilen pivot elemanları gösterir. | |
| Sınıf | Sıralama algoritması |
| Veri yapısı | Değişken |
| Zaman karmaşıklığı | Ortalama O(n log n) |
| En iyi | Ara sıra |
| Alan karmaşıklığı | Uygulamaya göre değişken |
Tarihi
Hızlı sıralama algoritması 1960 yılında küçük bir İngiliz şirketi olan 'ta çalışan C. A. R. Hoare tarafından geliştirilmiştir.
Algoritma
Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır.
Algoritmanın adımları aşağıdaki gibidir:
- Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç.
- Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir). Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir. Algoritmanın bu aşamasına bölümlendirme aşaması denir.
- Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden olarak çağrılarak sıralanır.
Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar.
Örnek
Algoritma
TEKRARLA Ara index_sol için sortFeld[index_sol] ≥ sortFeld[Pivot] Ara index_sağ için sortFeld[index_sağ] ≤ sortFeld[Pivot] EĞER index_sol ve index_sağ bulundu ise SONRA Değiştir sortFeld[index_sol] ile sortFeld[index_sağ] YOKSA Bir element kaydır SON EĞER Koşul tamamlanıncaya kadar
Üstteki algoritmaya göre asagidaki örnek :
SORTIERBEISPIEL
1 - Pivot(karşılaştırma) elementini bulmak için :
İlk önce harfler sayılır. Eger toplam tek ise (1) ekleyip ikiye bölünür. (15 + 1) / 2 = 8 toplam çift ise ikiye bölünür.
2 - Bu durumda Pivot element B oluyor. SORTIER B EISPIEL
Burada ilk harf olan 'S' son harf olan 'L' ve orta harf olan 'B' karşılaştırılır. İçlerinde ortanca olan değer her zaman orta değerdir.
Yani örnek şu şekle dönüşür : SORTIER L EISPIEB
3 - Yukarıdaki algoritma göz önünde bulundurulursa;
Kontrol ediliyor : Soldaki element(S) Pivot(L) den büyük mü? (Evet ) Sağdaki element(B) Pivot(L) den küçük mü? (Evet )
Eğer iki koşul da doğru ise ilk element(S) ile son element(B) yer değiştirilir. (BORTIER L EISPIES) (Algoritmaya göre sadece ikisi 'evet' ise değişim gerçekleşir)
Soldaki element(O) Pivot(L) den büyük mü? (Evet ) Sağdaki element(E) Pivot(L) den küçük mü? (Evet )
Eğer iki koşul da doğru ise ilk element(O) ile son element(E) yer değiştirilir. (BERTIER L EISPIOS)
Soldaki element(R) Pivot(L) den büyük mü? (Evet ) Sağdaki element(I) Pivot(L) den küçük mü? (Evet )
Eğer iki koşul da doğru ise ilk element(R) ile son element(I) yer değiştirilir. (BEITIER L EISPROS)
Soldaki element(T) Pivot(L) den büyük mü? (Evet ) Sağdaki element(P) Pivot(L) den küçük mü? (Hayır )
Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor, sağdaki element(P) yi direkt sağa yazılır. (BEIIER L EISPROS) (DİKKAT : 'T' algoritmaya şu an dahil değil, ta ki ikisi de 'evet' oluncaya kadar)
Soldaki element(T) Pivot(L) den büyük mü? (Evet ) Sağdaki element(S) Pivot(L) den küçük mü? (Hayır )
Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor, sağdaki element(S) yi direkt sağa yazılır. (BEIIER L EISPROS)
Soldaki element(T) Pivot(L) den büyük mü? (Evet ) Sağdaki element(I) Pivot(L) den küçük mü? (Evet )
Eğer iki koşul da doğru ise element(T) ile element(I) yer değiştirilir. (BEIIIER L ETSPROS) (Şimdi 'T' yazılabilir, ikisi de evet)
Soldaki element(E) Pivot(L) den büyük mü? (Hayır ) Sağdaki element(E) Pivot(L) den küçük mü? (Evet )
Eğer bir koşul yanlış ise soldaki element(E) sola yazılır, sağdaki element(E) sabit kalıyor (BEIIIER L ETSPROS)
Soldaki element(R) Pivot(L) den büyük mü? (Evet ) Sağdaki element(E) Pivot(L) den küçük mü? (Evet )
Eğer bir koşul da doğru ise soldaki element(R) ile sağdaki element(E) sabit kalıyor (BEIIIEE L RTSPROS)
Son aşama
Soldaki element(R) Pivot(L) den büyük mü? (Evet ) Sağdaki element(E) Pivot(L) den küçük mü? (Evet )
Eğer bir koşul yanlış ise soldaki element(R) sola yazılır, sağdaki element(E) sabit kalıyor (BEIIIEE L RTSPROS)
B - E - I - I - I - E - E - L - R - T - S - P - R - O - S
Aynı işlemleri sağdaki ve soldaki bölümlere ayrı ayrı yapılır.
Sonuç şöyle :
B E E E I I I L O P R R S S T
Sözde Kodu
Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:
function quicksort(array) var list less, equal, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x < pivot then append x to less if x = pivot then append x to equal if x > pivot then append x to greater return concatenate(quicksort(less), equal, quicksort(greater))
Diğer Sıralama Algoritmaları
Kaynakça
- ^ . Computer History Museum. 21 Haziran 2015 tarihinde kaynağından arşivlendi.
Kaynakça
- Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." 4(7), 321-322, 1961
- Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." Discrete Applied Mathematics 154(1): 1-5. 2006.
- R. Sedgewick. Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.
- David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Pages 113–122 of section 5.2.2: Sorting by Exchanging.
- , , , and . , Second Edition. MIT Press ve McGraw-Hill, 2001. . Chapter 7: Quicksort, pp. 145–164.
- A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.
- . Analysis of Quicksort 30 Eylül 2007 tarihinde Wayback Machine sitesinde .. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
- Steven Skiena. . CSE 373/548 - Analysis of Algorithms. Department of Computer Science. State University of New York at Stony Brook.
- Conrado Martínez and Salvador Roura, Optimal sampling strategies in quicksort and quickselect. SIAM J. Computing 31(3):683-705, 2001.
- Jon L. Bentley and M. Douglas McIlroy, "Engineering a Sort Function, SOFTWARE---PRACTICE AND EXPERIENCE, VOL. 23(11), 1249–1265, 1993
Dış bağlantılar
- Hızlı Sıralama videosu 6 Eylül 2010 tarihinde Wayback Machine sitesinde .
- 32 programlama dilinde yazılmış Hızlı Sıralama örnekleri 1 Mart 2008 tarihinde Wayback Machine sitesinde .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Hizli siralama Ingilizcesi Quicksort gunumuzde yaygin olarak kullanilan bir siralama algoritmasidir Hizli siralama algoritmasi n adet sayiyi ortalama bir durumda O n log n displaystyle mathcal O n log n karmasikligiyla en kotu durumda ise O n2 displaystyle mathcal O n 2 karmasikligiyla siralar Algoritmanin karmasikligi ayni zamanda yapilan karsilastirma sayisina esittir Hizli siralamaHizli siralama nin uygulanmasi sirasindaki davranisi Yatay cizgiler secilen pivot elemanlari gosterir SinifSiralama algoritmasiVeri yapisiDegiskenZaman karmasikligiOrtalama O n log n En iyiAra siraAlan karmasikligiUygulamaya gore degiskenTarihiHizli siralama algoritmasi 1960 yilinda kucuk bir Ingiliz sirketi olan ta calisan C A R Hoare tarafindan gelistirilmistir AlgoritmaHizli siralama algoritmasi siralanacak bir sayi dizisini daha kucuk iki parcaya ayirip olusan bu kucuk parcalarin kendi icinde siralanmasi mantigiyla calisir Algoritmanin adimlari asagidaki gibidir Sayi dizisinden herhangi bir sayiyi pivot eleman olarak sec Sayi dizisini pivottan kucuk olan tum sayilar pivotun onune pivottan buyuk olan tum sayilar pivotun arkasina gelecek bicimde duzenle pivota esit olan sayilar her iki yana da gecebilir Bu bolumlendirme isleminden sonra eleman siralanmis son dizide olmasi gerektigi yere gelir Algoritmanin bu asamasina bolumlendirme asamasi denir Pivotun sol ve sag yaninda olmak uzere olusan iki ayri kucuk sayi dizisi hizli siralama algoritmasi bu kucuk parcalar uzerinde yeniden olarak cagrilarak siralanir Algoritma icinde sayi kalmayan eleman sayisi sifir olan bir alt diziye ulastiginda bu dizinin sirali oldugunu varsayar OrnekAlgoritma TEKRARLA Ara index sol icin sortFeld index sol sortFeld Pivot Ara index sag icin sortFeld index sag sortFeld Pivot EGER index sol ve index sag bulundu ise SONRA Degistir sortFeld index sol ile sortFeld index sag YOKSA Bir element kaydir SON EGER Kosul tamamlanincaya kadar Ustteki algoritmaya gore asagidaki ornek SORTIERBEISPIEL 1 Pivot karsilastirma elementini bulmak icin Ilk once harfler sayilir Eger toplam tek ise 1 ekleyip ikiye bolunur 15 1 2 8 toplam cift ise ikiye bolunur 2 Bu durumda Pivot element B oluyor SORTIER B EISPIEL Burada ilk harf olan S son harf olan L ve orta harf olan B karsilastirilir Iclerinde ortanca olan deger her zaman orta degerdir Yani ornek su sekle donusur SORTIER L EISPIEB 3 Yukaridaki algoritma goz onunde bulundurulursa Kontrol ediliyor Soldaki element S Pivot L den buyuk mu Evet Sagdaki element B Pivot L den kucuk mu Evet Eger iki kosul da dogru ise ilk element S ile son element B yer degistirilir BORTIER L EISPIES Algoritmaya gore sadece ikisi evet ise degisim gerceklesir Soldaki element O Pivot L den buyuk mu Evet Sagdaki element E Pivot L den kucuk mu Evet Eger iki kosul da dogru ise ilk element O ile son element E yer degistirilir BERTIER L EISPIOS Soldaki element R Pivot L den buyuk mu Evet Sagdaki element I Pivot L den kucuk mu Evet Eger iki kosul da dogru ise ilk element R ile son element I yer degistirilir BEITIER L EISPROS Soldaki element T Pivot L den buyuk mu Evet Sagdaki element P Pivot L den kucuk mu Hayir Eger bir kosul yanlis ise soldaki element T sabit kaliyor sagdaki element P yi direkt saga yazilir BEIIER L EISPROS DIKKAT T algoritmaya su an dahil degil ta ki ikisi de evet oluncaya kadar Soldaki element T Pivot L den buyuk mu Evet Sagdaki element S Pivot L den kucuk mu Hayir Eger bir kosul yanlis ise soldaki element T sabit kaliyor sagdaki element S yi direkt saga yazilir BEIIER L EISPROS Soldaki element T Pivot L den buyuk mu Evet Sagdaki element I Pivot L den kucuk mu Evet Eger iki kosul da dogru ise element T ile element I yer degistirilir BEIIIER L ETSPROS Simdi T yazilabilir ikisi de evet Soldaki element E Pivot L den buyuk mu Hayir Sagdaki element E Pivot L den kucuk mu Evet Eger bir kosul yanlis ise soldaki element E sola yazilir sagdaki element E sabit kaliyor BEIIIER L ETSPROS Soldaki element R Pivot L den buyuk mu Evet Sagdaki element E Pivot L den kucuk mu Evet Eger bir kosul da dogru ise soldaki element R ile sagdaki element E sabit kaliyor BEIIIEE L RTSPROS Son asama Soldaki element R Pivot L den buyuk mu Evet Sagdaki element E Pivot L den kucuk mu Evet Eger bir kosul yanlis ise soldaki element R sola yazilir sagdaki element E sabit kaliyor BEIIIEE L RTSPROS B E I I I E E L R T S P R O S Ayni islemleri sagdaki ve soldaki bolumlere ayri ayri yapilir Sonuc soyle B E E E I I I L O P R R S S T Sozde Kodu Algoritmanin yalin bir sozde kod olarak gosterimi asagidaki gibidir function quicksort array var list less equal greater if length array 1 return array select a pivot value pivot from array for each x in array if x lt pivot then append x to less if x pivot then append x to equal if x gt pivot then append x to greater return concatenate quicksort less equal quicksort greater Diger Siralama AlgoritmalariKabarcik Siralamasi Birlestirmeli Siralama Secmeli Siralama Kokteyl Siralamasi Tarak SiralamasiKaynakca Computer History Museum 21 Haziran 2015 tarihinde kaynagindan arsivlendi KaynakcaHoare C A R Partition Algorithm 63 Quicksort Algorithm 64 and Find Algorithm 65 4 7 321 322 1961 Brian C Dean A Simple Expected Running Time Analysis for Randomized Divide and Conquer Algorithms Discrete Applied Mathematics 154 1 1 5 2006 R Sedgewick Implementing quicksort programs Comm ACM 21 10 847 857 1978 David Musser Introspective Sorting and Selection Algorithms Software Practice and Experience vol 27 number 8 pages 983 993 1997 Donald Knuth The Art of Computer Programming Volume 3 Sorting and Searching Third Edition Addison Wesley 1997 ISBN 0 201 89685 0 Pages 113 122 of section 5 2 2 Sorting by Exchanging and Second Edition MIT Press ve McGraw Hill 2001 ISBN 0 262 03293 7 Chapter 7 Quicksort pp 145 164 A LaMarca and R E Ladner The Influence of Caches on the Performance of Sorting Proceedings of the Eighth Annual ACM SIAM Symposium on Discrete Algorithms 1997 pp 370 379 Analysis of Quicksort 30 Eylul 2007 tarihinde Wayback Machine sitesinde CS 332 Designing Algorithms Department of Computer Science University of Wales Swansea Steven Skiena CSE 373 548 Analysis of Algorithms Department of Computer Science State University of New York at Stony Brook Conrado Martinez and Salvador Roura Optimal sampling strategies in quicksort and quickselect SIAM J Computing 31 3 683 705 2001 Jon L Bentley and M Douglas McIlroy Engineering a Sort Function SOFTWARE PRACTICE AND EXPERIENCE VOL 23 11 1249 1265 1993Dis baglantilarHizli Siralama videosu 6 Eylul 2010 tarihinde Wayback Machine sitesinde 32 programlama dilinde yazilmis Hizli Siralama ornekleri 1 Mart 2008 tarihinde Wayback Machine sitesinde