Bir bilgisayar sayıları nasıl sıralar?

Kabarcık sıralaması, komşuları karşılaştırıp sıraları bozuksa yerlerini değiştirerek çalışır. Listenin başından başla: ilk iki sayıyı karşılaştır, gerekirse yerlerini değiştir, sonra bir sonraki çifte geç. Örneğin, 85, 72, 90, 65 ile 85 ve 72'yi karşılaştır: 72, 85 olacak şekilde yerlerini değiştir. Sonra 85 ile 90'ı karşılaştır: yer değiştirme yok. Sonra 90 ile 65'i karşılaştır: 72, 85, 65, 90 olacak şekilde yerlerini değiştir. Bir geçişten sonra en büyük sayı (90) sonda olur. 6

Kabarcık sıralamasının bir geçişi yeterli değildir çünkü daha küçük sayılar hâlâ yanlış sırada olabilir. Bilgisayar liste üzerinde geçişleri tekrarlar. Her geçiş, bir sonraki en büyük sayıyı sondaki doğru yerine iter. Örneğin, ilk geçişten sonra liste 72, 85, 65, 90 olur. İkinci geçiş 72, 65, 85, 90 verir. Üçüncü geçiş 65, 72, 85, 90 verir. Bir geçiş hiç yer değiştirme yapmazsa liste sıralanmıştır. 7

Böl ve birleştir başka bir yaklaşımdır: listeyi daha küçük parçalara ayır, her parçayı sırala, sonra onları birleştir. Örneğin, 85, 72, 90, 65'i iki listeye ayır: 85, 72 ve 90, 65. Her birini sırala: 72, 85 ve 65, 90. Sonra iki sıralanmış listeyi tek bir sıralanmış listede birleştir: 65, 72, 85, 90. Bu yöntem büyük listeler için genellikle daha hızlıdır. 8

İki sıralanmış yığını birleştirmek, tekrar tekrar daha küçük olan üstteki kartı seçerek tek bir sıralanmış yığın oluşturmak demektir. Örneğin, A yığını: 72, 85 ve B yığını: 65, 90. Üstteki kartları karşılaştır: 72 ve 65; 65'i seç. Sonra 72 ile 90'ı karşılaştır; 72'yi seç. Sonra 85 ile 90'ı karşılaştır; 85'i seç. Sonra 90'ı seç. Birleştirilmiş yığın 65, 72, 85, 90 olur. 9

Seçmeli sıralama en küçük sayıyı bulur ve onu öne taşır. En küçüğü bulmak için listeyi tara, sonra onu ilk öğeyle yer değiştir. Örneğin, 85, 72, 90, 65 ile en küçük 65'tir; 85 ile yer değiştirerek 65, 72, 90, 85 elde et. Sonra kalanlarda (72, 90, 85) en küçüğü bul: o 72'dir, zaten yerinde. Sonra 90, 85 içinde en küçüğü bul: o 85'tir; 90 ile yer değiştirerek 65, 72, 85, 90 elde et. 10

Farklı sıralama yöntemleri farklı miktarda iş gerektirir. Kabarcık sıralaması komşuları özellikle büyük listelerde çok kez karşılaştırır. Birleştirmeli sıralama böler ve birleştirir; bu, büyük listeler için daha hızlı olabilir. Örneğin, 10 sayıyı sıralamak kabarcık sıralamasıyla yaklaşık 100 karşılaştırma alabilirken birleştirmeli sıralamayla daha az alabilir. Karşılaştırmaları ve yer değiştirmeleri saymak, hızları karşılaştırmana yardımcı olur. 11

Bazı sıralama yöntemleri listenin kendisi dışında ek bellek kullanmadan yerinde sıralar. Diğerleri kopyalar için ek alan gerektirir. Örneğin, kabarcık sıralaması ve seçmeli sıralama yerinde çalışır: yalnızca liste içindeki öğelerin yerlerini değiştirir. Birleştirmeli sıralama, birleştirmeden önce bölünen parçaları tutmak için ek alan gerektirir. Bellek sınırlıysa yerinde çalışan bir yöntem daha iyi olabilir. 12

Verinin boyutu önemlidir: 100 sayıyı sıralamak 10 sayıyı sıralamaktan daha çok iş gerektirir. Mevcut sıra da önemlidir: neredeyse sıralanmış bir liste bazı yöntemler için çok daha hızlı olabilir. Örneğin, kabarcık sıralaması zaten sıralanmış bir listede yalnızca yer değiştirmesiz bir geçiş gerektirir. Karıştırılmış bir liste çok sayıda geçiş gerektirir. Yani bilgisayarın işi hem boyuta hem de sıraya bağlıdır. 13

Değerlerin türü sıralamayı etkiler. Sayılar büyüklüğe göre karşılaştırılır, ama kelimeler alfabetik olarak karşılaştırılır. Örneğin, Alice, Bob, Carol gibi adları sıralamak alfabetik sırayı kullanır. Bazı yöntemler sayılar için iyi çalışır ama kelimeler için ayarlamalar gerektirir. Değerin türü, hangi sıralama yönteminin en uygun olduğuna yön verir. 14

Yeni başlayanlar genellikle kabarcık sıralamasının bir geçişinden sonra durur, ama bir geçiş yeterli değildir. Bir başka hata, listenin zaten sıralanmış olabileceğini unutmaktır; bunu kontrol et. Ayrıca küçük listelerle ve yinelenen sayılar veya ters sıra gibi zor durumlarla test et. Örneğin, hataları yakalamak için 3, 2, 1 ve 1, 1, 1'i sıralamayı test et. 15

Bilgisayarlar sayıları karşılaştırıp taşıyarak, hız ve bellek bakımından farklılaşan yöntemlerle sıralar. Kabarcık sıralaması komşuların yerlerini tekrar tekrar değiştirir; birleştirmeli sıralama böler ve birleştirir. Veri miktarı, mevcut sıra ve değerlerin türü seçime yön verir. Doğruluğu sağlamak için küçük ve zor örneklerle test etmeyi unutma. 16