2 dk, tahmini okuma süresi
Python İle Secim Sıralaması
En Son Güncelleme: 21 Eylül, 2022Selection sort, works by repedeatly finding the lowest (minimum) in an array and putting it in the beginning. We keep track of the minimum and in each iteration and switch it with the element that the current iteration starts with.
Seçimli sıralaması, bir dizideki en düşük (minimum) değeri tekrar tekrar bulup listenin çalışır koyma şeklinde çalışır. Minimum değerini yinelemede takip ediyoruz ve mevcut yinelemenin başladığı elemanla değiştiriyoruz.
§Anlamamıza Yardımcı Olacak Bir Örnek
O halde adım adım neler yapmamız gerektiğini bir görelim.
Yinelememiz, listemizdeki her öğe için tekrarlayacak. İlk yinelemede dizideki ilk değeri varsayılan minimum değerimiz olarak alacağız.
In our nested, second iteration we will continue iterating until we find a value smaller than our min. When we find it the new value becomes the new min and we continue like that. When the second iteration is over we end up with the lowest value as the min. Now we swap the min and the first value we selected as min in our first iteration.
İç içe, ikinci yinelememizde, min'den daha küçük bir değer bulana kadar yinelemeye devam edeceğiz. Bulduğumuzda yeni değer yeni min olur ve böyle devam ederiz. İkinci yineleme bittiğinde min olarak en düşük değeri elde etmiş oluruz. Şimdi ilk iterasyonumuzda min ve min olarak seçtiğimiz ilk değeri değiştiriyoruz.
Devam eden adımlarda, listedeki en düşük değeri bulmaya devam ediyoruz ve onu iterasyonun başladığı değerle değiştiriyoruz.
Bir örneğin, her şeyin nasıl daha iyi çalıştığını anlamamıza yardımcı olacağına inanıyorum.
def selectionSort(arr, size):
for i in range(size):
min = i
for j in range(i+1, size):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Artan Sırada Sıralanmış Dizi:')
print(data)
İşte başlıyoruz! Peki burada neler oluyor? İlk yinelemede i değerimiz 0'dan başlar ve dizinin uzunluğu eksi 1'e kadar gider.
İkinci dizide i+1'den başlıyoruz. Bu, minimum için seçtiğimiz değerin hemen yanındaki değer anlamına gelir. Bu ikinci dizide daha küçük bir değer arıyoruz (dizi[min]'den). Bulduğumuzda, bu yeni değer yeni min olur. Yani ikinci yinelemenin ilk döngüsünün sonunda dizimiz şudur:
[-9, 45, 0, 11, -2]
Gördüğünüz gibi -9 ve -2 yer değiştirdi. Dizimiz sıralanana kadar bu adımları tekrarlamaya devam ediyoruz.
İkinci döngünün sonunda:
[-9, -2, 0, 11, 45]
Üçüncü döngünün sonunda:
[-9, -2, 0, 11, 45]
Dördüncü döngünün sonunda:
[-9, -2, 0, 11, 45]
Beşinci döngünün sonunda:
[-9, -2, 0, 11, 45]
Rastgele sayılarımızı sıralamak bu örnekte gayet kolay çıktı ve ikinci adımdan sonra pek bir şey yapmamıza gerek kalmadı. Ancak, bu noktada seçim sıralamasının nasıl çalıştığını anladığınızı varsayıyorum. Sadece ezberlemek yerine anladığınızdan emin olmak için en az bir kez kendi başınıza yazdığınızdan emin olun.
§Seçim Sıralamasının Karmaşıklığı
İki döngü olduğu için zaman karmaşıklığının O(N²) olduğunu söyleyebiliriz. Dizide yineleme için bir döngü ve karşılaştırmalar için bir döngü.
Seçim sıralaması, minimum değeri tutmak için kullanılan bellek maliyeti ile bellek açısından verimlidir. Bu nedenle kullanılan en kötü durum belleği, min'i tutmak için O(1) ve değiştirmeler için O(N)'dur. Bu nedenle, zamanınız varsa ancak yeriniz (belleğiniz) yoksa, seçim sıralamasını seçebilirsiniz.
Öğrenmeye devam edin!
Ilker AkbiyikBenzer Paylaşımlar
