Kabarcık sıralaması - Vikipedi
Kabarcık sıralaması | |
---|---|
![]() Kabarcık sıralaması'nın rastgele üretilmiş sayıları sıraladığını gösteren bir örnek | |
Sınıf | Sıralama algoritması |
Veri yapısı | Dizi |
Zaman karmaşıklığı | О(n²) |
En iyi | Yok |
Alan karmaşıklığı | toplamda О(n), ek alan O(1) |
![Kabarcık sıralamasının durağan gösterimi](http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/220px-Bubblesort-edited-color.svg.png)
Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır. Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler. Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir.
Başlangıçta yer yer değiştirme sıralaması olarak adlandırılan kabarcık sıralaması, dizi içindeki büyük elemanların algoritmanın her adımında dizinin sonuna doğru doğrusal olarak ilerlemesini sağlar. Bu ilerleme, seçmeli sıralama algoritmasındaki dizideki değeri küçük olan elemanların dizinin başında kümelenmesi yöntemine benzer şekilde gerçekleşir.
İnceleme
[değiştir | kaynağı değiştir]Kabarcık sıralaması dizinin başından başlar ve dizi elemanlarını sırayla seçer. Seçilen dizi elemanı kendinden sonra gelen elemandan büyükse bu iki elemanın yerleri değiştirilir. Bu işlem sonucunda dizinin en büyük elemanı dizi sonuna yerleştirildiğinden bir sonraki adımda arama sınırı bir eleman geri çekilir. Bu işlem, dizinin sonundaki elemanın karşılaştırılmasına kadar yinelenerek sürdürülür.
Algoritmanın Karmaşıklığı
[değiştir | kaynağı değiştir]Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı 'dir. Algoritma ortalama ve en kötü durumda adet karşılaştırma ve yer değiştirme gerçekleştirir.
Algoritmanın Adım Adım İşleyişi
[değiştir | kaynağı değiştir]İçeriği "5 1 4 2 8" olan bir dizi kabarcık sıralaması ile en küçükten en büyüğe doğru aşağıdaki biçimde sıralanır. Her adımda dizinin kalın olarak işaretlenmiş elemanları karşılaştırılan elemanlardır.
Birinci Geçiş:
(5 1 4 2 8 ) (1 5 4 2 8 ) Burada algoritma ilk iki elemanı karşılaştırır ve yerlerini değiştirir.
(1 5 4 2 8 ) (1 4 5 2 8 )
(1 4 5 2 8 ) (1 4 2 5 8 )
(1 4 2 5 8) (1 4 2 5 8) Burada elemanlar zaten sıralı olduğu için algoritma yerlerini değiştirmez.
İkinci Geçiş:
(1 4 2 5 8 ) (1 4 2 5 8 )
(1 4 2 5 8 ) (1 2 4 5 8 )
(1 2 4 5 8 ) (1 2 4 5 8 )
(1 2 4 5 8) (1 2 4 5 8)
Artık dizi sıralıdır ancak algoritma işlemin bittiğini bilmemektedir. Algoritmanın dizinin sıralandığını anlaması için bütün dizinin üzerinden hiçbir değişiklik yapmadan tam bir geçiş yapması gerekir.
Üçüncü Geçiş:
(1 2 4 5 8 ) (1 2 4 5 8 )
(1 2 4 5 8 ) (1 2 4 5 8 )
(1 2 4 5 8 ) (1 2 4 5 8 )
(1 2 4 5 8) (1 2 4 5 8)
Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır.
Sözde Kodu
[değiştir | kaynağı değiştir]Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:
procedure bubbleSort(A : sıralanabilir öğe dizisi ) defined as: do swapped := false for each i in 0 to length(A ) - 2 do: if A[ i ] > A[ i + 1 ] then swap(A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure </gösterilebilir:
procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j -1 ] > A[ j ] then swap( A[ j - 1], A[ j ] ) end if end for end for end procedure
Diğer Sıralama Algoritmaları
[değiştir | kaynağı değiştir]- Hızlı Sıralama
- Birleştirmeli Sıralama
- Seçmeli Sıralama
- Kokteyl Sıralaması
- Tarak Sıralaması
- Yığın Sıralaması
- Eklemeli Sıralama
- Kabuk Sıralaması
Dış bağlantılar
[değiştir | kaynağı değiştir]- K 28 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.
abarcık Sıralama MATLAB 28 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi. Kod Örneği 28 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralama Python 28 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi. Kod Örneği 28 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.
- 20 programlama dilinde yazılmış Kabarcık Sıralaması örnekleri 6 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması'nın güzel görünümlü bir örneği ve örneğin kaynak kodu
- Java Applet olarak Kabarcık Sıralaması 20 Ekim 2007 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması örneği
- Kabarcık Sıralaması örneği - 2 29 Ocak 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması örneği - 3 19 Ocak 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması örneği - 4 (İspanyolca) 19 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- C++ ile yazılmış sıralama uygulamacıkları 24 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması'nı uygulayan C++ programı 2 Şubat 2008 tarihinde Wayback Machine sitesinde arşivlendi.
- Kabarcık Sıralaması'nı uygulayan C++ programı ve açıklaması
- Kabarcık Sıralaması görüntüsü ve C++ kodu
- Kabarcık Sıralaması'nı Javascript IDE kullanarak incelemeyi sağlayan bir araç
- Kabarcık Sıralaması'nın C++ ve Java örnekleri