Yazan : Şadi Evren ŞEKER
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki orta noktada (mean) bulunan bir sayıyı seçerek diğer bütün sayıları bu orta sayıdan büyük veya küçük diye sınıflayarak sıralama yapmayı hedeflemektedir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır. Ayrıca bu seçilen orta noktaya eksen (pivot) adı da verilir çünkü bütün diğer sayılar bu sayının ekseninde sıralanacaktır.
Sıralanmak istenen verimiz:
5,7,2,9,6,1,4,7 (düzeltildi, Erol Bey'e teşekkürler)
olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.
Yukarıda verilen bu örnek dizinin sıralanması adım adım aşağıda anlatılmıştır:
1. adım, dizinin ortasındaki sayı bulunur. Bu örnekte 8 sayı olduğu için ortadaki sayı 4. elemandır. Bu elemanın değeri de 9’dur. Bu durum aslında biraz bahtsız bir durumdur çünkü tesadüfen dizideki en büyük sayıdır. Bu mesele 2. adımda ortaya çıkacaktır.
2.adım: Diziden 1.adımda seçilen sayıya göre dizideki bütün elemanları küçük veya büyük diye sınıflandır. Tabi 1. adımda şanssız bir şekilde en büyük sayı seçildiği için bütün sayılar 9’dan küçük olarak sınıflandırılacaktır.
5,7,2,6,1,4,7 (9)
3. adım: Sınıflandırılana küçük ve büyük dizileri tekrar hızlı sıralamaya ver. Yani 5,7,2,6,1,4,7 dizisini aynı adımlarla tekrar sıralıyoruz.
4. adım: eleman sayımız 7 ve ortadaki eleman 3. eleman olan 6 olur. Dizideki sayılar 6’dan büyük ve 6’dan küçük diye sınıflandırılırsa:
5,2,1,4 (6) 7,7
olarak iki grup elde edilir. Bu grupları da sıralamak üzere tekrar hızlı sıralama algoritmasına veririz. Dolayısıyla 5,2,1,4 sayıları ayrı ve 7,7 sayıları ayrı ayrı sıralanacaktır.
5. adım 5,2,1,4 sayılarının orta değeri 2’dir ve sınıflandırılırsa:
1 (2) 4,5 bulunur. Aynı zamanda diğer dizi olan 7,7 sıralanırsa sonuç değişmez ve 7,7 bulunur.
6. adım 1 sıralanırsa 1 ve 4,5 sıralanırsa 4,5 bulunur.
7.adım. Bu adımdan sonra artık birleştirme işlemine geçilebilir. Buna göre 6. adımda sıralanan değerleri birleştirirsek :
1,2,4,5 değerleri elde edilir.
8.adım: 4. adımdaki sayılar birleştirilirse 1,2,4,5,(6),7,7 sayıları elde edilir.
9.adım: 2. adımdaki sayılar birleştirilirse 1,2,4,5,6,7,7 (9) olarak dizinin sıralanmış hali elde edilir.
Bu algoritmanın JAVA dilindeki karşılığı aşağıdaki şekilde yazılabilir:
public static void quickSort(int A[],int p, int r)
{
int q;
if(p<r)
{
q=partition(A,p, r);
quickSort(A,p, q-1);
quickSort(A,q+1, r);
}
}
Görüldüğü üzere yukarıdaki kod özyineli (recursive) bir koddur ve kendi içerisinde orta değeri bulmak için partition adı verile harici bir fonksiyonu çağırmıştır. Bu fonksiyonun kodu da aşağıda verilmiştir:
public static int partition(int A[],int p, int r){
int tmp;
int x = A[r];
int i = p-1;
for(int j=p; j<=r-1; j++)
{
if(A[j]<=x)
{
i++;
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
}
tmp=A[i+1];
A[i+1]=A[r];
A[r]=tmp;
return i+1;
}
Yukarıdaki bu orta nokta bulmaya yarayan fonksiyonun en büyük özelliği tek bir dizi kullanarak bu dizi içerisindeki indisi döndürmeye çalışmasıdır. Bu yüzden hangi parça üzerinde orta nokta aradığını alt ve üst limitleri parametre alarak bulur. Bu parametreler koddaki p ve r değişkenleridir.
Hızlı sıralamanın algoritma karmaşıklığına bakıldığında O(nlogn) olarak bulunur çünkü üzerinde çalışılan dizi her adımda en fazla 2ye bölünmüştür (Big-O hesaplanırken en kötü ihtimalin hesaplandığını hatırlayınız) böylece sonuç dizisi olan 2şer elemanlı dizilere log2n adımda ulaşılabilir. Daha sonra her n eleman için sıralama yapıldığı ve her n eleman üzerinden geçildiği için bu değer çarpan olarak gelmekte ve sonuç nlog2n olarak bulunmaktadır.
Örnek görsel çalışma
Yapılan yorumlardan sonra hızlı sıralama algoritmasının çalışmasını görsel bir örnek üzerinden göstermeye karar verdim.
Sıralayacağımız sayılar 88,31,52,25,98,14,30,62,23,79 olarak verilsin
Yukarıdaki bu sayıları sıralamak için öncelikle ortadaki değer (pivot) bulunur. Bu değer sayılar arasından rast gele seçilebileceği gibi dizinin ilk elemanı, son elemanı gibi belirli bir yerdeki sayı olarak da atanabilir. Bu değer yukarıdaki kodda verilen p değişkeni ile gösterilen değerdir. Biz örneğimizde 52 olarak seçtiğimizi düşünelim:
Yukarıdaki şekilde gösterildiği üzere sayı rast gele olarak seçildikten sonra, diğer sayılar, bu seçilen rast gele sayıdan (52) büyük ve küçük olarak sınıflandırılır.
Görüldüğü üzere problem iki parçaya bölünmüş ve burada parçala fethet (divide and conquere) yaklaşımı kullanılmıştır. Artık problemin her iki alt kümesi ayrı ayrı yeniden hızlı sıralama algoritmasına verilecek ve bir önceki adımda olduğu gibi sayılar arasından rast gele bir sayı seçilerek problemi alt parçalara bölecektir:
Yukarıdaki son şekilde görüldüğü üzere problem bir önceki adımda bulunan parçaların alt parçalara bölünmesi ile daha küçük hale getirilmiştir. Burada rast gele olarak seçilen pivot sayıları ilk grup için 25 ve ikinci grup için 79 olmuştur.
Problem son kez alt adımlara bölünerek çözülür
Görüldüğü üzere son adımda son kümeler için yine pivot seçimi yapılmış ve 23, 31, 98 sayıları pivot olarak seçilmiştir. Problem bu aşamadan sonra çözülmüştür çünkü bu sayıların alt grupları tek elemanlı kümeler haline gelmiştir.
Ardından her küme kendi pivotunun solunda veya sağında olmasına göre yukarı doğru toplanır. Bu toplama işlemi yukarıkida şeklin en altında gösterilmiştir.
Diğer sıralama algoritmaları için bu bağlantıyı tıklayabilirsiniz.
Teşekkürler, gayet güzel ve anlaşılır bir anlatım olmuş.
Merhaba,
yararli bir makale, emeginiz icin tesekkürler.
Fakat gördügüm bir yanlislik var :
ilk verdiginiz deger :
Sıralanmak istenen verimiz:
5,7,2,9,6,1,3,7
(buradaki 3 degeri 2. Asamada 4 olarak yaziliyor)
hatayı düzelttim, ilginiz için teşekkürler
Teşekkürler hocam konuyu burdaki anlatım sayesinde daha iyi anladım fakat bir de c dilinde bir kod örneği yayınlayabilirseniz adım adım yorumlayarak tam oturcak konu hocam.İyi çalışmalar(aynı sıkıntı bubblesort,mergesort tada yapabilirseniz çok iyi olur hocam binary search te anlattığınız gibi.)
thank you bilgileriniz için ama akış diyagramınıda çizseydiniz daha iyi olurdu.
Merhaba, öncelikle elinize sağlık, gerçekten çok güzel bir anlatım olmuş. Fakat bir noktada takıldım, buradaki p,q ve r değerleri tam olarak neye karşılık geliyor acaba?
Teşekkürler…:)
5. adımdaki sıralama 1 (2) 4,5 değil 1 (2) 5,4 olacak
http://www.erbaaeml.k12.tr7
Bu kodda bulunna partition fonksiyonu verilen pivota göre diziyi ikiye bölmektedir.
Bu durumu açıklayan bir resmi yukarıdaki yazıya ekliyorum. Sanırım daha açıklayıcı olacak.
Acelya Hanıma uyarısından dolayı teşekkür ederim.
evet haklsınız sayıları 5. adımda yazarken 4 ile 5’in yeri değişmiş, yukarıdaki yazıda belirttiğiniz bu hatayı düzeltiyorum.
Mustafa Bey’e teşekkür ederim.
recursive algoritmalarda ogrenemedigim bir sorun var.yukarıda yazılan kodda quickSort(A,p, q-1);
isimli fonksiyon if(p
Sorunuzun cevabı, basitçe çalıştırmaz!
Bakın bahsettiğiniz kod parçasında, p ve r değerleri birer tam sayı ve dizi üzerindeki sıralanacak bölümün sınırlarını tutuyorlar.
Yani örneğin P=5 , r= 18 için (bu sayıları rast gele yazdım) kodumuz 5. ve 18. dizi elemanları arasındaki sayıları sıralamaya çalışıyor.
Video’da da anlatmaya çalıştım, hızlı sıralama algoritması, sıralamak istediği sayı bloğunun en sonuncu elemanını pivot olarak alabilir. (farklı sayılarda seçilebilir ama kodda ve video’da son elemanı kabul ettim) dolayısıyla buradaki p-r aralığı sıralanırken, partition isimli fonksiyonda görüldüğü üzere x değeri A[r] yani dizinin sıralanmasını istediğimiz alandaki son eleman oluyor.
Ardından p ile r arasında dönen bir for döngüsü ile bütün sayılar, bu x değerinden yani pivot değerinden büyük ve küçük olarak tasnif ediliyor.
Elbette bu sıralama işleminin sadece bir kısmı, ardından bu problem pivotun solundakiler ve pivot’un sağındakiler olarak alt gruplarda çözülecek. Yani bir seviye alta iniyoruz ve buradaki sayıları da sıralıyoruz. Bunun için quicksort fonksiyonunda bulunan diğer iki quicksort fonksiyonu çağırmasına ihtiyaç var. Bu fonksiyonlardan birisi p ile q-1 arasını (buradaki q değeri, pivotun dizideki kaçıncı sayı olduğu) diğer fonksiyon ise q+1 ile r arasını sıralıyor. Yani problem, p-r arasındaki sayılar iken iki alt probleme indiriliyor p-q ve q-r şeklinde iki grup sıralanıyor.
q elemanı iki gruba da dahil değil (birisinde q-1’e kadar diğerinde q+1’den sonraki sayılar sıralamaya dahil edilmiş) bunun sebebi q değerinin pivot olması ve sıralama işleminde herhangi bir alt gruba girmemesi gerektiğidir.
Sizin sorunuza dönecek olursak. Bahsettiğiniz if bloğuna pr durumlarında girmez. Bu durumlar da zaten sıralanacak eleman sayımız 0 veya sıfırdan küçük sayıda demektir ki bu da saçmadır. Yani en son 1 eleman sıralanabilir ve bu tek elemanın sıralanmış hali yine kendisidir. 1 elemandan az gruplar sıralanamaz ve bu if kontrolu bunu belirtir.
Peki neden böyle bir if kontrolüne ihtiyaç duyoruz? Sebebi basit, her pivota göre sağ ve sol şeklinde problemi böldükten sonra elaman sayımız azalıyor. En nihayetinde tek eleman kalıyor ve bu tek elemanı sıralayıp işlemi bitiriyoruz. Şayet bu if kontrollerini koymazsak sıralama işlemi hiç bitmez ve 0 veya eksi değerdeki elemanları da sıralamaya çalışırız.
Yani daha basit bir ifade ile, bu if kontollerinin amacı, tek elemandan az sayıdaki elemanları sıralamayarak, sıralama işleminin bu seviyede tamamlandığını belirtmektir.
Bu koşul terk edildiğinde de (yani çalıştırılmadığında) fonksiyon işlemini bitirerek çıkar ve bu fonksiyonu çağırmış olan bir üstteki fonksiyon işe kaldığı yerden devam eder.
hocam tam da sınava çalışırken sitenize rastladım,çok faydalı oldu,ellerinize sağlık..
hocam iyide benim anlamadığım bi durum var partition metodu recursif olarak diziyi parçalaması gerekiyo ama kodlarda bunu bir defa yapıyo…yrdımcı olursanız sevinrim….
Sanırım recursive fonksiyonlarla ilgili probleminiz var. Bu konuyu okuyun. Ama yine de şöyle anlatmaya çalışayım. Koddaki:
q=partition(A,p, r);
quickSort(A,p, q-1);
quickSort(A,q+1, r);
satırlarına bakacak olursanız, buradaki ilk satır, sizin de bahsettiğiniz üzere parçalama işlemi yapıyor. İkinci satır ise aynı fonksiyonu bir kere daha farklı paramatreler ile çalıştırıyor. Bu durumda aynı kod bir kere daha çalışıp bir kere daha partition işlemi yapılıyor. Ve bu işlem böylece sürüp gidiyor.
Kısacası özyineli fonksiyonlar (recursive functions) birer döngü gibi çalışır ve kod tekrarı yapar.
başarılar
emeğinize sağlık güzel bir çalışma ama hiç ilk elemanın pivot alınıp bir tur dönmesi sonunki sıralamaya raslamadım…
Hızlı sıralama algoritmasında amaç, sıralanmamış bir dizinin sıralanması ise bu durumda pivot değerinin rast gele alınması en sağlıklı yoldur. Şayet dizimiz rast gele değerlerden oluşuyorsa, dizideki alınan ilk değer, son değer veya ortadaki değer gibi sabit konumlar sonuçta rast gele sayılar verecektir. Dolayısıyla ilk sayının alınmasının bir sakıncası yoktur çünkü aslında rast gele bir sayı pivot olarak seçilmiş olur.
Şayet dizide bir ön sıralama işlemi yapılmışsa, örneğin dizi ters sıralı ise (biz küçükten büyüğe sıralamak isterken dizi büyükten küçüğe sıralıysa) bu durumda ilk elemanın alınması sıralama işlemini engellememkle birlikte kötü bir sıralama sonucu verecektir.
Pivot seçiminde en güzel yol, problemi tam ikiye bölen değerleri almaktır. Şayet bir şekilde problemi eşit iki parçaya bölen değeri bilyorsak bu değeri almak en iyi sonucu verir ancak ne yazık ki rast gele sayılardan oluşan bir dizi için bu değerin bulunması ayrıca bir yük getirecektir ve sıralama algoritmamızdan daha büyük bir maliyeti olacaktır.
Bununla birlikte parçalı sıralama problemleri (partial sorting problems) bulunmaktadır ve bu problemlere özgü çözümler üretilmektedir. Örneğin sizin bir veri tabanınızda onbin kayıt olsun ve sadece son bin tanesinin sıralı olmadığını biliyor olun. Bu gibi özel problemlerde özel çözümler bulunur.
Başarılar
hocam iyi günler emeğinize saygılar teşekkürler. Benim 1 sorum olacaktı;
Quick sort algortimasını visual studio c++ da nasıl uygulabiliriz butonla çalıştıracagız sadece arka plan kodunu doğru yazamadım. Teşekkürler iyi günler hocam…
Yukarıdaki kod, hem Dev-CPP hem de Visual Studio ile açılabilir. Kodu Visual Studio ile açmak için aşağıdaki bağlantıya bakmanızda yarar olabilir:
http://www.bilgisayarkavramlari.com/2010/05/01/dev-cpp-projelerinin-visual-studio-ile-acilmasi/
başarılar
merhaba hocam bu sorudaki bölme sıralamasını gösterebilirmiisniz acaba? sizin yönteminizle yaptım muhtemelen doğru fakat kendi hocamızın yaptığı partition sıralamasıyla uymuyor sayılar.o nedenle biraz kafam karıştı.
Illustrate the operation QUICK-SORT the array A.
A={9,7,8,3,1,2,5}
Gizem Hanım; sıralama algoritması tektir ancak pivot seçimi gibi bazı uygulama farklılıkları olabilir. Örneğin yukarıdaki yazıda açıkça belirttiğim üzere en baştaki, ortadaki veya sondaki sayı pivot seçilebilir. Sizin sorunuzu sondaki sayıyı pivot seçerek yapıyorum ancak hocanız da muhtemelen aynı algoritmayı farklı bir pivot seçerek yapmış ve doğru yapıyor olabilir.
9,7,8,1,2,5 -> pivot 5 için
1,2 – 5 – 9,7,8
pivot 2 için 1,2
pivot 8 için 7 – 8 – 9
kısacası aşağıdaki ağaç çıkar:
5 / 2 8 / / 1 7 9bu ağaç toplandığında ise sıralanmış bir şekilde
1,2,5,7,8,9 olarak sayılar bulunur.
başarılar
teşekkür ederim hocam.bu şekilde kolay görünüyor.hocamızın yaptığı çok daha uzun ve karışık geldi.
yani sanırım mantık olarak baştakiyle sondakini karşılaştırıp baştaki sayı büyükse yerlerini değiştiriyor.ama bölme kısmını tam çözemedim.buraya hocamızın çözümünü de yazıyorum.
9-7-8-3-1-2-5
5-7-8-3-1-2 9 (u ayırmış burda)
2-7-8-3-1-5 9
2-1-8-3-7-5 9
2-1-3-8-7-5 9
sonuncuyu 2-1-3 , 8-7-5 ve 9 olarak ayrılmışlar.
2-1-3 ü 1-2-3 olarak düzenlemiş 8-7-5 i de 5-7-8.
sonra 1-2-3 kısmını 1-2 ve 3 şeklinde bölmüş.aynı şekilde 5-7-8 i de 5 , 7-8 olarak.son olarakta hepsini ayırmış ztn.
tamam şimdi anlaşıldı. Hocanız kodlama kısmını anlatmış. Teoride benim anlattığım şekilde geçer ancak kodlarken tahmin edileceği üzere hafıza karmaşıklığı (memory complexity) O(n) olan algoritmadır. Yani n boyutundaki bir dizi için hafızada (RAM) n adet yer kaplar bu da n boyutunda bir dizi demektir.
O halde bir dizinin içerisinde yukarıda anlatılan ve pivota göre küçük ve büyük kümeleri nasıl oluşturabiliriz?
Bu sorunun çözümü dizinin iki ucunda birer gösterici (pointer) çıkarmak ve küçük/büyük durumuna göre yer değiştirmektir.
Bakın sizin dizilim için çözümü aşağıda anlatıyorum. Genelde bu çözümde ortadaki sayı pivot seçilir. Sizin durumunuzda pivot 3 oluyor
yukarıdaki şekilde dizinin iki ucunda A ve B isminde iki göstericimiz (pointer) olduğunu düşünün.
Amacımız seçtiğimiz pivottan büyükleri sağına küçükleri soluna taşımak.
O halde;
Şayet A>P durumu söz konusu ise bu değer P’nin soluna taşınacak.
Şimdi örneğe dönerek soruyu çözelim:
Sorgulayacağımız durumlar A>P ve B>P durumu. A>P olduğu için B ile yer değiştiriliyor ve B>P olduğu için B göstericimiz bir adım içeri ilerliyor.
Benzer şekilde A>P durumu var ve değiştirme işlemi yapıyoruz:
A
P ve B
P haline geldiği için birer adım ilerliyorlar:
2-1-8-3-7-5-9 A P BSon olarak A göstericisi pivota kadar ulaştığı için pivot ile yer değiştiriyor.
2-1-3-8-7-5-9
Yukarıdaki son durumda seçilmiş olan 3 pivotuna göre sayılar küçük (3’ün solunda) ve büyük (3’ün sağında) sıralanmış oluyor. Bu işlem benim yukarıdaki anlatımda geçen pivottan küçük ve büyük şeklinde bölme işlemidir. Sadece kodlama sırasındaki dizideki değişimler detaylıca gösterilmiştir.
Bundan sonraki adımlar ise özyineli olarak (recursive) 3’ün solunda ve sağındaki alt gruplar için uygulanmıştır.
hocam bunu 2 pivot ile yapma imkanımız var mıdır?
ör= *2 *11 7 10 1 30
sonunda 1 2* 7 10 11* 30 gibi?
c kodunu tam nasıl yazaibliriz acaba?
evet yapılabilir. C kodunda 3 bölge olacak. Örneğin ilk pivot a ve ikinci pivot b için a<b olması şartı ile;
x<a, a<x<b, ve b<x
şeklinde x herhangi bir sayı olmak üzere 3 ihtimal bulunacak bunlara göre sıralama yapılacak.
başarılar
zor gibi baya bir türlü yapamadım hocam :/
Hakan Bey;
Kodunuzu ve takıldığınız noktayı yollarsanız yardımcı olmaya çalışayım.
başarılar
şuan eksik baya çünkü tam olarak beceremedim yazmayı. sadece ilk 2 elemanı alıyorum onlar benm 2 tane pivotum oluyor onlar arasında büyük ise ilk pivot yer değiştirme yapıyorum ve yeni halde 2 pivota göre ayarlamam gerek ama takıldıgım yer cok hocam
#define A[10] void quicksort(int first, int last) { int lastS1,lastS2; int fUnknown; int temp; if(firstA[first+1])// first 0.index 1.pivotu ,first+1 1. index 2. pivot { temp= A[first]; A[first]=A[first+1]; A[first+1]=temp; } lastS1=first; for(fUnknown=first+1;fUnknown< =last;fUnknown++) { if(A[fUnknown]=A[first] && A[fUnknown] A[first+1]) { } } quicksort(first,lastS1-1); quicksort(lastS1+1,LastS2-1); quicksort(lastS1+1,last); } }buna bir bakarmısınız hocam ben böyle bir şey yaptım dogru çalışıyor acaba dogru bir algoritmamı quicksort için?
siz sorduktan sonra ben kodlamaya başlamıştım, aşağıdaki şekilde yazdım. Büyük ihtimalle çalışıyor, hatasını göremedim.
Yukarıdaki kodda, debug için kod eklemiştim, bunların kaldırıldığı sade hali aşağıda, ayrıca yorum da ekliyorum.
çok teşekkürler hocam farklı bir mantıkla yazılması benmde bakış açımı biraz olsun değiştirmem gerektiğini düşündüm. 🙂
çok yararlı oldu emeğinize sağlık 🙂
ya hocam gercekten harika anlatıyosunuz.
okulda hoca bunu 2 saat anlattı hiçbişey anlamadım valla ama burda bütün olayı anladım:)
gercekten harikasınız.
bu algoritma merge sort algoritmasi. qick sort algoritmasi boyle degil. quick sortta pivotlari ilerleterek ve sondaki ve basta sayiyi karsilastirip swap islemi yapilarak yapilir.
Şadi hocam son yazdığınızda p1 ve p2 diye iki pivot belirlemişsiniz. p1 den küçükler ve p2 den büyükler diye ayırmışsınız. Quıck Sort da 1 tane pivot seçip işlem yapmıyor muyuz. Yazdıgın kodu açıklar mısınız biraz. Teşekkür ederim kolay gelsin
Yorumların tamamını okursanız son yazılan kod, bir arkadaşın sorusu üzerine 2 pivot ile yapılmış özel koddur. Yani Hakan Bey, sorusunda bu kodu iki pivot ile yapmamızın mümkün olup olmayacağını sormuş ve bunun üzerine özel olarak yukarıdaki kodu yazmışız. Bu kod klasik quick sort algoritmasından farklıdır ve özel bir soru üzerine yazılmıştır.
Başarılar
şadi hocaam okul ödevim için yardımınıza ıhtıyacım var döngü içinde belırlenen 10 sayıyı sıralayan ekran cıktısında ılk bastakı hali ve sıralanmıs halini gosterecek sekılde yazabılırmısınız tekrar..
Merhaba hocam bu kodun javada uygulanması gösterirmisin ? kodu bir türlü dizi üzerinde uygulayamadım
Vidyolar kısa,öz,açık ve net teşekkürler hocam.
Çok güzel bir anlatım olmuş teşekkürler hocam.Umarım çalışmalarınızın devamı gelir:)
Hocam merhaba kodla ilgili bir sorum olacak.For içindeki if değerinde A[0] ile A[0] arasında yer değiştirme yapıyorsunuz.Şöyle açıklayayım p=0 değeri için i=-1 oluyor daha sonra j’ye p değerini atıyorunuz bu durumda j=0 oluyor kod if içine girdiğinde i++ yaparak i=0 olyor sonra a[i]ie a[j] arasında yer değiştirme yapıyorsunuz.Halbuki iki değerde aynı şey???? neden boşuna yer değiştiriyorsunuz.
Evet ihtimallere göre değiştirir. Mesela aşağıdaki durumda değiştirmez.
88,31,52,25,98,14,30,62,23,79
dizinin son elemanı ilk elemanından küçüktür dolayısıyla bahsettiğiniz gibi bir değişim olmaz ama
79,31,52,25,98,14,30,62,23,88
olsaydı değiştirirdi. Yani 79’u 79 ile değiştirirdi.
Bu durum algoritmanın çalışması sırasında ilerleyen zamanlarda da çıkabilir. Sonuçta iki adet gösterici gibi düşünebileceğimi i ve j değerini kullanıyoruz ve bu değerler dizinin üzerinde hareket ediyorlar, elbette bu hareket sırasında karşılaşmaları mümkün.
Çözüm olarak değişimi engellemek istiyorsanız ilgili kısmı aşağıdaki şekilde değiştirebilirsiniz:
if(A[j]< =x&&j!=i-1) { i++; tmp=A[i]; A[i]=A[j]; A[j]=tmp; } }Ancak performans artışı sağlayacağını kesin olarak garanti edemeyiz hatta bazı durumlarda menfi etkisi bile olabilir.
Başarılar
Teşekkürler hocam.İyi çalışmalar…
hocam peki Quick sortla pivot secerek sırasız bir listede sıralama yapmaksızın i. büyük sayıyı bulan programı nasıl yapabilirim.
işlem aslında bir sayıdan büyük kontrolü yapmak kadar basit. Yani bir döngü ile sayıların üzerinden geçtiğinizi ve büyük olanları ve küçük olanları (pivottan) kontrol ettiğinizi düşünebilirsiniz. Yazıdaki kodda (partition fonksiyonu) bunu yapan bir döngü bulunuyor. Döngüde ilave olarak sayılar uygun şekilde yer değiştiriliyor (swap).
Başarılar
Sırasız listede, sıralama yapmaksızın, listede ki i. buyuk sayıyı bulan programı/fonksiyonu/algoritmayı bulamadım yardımcı olabilir misiniz?
Sorunuza genel bir cevap vermem gerekirse, sırasız bir listede i. büyük sayıyı bulmak aslında ilk i sayıyı sıralamaktır. Örneğin 1. en büyük sayıyı (yani bütün listedeki en büyük sayıyı arıyorsanız) aslında sadece 1 sayı sıralıyorsunuz demektir. Veya n elemanlı bir sırasız listede, n. en büyük elemanı arıyorsanız aslında n elemanı da sıralıyorsunuz demektir.
Buradaki önemli nokta sizin sıralanmış bütün listeye ihtiyacınız olmayıp sadece 1 sayı arıyor olmanız ve bu durumun da size bazı hız avantajları sağlaması. Mesela n elemanlı bir listedeki n. en büyük elemanı aramak aslında en küçük elemanı aramak olarak da yorumlanabilir. Dolayısıyla sıralama işlemi baştan veya sondan yapılarak aranan sayıya ulaşılması mümkündür.
Problem için herhangi bir sıralama algoritması da kullanılabilir. Örneğin kabarcık sıralaması (bubble sort) kullanarak ilk i elemanı sıralarsanız (ki bu da en kötü ihtimalle i adet geçiş (pass) demektir) i. büyük sayıyı bulmuş olursunuz. Veya herhangi başka bir sıralama algoritması ile de bu işlemi yapabilirsiniz.
Burada kullanacağınız algoritma aslında herhangi bir sıralama algoritması olabilir ama bu yazının konusu olan ve parçala fethet (divide and conquere) yaklaşımı kullanan hızlı sıralama (quick sort) veya birleştirme sıralaması (merge sort) gibi algoritmaların performansı, doğrusal sıralama algoritmalarına (bubble sort, insertion sort, shell sort gibi) daha kötü olacaktır. Bunun sebebi parçala fethet yaklaşımındaki algoritmaların bütün sıralama işlemi bitmeden durmamasıdır. Yani sonuca ulaşmak için algoritmanın bütün diziyi sıralaması gerekir, oysaki doğrusal sıralama algoritmalarında i. elemana ulaşıldığında listenin gerisi sıralanmadan durdurma yapılabilir.
Kısacası en sevdiğiniz sıralama algoritmasını i. elemana ulaşana kadar kullanarak en büyük i. elemana ulaşabilirsiniz, ufak bir hile olarak da i sayısı n/2’den büyükse (n – i). en küçük sayıyı bulmayı deneyebilirsiniz.
Anladım hocam teşekkür ederim .Bunu bir kod üzerinde anlatabilir misiniz acaba?
Hoca kodu sen yaz diye konuyu anlatmış zaten. Yazsa direkt yazardı Uğurcum.
şimdi algortima karmaşıklığı o(nlogn) mi ? yoksa o(nlog2n) mi ?
algoritma karmaşıklıklarını göstermek için kullanılan big-oh notasyonu için sabit sayıların önemi yoktur. Örneğin 2n gibi bir sayı yerine n yazılabilir veya log2n yerine logn yazılabilir. Burada ifade edilen değer logaritmik çalıştığıdır. Algoritmanın logaritmik çalışmasını göstermek için log2n yazılmış ancak literatüre bakarsanız nlogn şeklinde geçtiğini görürsünüz. Big-o gösteriminde ikisi de aynı şeyi ifade eder.
merhaba hocam burda verdiğiniz örnekte 5 7 2 9 6 1 4 7 pivotu baştakini seçersek soldaki ve sağdakini karşılaştırdığımızda 7 ve 7 birbirine eşit olduğu durumda exchange etmiyoruz fakat 7 5 ten büyük olduğu için diğer 7 nin yanına mı geçmesi gerekiyor? teşekkür ederim
hocam quicksort’ta “ortadaki” değeri almak gerektiğinden bahsederken “mean” demişsiniz ama mean “ortalama” değerdir. Yani sumOfAllElements/numberOfElements demektir. Ortadaki değerden bahsediyorsak “middle of array” daha uygun olabilir.
elinize sağlık.