Sıralama Algoritmaları -1 / Bubble Sort Algorithm

CyberXhackk

Kıdemli Üye
13 Mar 2016
3,132
10
C/C++ Dev.
Bubble Sort Algorithm



CjK4Ni.png

Bubble Sort Algoritmasını herhangi bir listeyi sıralamak için kullanabiliriz. Temel mantığı elemanları 2-2 şeklinde alarak kendi aralarında karşılaşmaktan geçer. N terimli bir arrayimiz var diyelim. Bu arrayi küçükten büyüğe sıralamak istediğimizi düşünelim. Bu algoritmaya göre önce 1. ve 2. elemanı karşılaştırmamız gerekiyor. Eğer 1. eleman 2. elemandan büyük ise elemanları çaprazlama yer değiştiriyoruz. Değilse olduğu gibi bırakıyoruz ve bir sonraki tura atlıyoruz. 2. ve 3. elemanı karşılaştırıyoruz. 2. eleman 3. elemandan büyük ise yine yer değiştiriyorlar. Değilse sonraki adım. Böyle son elemana kadar gidersek döngümüzün N-1 defa döneceğinin farkına varabiliriz.

Örnek Liste:

Kod:
[5,2,4,3]

5 ile 2 yi karşılaştırıyoruz. 5 sayısı 2 sayısından büyük mü? Evet büyük.. O zaman terimleri yer değiştir.. 2,5 oldu yeni arrayimiz.

Kod:
[2,5,4,3]

1. ve 2. elemanı karşılaştırdık şimdi 2. ve 3. elemanı ele alalım. 5 sayısı 4 sayısından büyük mü? Cevabımız yine evet. Yer değiştirip devam ediyoruz.

Kod:
[2,4,5,3]

3 ve 4. elemanı karşılaştırcak olursak yine 5 sayısının 3 sayısından den büyük olduğunu görüyoruz ve döngüye devam ediyoruz.

Kod:
[2,4,3,5]

Gördüğümüz üzere elemanlar bitti. Daha fazla devam edemiyoruz. Fakat döngümüz hala sırasız biçimde..

Gözle görüleceği üzere bu yaptığımız kontrol işlemini 2 defa daha yapmamız gerekiyor 4 ve 3 ün yerini değiştirmemiz için. Fakat bu her array için 1 olmak zorunda değil daha karışık bir liste verilebilirdi. O yüzden işimizi riske atıp 2 defa daha kontrol et diyemeyiz. Baştan sona N-1 adımda gelebiliyoruz. Bu sebepten dolayı bu yaptığımız döngüyü N-1 defa çalıştırmak zorundayız.


Örnek olarak Pseudo Code yazıyorum.
Kod:
for(n-1 defa dön)
    for (n-1 defa dön)
        if a>b: a , b = b , a
        else: continue

Bu yazdığımız kod ne kadar sırasız liste verirsek verelim listeyi sıralayıp bize geri döndürecektir.

Şimdi bu kodu C diline dönüştürelim..


Kod:
#include <stdio.h>
int main()
{
    int n;
    printf("Sıralamak istediğiniz array kaç elemanlı :"); // [B][COLOR="Sienna"][SIZE="4"]Burada array oluşturmak için input alıyoruz[/SIZE][/COLOR][/B]
    scanf("%i", &n);
    int list[n];
    for (int i = 0; i < n; i++){                 //  [B][COLOR="Sienna"][SIZE="4"]Burada dizinin tek tek elemanlarını input alıyoruz[/SIZE][/COLOR][/B]
        int sayi;
        printf("%i. Eleman : ",i + 1);
        scanf("%i", &sayi);
        list[i] = sayi;    
    }   
    for (int j = 0; j < n - 1; j++)  // [B][COLOR="Sienna"][SIZE="4"]Burada dıştaki döngümüz başlıyor.[/SIZE][/COLOR][/B]
    {
        for (int i = 0; i < n - 1; i++)   // [B][COLOR="Sienna"][SIZE="4"]Burada içteki döngümüz başlıyor.[/SIZE][/COLOR][/B]
        {
            if (list[i] > list[i+1])    // [B][COLOR="Sienna"][SIZE="4"]Burada arrayin 2 elemanı arasında karşılaştırma yapıyoruz.[/SIZE][/COLOR][/B]
            {   
                int gecici = list[i+1]; // 4
                list[i+1] = list[i];
                list[i] = gecici;
            }
            else
            {
                continue;
            }  
        }
    }
    for (int i = 0; i < n; i++)    // [B][COLOR="Sienna"][SIZE="4"]Burada döngünün son halini yazıyoruz..[/SIZE][/COLOR][/B]
    {
        printf("%i - ", list[i]);
    }   
}

NOT: 2 tane for döngüsü kullanmak yerine recursive fonksiyon da kullanılabilir. Onun kodunu da yazdım merak edenler bakabilirler.

Kod:
#include <stdio.h>
int* sortOfArray(int sayac, int n, int arr[]);
int main()
{
    int sayac = 0;
    int n;
    printf("Arr kaç elemanlı :");
    scanf("%i",&n);
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        printf("%i. Eleman", i+1);
        scanf("%i", &arr[i]);
    }
    
    for (int i = 0; i < n; i++)
    {
        printf("%i ",sortOfArray(sayac,n,arr)[i]);
    }
    
    return 0;  
}


int* sortOfArray(int sayac, int n, int arr[])
{
    
    for (int i = 0; i < n - 1; i++) // 3,2,5,4 -> 2,3,5,4
    {
        if (arr[i] > arr[i+1])
        {
            int gecici = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = gecici;
        } 
       
    }
    
    if (sayac==n)
    {
        return arr;
    }
    
    return sortOfArray(sayac+1,n,arr);      
}

Bubble Sort algoritmasının yanısıra bir çok sort algoritmaları mevcuttur. En hızlı çalışan sıralama algoritması Quick Sort Algorithmdir.



 

Anonim6

Yeni üye
29 Şub 2012
0
5
Neden yok dediniz Quick Sort Algorithm için :)
epey bariz aslında. hepimizin elinin altında arama motorları, internet erişimi var zannedersem, yani sanırım. quicksort kime, neye göre, neden ve hangi durumda en hızlısıymış, bu soruları yanıtlamadan nasıl net bir biçimde ismine kanarak hızını betimliyorsunuz hayret ettim.
 

leaks

Katılımcı Üye
29 Eki 2018
869
1
Biraz eksik olmuş, Büyük O gösterimine (Big O notation) de değinseydiniz. Ayrıca 'En hızlı sıralama algoritması Quicksort' cümlesi yanlış olmuş.
 

CyberXhackk

Kıdemli Üye
13 Mar 2016
3,132
10
C/C++ Dev.
Biraz eksik olmuş, Büyük O gösterimine (Big O notation) de değinseydiniz. Ayrıca 'En hızlı sıralama algoritması Quicksort' cümlesi yanlış olmuş.

Büyük O gösterimi biraz matematik temeline dayanıyor. Ben burada sadece algoritmanın mantığını anlatmaya çalıştım kendi cümlelerimle. İnternette araştırdığıma göre ve Harvard CS50 introduction to Computer Science dersine göre de en hızlı arama algoritması olarak Quick Sort Algoritması gösteriliyor. Yanlış bir cümle ise doğru bir kaynak gönderebilir misiniz?
 

leaks

Katılımcı Üye
29 Eki 2018
869
1
Büyük O gösterimi biraz matematik temeline dayanıyor. Ben burada sadece algoritmanın mantığını anlatmaya çalıştım kendi cümlelerimle. İnternette araştırdığıma göre ve Harvard CS50 introduction to Computer Science dersine göre de en hızlı arama algoritması olarak Quick Sort Algoritması gösteriliyor. Yanlış bir cümle ise doğru bir kaynak gönderebilir misiniz?

Sıralama algoritmalarının hızları verilen girdiye göre değişkendir. Quicksort, en iyi durumda O(n.log(n)) zaman karmaşıklığına sahip, merge sort ve heap sort da aynı ancak quicksort hem kararlı hem de inplace sıralama yapıyor. Bu özellikleri yüzünden quicksort çokça kullanılır. Ancak belirli durumlarda (sıralanacak verilerin eşit uzunlukta olması gibi) radix sort (O(n+K)) gibi algoritmalar daha hızlı çalışabilir.
 

CyberXhackk

Kıdemli Üye
13 Mar 2016
3,132
10
C/C++ Dev.
Sıralama algoritmalarının hızları verilen girdiye göre değişkendir. Quicksort, en iyi durumda O(n.log(n)) zaman karmaşıklığına sahip, merge sort ve heap sort da aynı ancak quicksort hem kararlı hem de inplace sıralama yapıyor. Bu özellikleri yüzünden quicksort çokça kullanılır. Ancak belirli durumlarda (sıralanacak verilerin eşit uzunlukta olması gibi) radix sort (O(n+K)) gibi algoritmalar daha hızlı çalışabilir.

O zaman cümlem yanlış değil eksik diyebiliriz, belirli durumlar hariç en hızlı sıralama algoritması Quick Sort Algorithm yargısı doğru oluyor.
 

Anonim6

Yeni üye
29 Şub 2012
0
5
O zaman cümlem yanlış değil eksik diyebiliriz, belirli durumlar hariç en hızlı sıralama algoritması Quick Sort Algorithm yargısı doğru oluyor.
daha doğrusu, yalnızca belirli durumlarda quicksort en hızlısı, o da ne demekse yahu. bilgisayarın, belleğin mekaniğinden tut sıralanacak verinin entropisine değin epey kıyas faktörü var iken, tümden teorik ve ideal bir analiz olsa bile herhangi bir algoritma için en hızlı yargısı hepten yanlış.
 

Trexcalibur

Yeni üye
30 Haz 2015
16
0
Daha hızlı çalışan algoritmalar da mevcut runtime süresi olarak sana söyle diyeyim bubble sort O(n) de çalıştıgı zamanlar bile var sanırsam en hızlısı rastlantısal her şey hızlı giderse bogo sort ama en stabil sekilde çalışan radix sort diye biliyorum algoritma analizi yapmadan hızlı yavaş demek dogru degildir.
 
Üst

Turkhackteam.org internet sitesi 5651 sayılı kanun’un 2. maddesinin 1. fıkrasının m) bendi ile aynı kanunun 5. maddesi kapsamında "Yer Sağlayıcı" konumundadır. İçerikler ön onay olmaksızın tamamen kullanıcılar tarafından oluşturulmaktadır. Turkhackteam.org; Yer sağlayıcı olarak, kullanıcılar tarafından oluşturulan içeriği ya da hukuka aykırı paylaşımı kontrol etmekle ya da araştırmakla yükümlü değildir. Türkhackteam saldırı timleri Türk sitelerine hiçbir zararlı faaliyette bulunmaz. Türkhackteam üyelerinin yaptığı bireysel hack faaliyetlerinden Türkhackteam sorumlu değildir. Sitelerinize Türkhackteam ismi kullanılarak hack faaliyetinde bulunulursa, site-sunucu erişim loglarından bu faaliyeti gerçekleştiren ip adresini tespit edip diğer kanıtlarla birlikte savcılığa suç duyurusunda bulununuz.