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.

Yorumlar

  1. ERol

    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)

  2. Bekir

    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.)

  3. Acelya

    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...:)

  4. Şadi Evren ŞEKER Article Author

    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.

  5. Şadi Evren ŞEKER Article Author

    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.

  6. esra

    recursive algoritmalarda ogrenemedigim bir sorun var.yukarıda yazılan kodda quickSort(A,p, q-1);
    isimli fonksiyon if(p

  7. Şadi Evren ŞEKER Article Author

    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.

  8. abdullah

    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....

  9. Şadi Evren ŞEKER Article Author

    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

  10. ali

    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...

  11. Şadi Evren ŞEKER Article Author

    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

  12. deniz

    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...

  13. gizem

    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}

  14. Şadi Evren ŞEKER Article Author

    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:

    1
    2
    3
    4
    5
    
           5
          / 
         2   8
        /   / 
       1   7   9

    bu ağaç toplandığında ise sıralanmış bir şekilde

    1,2,5,7,8,9 olarak sayılar bulunur.

    başarılar

  15. gizem

    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.

  16. Şadi Evren ŞEKER Article Author

    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

    1
    2
    
    9-7-8-3-1-2-5
    A     P     B

    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;

    • A göstericisi P'den küçük olduğu sürece sayıyı kabul edip P'ye doğru ilerleyecek.
    • B göstericisinin değeri A'dan büyük olduğu sürece sayıyı kabul edip P'ye doğru ilerleyecek.
    • Şayet B

      Şayet A>P durumu söz konusu ise bu değer P'nin soluna taşınacak.

    Şimdi örneğe dönerek soruyu çözelim:

    1
    2
    
    9-7-8-3-1-2-5
    A     P     B

    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.

    1
    2
    
    5-7-8-3-1-2-9
    A     P   B

    Benzer şekilde A>P durumu var ve değiştirme işlemi yapıyoruz:

    1
    2
    
    2-7-8-3-1-5-9
      A   P B

    A

    P ve B

    P haline geldiği için birer adım ilerliyorlar:

    1
    2
    
    2-1-8-3-7-5-9
        A P B

    Son 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.

  17. hakan

    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?

  18. Şadi Evren ŞEKER Article Author

    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

  19. hakan

    ş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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    #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>=A[first] && A[fUnknown] <A> A[first+1])
    		  {
     
     
    		  }
    		}
     
     
     
     
              quicksort(first,lastS1-1);
    		  quicksort(lastS1+1,LastS2-1);
              quicksort(lastS1+1,last);
     
         }
     
    }
  20. hakan

    buna bir bakarmısınız hocam ben böyle bir şey yaptım dogru çalışıyor acaba dogru bir algoritmamı quicksort için?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    
    #include <stdio.h>
    #include <stdlib.h>
    #define N 9
    int A[N];
     
    void quicksort(int a, int b);
     
    int main()
    {
      int i;
     
      A[0]=5;
      A[1]=20;
      A[2]=1;
      A[3]=11;
      A[4]=9;
      A[5]=17;
      A[6]=4;
      A[7]=24;
      A[8]=21;
      /*A[9]=5;*/
     
      printf("nn");
     
      quicksort(0,8);
     
       for(i=0;i<9;i++)
          printf("%d ",A[i]);                    
        printf("nn");
     
      return 0;
    }
     
     
    void quicksort(int firstarrray, int lastarrray)
    {
     
         int lastS1,lastS2,last;
         int fUn,fr,sc;
         int temp,j,i;
     
     
    	 if(firstarrray<lastarrray)
         {
    		 fr=A[firstarrray];
    		 sc=A[firstarrray+1];
     
     
    		 if(A[firstarrray]>A[firstarrray+1])
    		 {
    			 temp= A[firstarrray];
    			 A[firstarrray]=A[firstarrray+1];
    			 A[firstarrray+1]=temp;
    		 }
     
    		last=firstarrray+1;
             //-----------------------------------
     
            for(fUn=last+1;fUn<=lastarrray;fUn++)             
            {
              if(A[fUn]< fr && A[fUn]< sc)
              {
     
    			 i=fUn;
                               while(i>0 && A[i]<A[i-1])
    			 {
    			         temp=A[i];
    				 A[i]=A[i-1];
    				 A[i-1]=temp;
     
    				 if(A[i]==fr)
    					 break;
    				 i--;
    			 }
              }
    		  else if(A[fUn] >= fr && A[fUn] < sc)
    		  {
    			  i=fUn;
                             if(i>0 && A[i]<A[i-1])
    			 {
                                     temp=A[i];
    				 A[i]=A[i-1];
    				 A[i-1]=temp;
     
    			 }
    		  }
    		  else if(A[fUn] >= sc && A[fUn]> fr)
    		  {
                       i=fUn;
                       if(i>0 && A[i]<=A[i-1] && i<= lastarrray)
    			 {
                     temp=A[i];
    				 A[i]=A[i-1];
    				 A[i-1]=temp;
     
    			}
     
    		  }
    		}
     
    		for(j=0;j<=lastarrray;j++)
    		{
    			if(A[j]==fr)
    				lastS1=j;
     
    			if(A[j]==sc)
    				lastS2=j;
    		}
     
     
     
     
              quicksort(firstarrray,lastS1-1);
    	  quicksort(lastS1+1,lastS2-1);
              quicksort(lastS2+1,lastarrray);
     
         }
     
    }
  21. Şadi Evren ŞEKER Article Author

    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.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    
    #include <conio.h>
    #include <stdio.h>
    void degistir(int A[], int a,int b){
         int temp = A[a];
         A[a] = A[b];
         A[b] = temp;     
    }
    void quickSort(int A[],int p1,int p2){
         int bas=p1;
         int bit=p2;
         printf("n giriyor bas: %d bit : %d n",bas,bit);
         if(p1<p2-2){
             for(int i = p1;i<p2;i++){
                     printf("i: %d, a[i] : %d p1: %d a[p1] : %d p2:%d a[p2]:%d  --- ",i,A[i],p1,A[p1],p2,A[p2]);
                                for(int i = 0;i<10;i++){
                                printf("%d",A[i]);
                        }printf("n");
                     if(A[i]<A[p1]){
                                    degistir(A,i,p1+1);
                                      for(int i = 0;i<10;i++){
                                printf("%d",A[i]);
                        }printf("n");
                          degistir(A,p1,p1+1); 
                          p1++;         
                     }
                     else if(A[i]>A[p2]){
                          degistir(A,i,p2-1);
                            for(int i = 0;i<10;i++){
                                printf("%d",A[i]);
                        }printf("n");
                          degistir(A,p2-1,p2);
                          p2--;
                     }
                      for(int i = 0;i<10;i++){
                                printf("%d",A[i]);
                        }printf("n");
             }
     
       if(p2<p2-1){
         degistir(A,p2,p2-1);
         p2--;
         }
         if(p1>p1+1){
         degistir(A,p1,p1+1);
         p1++;
         }
     
           for(int i = 0;i<10;i++){
                                printf("%d",A[i]);
                        }printf("n-----------n");
         quickSort(A,bas,p1);
         quickSort(A,p1,p2);
         quickSort(A,p2,bit);
         }
    }
    int main(){
        int a[10]={3,8,0,7,1,6,9,2,4,5};
        quickSort(a,0,9);
        for(int i = 0;i<10;i++){
                printf("%d",a[i]);
        }
        getch();
    }
  22. Şadi Evren ŞEKER Article Author

    Yukarıdaki kodda, debug için kod eklemiştim, bunların kaldırıldığı sade hali aşağıda, ayrıca yorum da ekliyorum.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    
    #include <conio.h>
    #include <stdio.h>
    void degistir(int A[], int a,int b){
         // klasik swap fonksiyonu 2 degerin yerini degistirir.
         int temp = A[a];
         A[a] = A[b];
         A[b] = temp;     
    }
    void quickSort(int A[],int p1,int p2){
         int bas=p1;
         int bit=p2;
         //siralancak araligin hudutlarini aliyoruz.
         if(p1<p2-2){
         // sayet iki siralancak deger arasinda tek eleman varsa
         // tek eleman zaten siralidir, siralama.
             for(int i = p1;i<p2;i++){
                     // araligi iteratif donuyoruz.
                     if(A[i]<A[p1]){
                          // pivot 1'den kuculeri alta aliyoruz
                          degistir(A,i,p1+1);        
                          degistir(A,p1,p1+1); 
                          p1++;         
                     }
                     else if(A[i]>A[p2]){
                          // pivot 2'den buyukleri yukarı alıyoruz
                          degistir(A,i,p2-1);
                          degistir(A,p2-1,p2);
                          p2--;
                     }
                     // pivot1 ve 2 arasındakiler aralarında kalıyor
             }
             // yer değiştirirken bir yanına alıp ilerlettiğim için
             // kodda bir defect oldu, belki daha akılcı çözülebilir.
             if(p2<p2-1){
                 degistir(A,p2,p2-1);
                 p2--;
             }
             if(p1>p1+1){
                 degistir(A,p1,p1+1);
                 p1++;
             }
             // defecti de hallettikten sonra recursive olarak 3
             // aralığı fonksiyona veriyoruz.
             quickSort(A,bas,p1);
             quickSort(A,p1,p2);
             quickSort(A,p2,bit);
         }
    }
    int main(){
        int a[10]={3,8,0,7,1,6,9,2,4,5};
        quickSort(a,0,9);
        for(int i = 0;i<10;i++){
                printf("%d",a[i]);
        }
        getch();
    }
  23. hakan

    ç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. 🙂

  24. veli kayı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.

  25. burak

    bu algoritma merge sort algoritmasi. qick sort algoritmasi boyle degil. quick sortta pivotlari ilerleterek ve sondaki ve basta sayiyi karsilastirip swap islemi yapilarak yapilir.

  26. Orhun

    Ş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

  27. Şadi Evren ŞEKER Article Author

    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

  28. gökçe özen

    ş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..

  29. aynur

    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.

  30. Şadi Evren ŞEKER Article Author

    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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
     
            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

  31. ela

    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.

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      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

  32. ugur

    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?

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      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.

    1. Şadi Evren ŞEKERŞadi Evren ŞEKER

      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.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ altı = 10