binary-search

Algoritma Dersleri – Quick Sort

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Quick Sort algoritmasını anlatmaya çalışacağız.

Quick Sort Nedir?

Quick Sort, bilgisayarda tuttuğumuz verileri belli bir düzene göre sıralamamızı sağlayan bir algoritmadır. Belli bir düzen diyorum çünkü her zaman küçükten büyüğe veya büyükten küçüğe sıralamak bizim istediğimiz sonuca ulaşmaz. Ancak basit ve anlaşılması kolay olsun diye bu örneğimizde küçükten büyüğe doğru sıralayacağız.

 

quick

 

Quick Sort Nasıl Çalışır?

Amacımız belli. Ancak bu algoritmayı diğer sıralama algoritmalarından farklı kılan durum probleme yaklaşma biçimidir. Biraz bahsetmek gerekirse, biz her bir adımda rastgele bir eleman seçiyoruz. Daha sonra diziyi baştan sona gezerek bu elemandan küçük olanları sola, büyük olanları sağa atıyoruz. Böylelikle seçtiğimiz elemandan küçük bütün sayılar solda, büyük sayılar ise sağda kalmış oluyor.

Bir örnek dizi vererek adım adım ne yaptığımızı inceleyelim:

Başlangıç: 7 2 3 6 10 1 5

(5) elemanını seçelim.

1. Adım: 2 3 1 (5) 10 7 6

Gördüğümüz gibi 5’ten küçükler solda, büyükler sağda kalmış oldu.
Bu adımda bir çıkarım yapalım. Biz artık biliyoruz ki soldaki hiçbir eleman 5’in sağına geçemez çünkü hepsi 5’ten küçük olduğundan 5’in sağ tarafında yer alması mümkün değildir. Aynı sebepten ötürü 5’ten büyük elemanların 5’in soluna geçemeyeceğini de rahatlıkla söyleyebiliriz.

Böylelikle artık diziyi ikiye bölebiliriz. {2,3,1} olan diziyi ayrıca sıralayıp yanına (5) ekleyip onun yanına da {10,7,6} dizisini sıralarsak cevaba ulaşmış oluruz.

Burada da Divide and Conquer dediğimiz yaklaşım bizi karşılıyor.

Divide and Conquer:

Türkçesi Böl ve Fethet olan Divide and Conquer, bir algoritmadan öte problemi çözmeye yönelik yapılan yaklaşımdır. Kısaca şöyle açıklayabiliriz ki elimizdeki problemi uygun bir şekilde benzer problemlere parçalıyoruz. Daha sonra bu parçaları kendi içerisinde ayrı ayrı çözüyoruz ve bütün ufak parçaları çözdükten sonra bu parçaları birleştirerek gerçek çözüme ulaşıyoruz.

Şimdi Quick Sort’a geri dönelim. Üstteki paragraftan da anlaşılacağı üzere bütün diziyi tek seferde çözmek yerine diziyi ikiye böldük. Bu iki parçayı Quick Sort fonksiyonuna tekrar gönderiyoruz. Belli işlemlerden geçen bu iki parça bize sıralanmış bir şekilde geliyor. En son olarak da bu iki parçayı birleştiriyoruz. Ve doğru sonuca ulaşmış oluyoruz.

Başlangıç: 7 2 3 6 10 1 5

1. Adım: 2 3 1 (5) 10 7 6

2. Adım: (1) 3 2 5 10 7 6

3. Adım: 1 (2) 3 5 10 7 6

4. Adım: 1 2 3 5 (6) 7 10

5. Adım (Sonuç) : 1 2 3 5 6 7 (10)

C/C++ Kodu:

int partition(int arr[], int low, int high)
{
    int pivot = arr[high]; 
    int i = (low - 1);  
 
    for (int j = low; j <= high- 1; j++)
    {
        
        if (arr[j] <= pivot)
        {
            i++;    
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
 
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

 

Kod Analizi:

Fonksiyonları açıklamak gerekirse alttaki quickSort fonksiyonu bir dizi ve bu dizinin sıralanacak aralığını parametre olarak alıyor. Gönderdiği partition fonksiyonu ise bir eleman seçerek diziyi bu elamanın küçükleri sola, büyükleri sağa gelecek şekilde yeniden şekillenmesini sağlıyor. Daha sonra Böl ve Fethet yöntemini kullanarak önce sol tarafı sıralıyor, sonra sağ tarafı kendi içinde sıralıyor.

Karmaşıklık Hesabı:

Her seferinde diziyi ikiye bölmeye çalışıyoruz ve o ikiliyi kendi içersinde sıralıyoruz bu nedenle yapacağımız bölme sayısı yaklaşık log2(N) partition fonksiyonundan da gelen toplamda N işlemdir yani algoritmanın karmaşıklığı O(N log2(N))‘dir. Ancak burada dikkat etmemiz gereken bir nokta var ki seçeceğimiz pivot elemanı her zaman en ortada olmadığı için her seferinde diziyi tam ortadan böleceğimizi garanti edemiyoruz. En kötü ihtimalle çok düşük ihtimal olsa da N^2 karmaşıklığa gitme ihtimalini göz ardı etmemeliyiz. Bunu engellemek için yapılabilecek en kolay çözüm bize verilen diziyi her ihtimale karşı rastgele bir şekilde permütasyonunu alıp Quick Sort fonksiyonuna göndermeliyiz.

Şimdi diğer dillerdeki kodu paylaşarak yazımıza son verelim.

Java:

class QuickSort
{
   
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high]; 
        int i = (low-1); 
        for (int j=low; j<high; j++)
        {
           
            if (arr[j] <= pivot)
            {
                i++;
 
                
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
 
        
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
 
        return i+1;
    }
    
    void sort(int arr[], int low, int high)
    {
        if (low < high)
        {
           
            int pi = partition(arr, low, high);
 
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

Python:

def partition(arr,low,high):
    i = ( low-1 )        
    pivot = arr[high]     
 
    for j in range(low , high):
 
       
        if   arr[j] <= pivot:
         
      
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
 
    arr[i+1],arr[high] = arr[high],arr[i+1]
    return ( i+1 )
 
def quickSort(arr,low,high):
    if low < high:
 
      
        pi = partition(arr,low,high)
 
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

Okuduğunuz için teşekkür ederim umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.

107

Hasan Bal

Competitive Programmer

Web Developer

6 Yorum

  • 1. adım nasıl 2 3 1 (5) 10 7 6 oldu açıklarmısınız? o kısımı hiç anlatmamışsınız.

    • Rastgele pivot secimi yapiyoruz. Bu pivotu 5 secmisiz. Daha sonra 5’den kucuk olanlari 5’in soluna, buyuk olanlari da sagina atiyoruz.

        • stack içine at ilk elemandan başlayarak sonra çıkarıp bir array içine ekleyebilirsin sırayla

        • Yığın (ingilizcesini yazmama site izin vermiyor) içine at ilk elemandan başlayarak sonra çıkarıp bir liste içine ekleyebilirsin sırayla

  • Algoritmalar sınavına çalışıyorum ve sürekli yazdığınız içerikleri okuyorum. Teşekkür ederim, emeğinize sağlık. Gayet faydalı bir içerikler üretmişsiniz.

Haftalık Bülten

Mobilhanem'de yayınlanan dersleri haftalık mail almak ister misiniz?