[]
quicksort vs. mergesort
arkadaslar son care olarak buraya basvuruyorum, hocalara sormaktan utaniyorum cünkü.. farki bir türlü göremiyorum.. aranizda konuyla ilgili olanlar varsa ve yardim ederlerse cok sevirinirim.. soruya gelince..
her ikisi de divide-and-conquer tipinde siralama algoritmasi olan quicksort ile mergesort arasindaki fark nedir? hayir O-Kalkül de de hem worst hem de best case lerde ikisi de ayni.. ikisi de bir pivot secip, rekursiv olarak bölünen parcalara geri dönüyor vs..
arada gercekten bir fark yok mu yoksa ben bir yerde cok büyük bir hata mi yapiyorum?
sevgiler, saygilar..
her ikisi de divide-and-conquer tipinde siralama algoritmasi olan quicksort ile mergesort arasindaki fark nedir? hayir O-Kalkül de de hem worst hem de best case lerde ikisi de ayni.. ikisi de bir pivot secip, rekursiv olarak bölünen parcalara geri dönüyor vs..
arada gercekten bir fark yok mu yoksa ben bir yerde cok büyük bir hata mi yapiyorum?
sevgiler, saygilar..
wikipedia'daki karşılaştırması şöyle,
Quicksort, however, is considered by many to be the fastest general-purpose sort algorithm. On the plus side, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
bizim öğrendiğimiz mergesort'un sıralı iki diziden sıralı bir dizi elde etmenin genel ismi olduğuydu. üstte wikipedia'da bir algoritma olduğu yazıyor.
bence üstte yazan özellikler içerisinde en önemlisi paralelliğe izin veriyor oluşu.
bir bakın,
en.wikipedia.org
Quicksort, however, is considered by many to be the fastest general-purpose sort algorithm. On the plus side, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
bizim öğrendiğimiz mergesort'un sıralı iki diziden sıralı bir dizi elde etmenin genel ismi olduğuydu. üstte wikipedia'da bir algoritma olduğu yazıyor.
bence üstte yazan özellikler içerisinde en önemlisi paralelliğe izin veriyor oluşu.
bir bakın,
en.wikipedia.org
- iron
(04.08.07 23:10:12)
quicksort yazması cok daha kolay geliyor bana
merge de divide ve de merge kismi icin taklalar attirabiliyorsun.
(tabi bunlar yazokulunda olan 1.sinif ogrencisi fikri degisir herhalde ilerde)
merge de divide ve de merge kismi icin taklalar attirabiliyorsun.
(tabi bunlar yazokulunda olan 1.sinif ogrencisi fikri degisir herhalde ilerde)
- kolpazan (04.08.07 23:50:28)
öncelikle sorunda iki hata var. merge de pivot yoktur array ortadan ikiye bölünür.her bir array bir eleman içerince bu arrayler ikişer ikişer birleştirilir. merge sort hep nlogn olarak çalışır.
quick te ise pivot seçilir. pivottan küçük olanlar sola büyük olanlar sağa atılır. daha sonra pivottan küçük ve bülyük elemanlar için kullanılır. o yüzden quick pivot tesadüfen mesela hep en küçükler olmuşsa n^2 olarak çalışır(worst case). ama ortalamada nlogn çalışır. n^2 çalışma riskine rağmen array kopyalama gereği olmadığından tercih edilir.
quick te ise pivot seçilir. pivottan küçük olanlar sola büyük olanlar sağa atılır. daha sonra pivottan küçük ve bülyük elemanlar için kullanılır. o yüzden quick pivot tesadüfen mesela hep en küçükler olmuşsa n^2 olarak çalışır(worst case). ama ortalamada nlogn çalışır. n^2 çalışma riskine rağmen array kopyalama gereği olmadığından tercih edilir.
- yoldan gecen adam (05.08.07 00:07:04)
evet simdi hatami gördüm ve utandim kendimden, resmen gözümün önündeymis..
o halde ikinci kisima gecmekte bir sakinca görmüyorum.. quicksort u O(nlogn) e olabildigince yaklastirmak icin bir ramdomQS olayi var.. burada pivot eleman ramdom olarak seciliyor ve bu sekilde worst-case den kacinmak hedefleniyor.. e peki secilen pivot eleman nasil hem random oluyor hem de mümkün mertebe en büyük elemanlar seciliyor da, en kücük elemanin sürekli secilmesi durumundaki O(n^2) engelleniyor? yani random nasil gidip de sürekli en büyük elemani secmeyi basariyor? random bunun neresinde?
o halde ikinci kisima gecmekte bir sakinca görmüyorum.. quicksort u O(nlogn) e olabildigince yaklastirmak icin bir ramdomQS olayi var.. burada pivot eleman ramdom olarak seciliyor ve bu sekilde worst-case den kacinmak hedefleniyor.. e peki secilen pivot eleman nasil hem random oluyor hem de mümkün mertebe en büyük elemanlar seciliyor da, en kücük elemanin sürekli secilmesi durumundaki O(n^2) engelleniyor? yani random nasil gidip de sürekli en büyük elemani secmeyi basariyor? random bunun neresinde?
- raizti (05.08.07 00:20:42)
random üç eleman seç. ortadakini pivot yap. sana kalmış. 5 7 falan seçsen daha iyi pivot olur da bu sefer de pivot seçerken zamandan kaybedersin.
- yoldan gecen adam (05.08.07 01:23:48)
1
