Listeli Birleştirme Sıralama Algoritması
02 Şubat 2024
Sırasız bir listeden sıralı listeler oluşturup birleştirerek sılarama üzerine...
Giriş
Bu yazımızda inceleyeceğim algoritma basit bir sıralama algoritması olacak. Instagram üzerinde gördüğüm garip bir algoritmayı geliştirmeyi planlıyorum.
Algoritma özet olarak bir listeyi sıralamak için sırayı bozan elemanları listeden siliyordu. Örneğin,
5 6 2 9 12 74 3 olan liste sıralama sonunda 5 6 9 12 74 olacaktır.
Ben ise sıralamayı bozan elemanları silmek yerine saklayarak daha sonra birleştirerek ilkine denk bir sıralı liste oluşturacağım.
İlk Adım Elemanları Ayırma
İlk adım sırayı bozan elemanları saklama sorunu çözmek olacak.
Insertion sorttan kaçınmak için sakladığımız elemanların da kendi içinde sıralı olması gerekmektedir.
Aksi halde, sakladığımız her elemanın doğru yerini asıl listede ararken listeyi baştan sona gezmek zorunda olduğumdan,
O(n^2) karmaşıklığa giden bir algoritma tasarlamış olurdum.
Benim hedefim ise saklanan elemanların sıralı olması sonucunda, eşleştirme sırasında asıl listeyi baştan sona tek bir seferde doldurmaktır.
Bulduğum çözüm asıl listeden çıkarılan elemanların ayrı bir listede sıralı şekilde tutulmasıdır.
Küçükten büyüğe dizi ile sıralama
int[] arr = {3, 81, 34, 87, 23, 1, 90, 45, 2}
int[][] list_of_sorted_arrays = new int[len(arr)][]
list_of_sorted_arrays[0] = arr
int num_of_sorted_lists = 1
for i = 1 to len(arr):
if(arr[i] < arr[i - 1]):
store(arr[i]) //TODO: implement store
sorted_arr = merge_to_sort(listt_of_sorted_arrays) //TODO: implement this
Küçükten büyüğe bağlı liste ile sıralama
list arr = {3, 81, 34, 87, 23, 1, 90, 45, 2}
list> c = new list>
list_of_sorted_lists.head = arr
list_of_sorted_lists.tail = arr
for i = 1 to len(arr):
if(arr[i] < arr[i - 1]):
store(arr[i]) //TODO: implement store
sorted_arr = merge_to_sort(list_of_sorted_lists) //TODO: implement this
Ancak oluşturulan ikinci listenin sıralı olmasını gözetmek,
insertion sort algoritmasını ikiye bölmekle eş değer olmakla birlikte amacımızdan uzaklaşmamız demektir.
Onun yerine sıralı özelliğini bozan her yeni eleman yeni bir listenin başı olmalıdır.
Store Fonksiyonunun Dizi İçin Uygulaması
store(int new_num):
for i = 1 to num_of_sorted_lists: //TODO: Fix num_of_sorted_lists starts with 1.
if(list_of_sorted_arrays[i][last_element] <= new_num): //TODO: Fix last_element problem.
list_of_sorted_arrays[i][last_element + 1] = new_num
return
list_of_sorted_arrays[num_of_sorted_lists][] = new int[len(arr)] //We can optimize space.
list_of_sorted_arrays[num_of_sorted_lists][0] = new_num
Store Fonksiyonunun Sıralı Liste İçin Uygulaması
store(int new_num):
cursor = list_of_sorted_lists.head.next
while(cursor != null):
if(cursor.tail <= new_num):
cursor.tail.next = new_num
cursor.tail = cursor.tail.next
return
list_of_sorted_lists.tail.next = new list
list_of_sorted_lists.tail = list_of_sorted_lists.tail.next
list_of_sorted_lists.tail.head = new_num
list_of_sorted_lists.tail = new_num
Yeni listeler de kendi içinde sıralı olmalı. Eğer sıra bozulacaksa yeni liste yapılmalı.
Liste birleştirme çok zeki olmalı yoksa yavaş olur ve yeni liste yaratmanın anlamı kalmaz.
Eğer listelerin ilk elemanı sürekli sıralı olursa her iterasyonda liste sayısı kadar eleman karşılaştırılmak zorunda kalınmaz. Sadece liste başlarını tutan liste güncellenmeli.
Eğer sürekli en küçük eleman liste başlarında aranırsa O(n*m) olur. m liste sayısıdır.
5 6 2 9 12 74 3
Ayırma
5 6 9 12 74
2 3
Birleştirme
2 3 5 6 9 12 74
Ayırma
5 6
2 geldiği için diğer listeler ile karşılaştırma
2 için yeni liste
9 12 74
3, 2'nin olduğu listenin kuyruğu(2)'ndan büyük sona eklenir.
Örnek 2:
3 81 34 87 23 1 90 45 2
Ayırma
3 81 87 90
34 45
23
1 2
Birleştirme
1 2 3 23 34 45 81 87 90