ALGORİTMALAR - Sıralama Algoritmaları - Kabarcık Sıralama WyNe rwxr-xr-x 0 09:02:00

Başlık	ALGORİTMALAR - Sıralama Algoritmaları - Kabarcık Sıralama
Yetki	rw-r--r--
Yazar	WyNe
Zaman	09:02:00
Kategori
Share

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.

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.

ALGORİTMANIN KARMAŞIKLIĞI

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.

ALGORİTMANIN ADIM ADIM İŞLEYİŞİ

İç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ş elemenları 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

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 

http://www.banadersanlat.com/index.php/algoritmalar/4431-s-ralama-algoritmalar-kabarc-k-s-ralama.html

ALGORİTMALAR - Sıralama Algoritmaları WyNe rwxr-xr-x 0 09:01:00

Başlık	ALGORİTMALAR - Sıralama Algoritmaları
Yetki	rw-r--r--
Yazar	WyNe
Zaman	09:01:00
Kategori
Share

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.

Sıralama algoritmaları, tanımı çok yalın olmasına karşın çözümü çok karmaşık olan bir işi gerçekleştirdikleri için, üzerinde en fazla araştırma yapılan bilgisayar bilimi konularından biridir. Çoğu kişi sıralama sorununu çözülmüş bir sorun olarak görse de, yeni sıralama algoritmaları üzerinde araştırmalar sürmektedir. Örneğin kütüphane sıralaması ilk olarak 2004 yılında ortaya atılmıştır. Sıralama algoritmaları, sayılarının çok olması ve değişik yaklaşımlar sunmaları nedeniyle özellikle giriş düzeyindeki bilgisayar bilimleri derslerinde büyük O gösterimi ve veri yapıları gibi temel algoritma kavramlarının açıklanması amacıyla yaygın biçimde kullanılırlar.

Bilgisayar bilimlerinde kullanılan sıralama algoritmaları genellikle aşağıdaki ölçütlere göre sınıflandırılır:

• Hesaplama karmaşıklığı: Dizideki öğelerin karşılaştırılmasının en iyi, ortalama ve en kötü başarımının dizinin boyutu (n) cinsinden gösterilmiş halidir. Olağan uygulamalarda sıralama algoritmalarının iyi durum başarımı O(n log n) ve kötü durum başarımı is ?(n²)'dir. Bir sıralama algoritmasının istenen karmaşıklığı O(n)'dir. Yalnızca soyut bir anahtar karşılaştırması yapan bütün sıralama algoritmaları en kötü durumda her zaman ?(n log n) karşılaştırma yaparlar.
• Yer Değiştirme Karmaşıklığı (yerinde sıralama algoritmaları için).
• Bellek (ve diğer donanım kaynaklarının) Kullanımı: Bazı sıralama algoritmaları dizinin içerdiği öğelerin dizinin saklandığı alanda sıralar. Böylece sıralanan öğeler dışında yalnızca O(1) ya da O(log n)'lik bir ek bellek alanı gerekir. Bazı algoritmalar ise verinin geçici olarak saklanması için dizinin tutulduğu alanın dışında ek bellek alanlarına gereksinim duyar.
• Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesiz çalışırken, birleştirmeli sıralama gibi bazı algoritmalar iki biçimde de uygulanabilir
• Kararlılık
• Kaşılaştırma sıralaması olup olmama: Bir karşılaştırma sıralaması sıralanacak veriyi, bir karşılaştırma işlemi kullanarak, karşılaştırarak inceler.
• Genel Yöntem: Araya sokma, değiştirme, seçme, birleştirme vb. Değiştirme sıralamalarına kabarcık sıralaması ve hızlı sıralama örnek olarak gösterilebilir. Yığın sıralaması ise seçme sıralamalarındandır.

KARARLILIK

Kararlı sıralama algoritmaları sıralanacak dizinin içinde değerleri birbirine eşit olan öğerlerin birbirlerine göre olan konulmlarını korur. Başka bir deyişle, bir sıralama algoritması kararlı olduğunda, eğer R ve S gibi içerdiği değer aynı olan iki öğe bulunduran asıl dizide, R, S' den önce geliyorsa, sıralanmış dizide de R, S'den önce osurur.

Dizinin içinde birbirine eşit değerler içeren öğeler birbirlerinden ayırt edilemiyorsa (örneğin sayılar ya da harfler gibi değerler öğenin kendisini oluşturuyor ise) kararlılık bir sorun değildir. Ancak aşağıda gösterildiği gibi sayı çiftleri, her çiftin virgülden önceki sayısına göre sıralanacağı düşünülürse kararlılık sorunu ortaya çıkar.

(4, 1)  (3, 7)  (3, 1)  (5, 6)

Bu durumda, 2 değişik sonuç mümkündür; ilk çözüm sıralama anahtarlarının değerleri aynı olan öğelerinin sırasını korur, ikincisi ise korumaz:

(3, 7)  (3, 1)  (4, 1)  (5, 6)   (sıra korunmuş)
(3, 1)  (3, 7)  (4, 1)  (5, 6)   (sıra değişmiş)

Kararsız sıralama algoritmaları sıralama anahtarlarının değerleri aynı olan öğelerin dizi içindeki sırasını değiştirebilir ancak kararlı sıralama algoritmaları asla değiştirmez. Kararsız sıralama algoritmaları özellikle kararlı olacak biçimde uygulanabilir. Bunu yapmanın bir yolu yapay olarak anahtar karşılaştırmasını anahtlarının değerleri birbirine eşit olan iki öğenin durumunu belirlemek için asıl listedeki konumlarını ölçüt olarak kullanacak biçimde genişletmektir. Ancak asıl dizideki öğre sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir. 

sıralama Algoritmalarının Listesi

Aşağıdaki tablolarda n dizideki sıralanacak olan eleman sayısını gösterir. "Ortalama" ve "En Kötü" kolonları ilgili durumlardaki karmaşıklığı, "Bellek" kolonu ise listenin sıralanabilmesi için listenin bellekte kapladığı alandan ne kadar daha fazla saklama alanı gerektiğini gösterir.

http://www.banadersanlat.com/index.php/algoritmalar/4430-s-ralama-algoritmalar.html