CP #32: Sorting Problemleri
Sorting onemli bir mevzumuzdur.
Sorting Nedir?
https://en.wikipedia.org/wiki/Sorting_algorithm
Bilgisayar bilimlerinde belirli bir dizi icerisinde yer alan elemanlaribelirli bir siraya sokan algoritmalara `sorting algorithm` adi verilir.
En fazla kullanim alani su iki kategoride bulunmaktadir:
1. sayilari siralamak (numeric sorting)
2. alfabetik siralama (lexicographic sorting)
Hangisi?
Sorting algoritmalarinin elbette ki dandik olanlari vardir, guzel olanlari vardir. Her duruma gore secilebilecek sorting algoritmasi da biraz farklilik gosterebilir.
Algoritmalari kiyaslayabilmek icin birkac kritere bakmamiz gerekiyor.
1. Runtime complexity
a. Best
b. Average
c. Worst
2. Memory complexity (hafiza tuketimi)
3. Stabil mi? (relative order'i koruyor mu? gotu basi oynuyor mu?)
4. Online sorting algoritmalari: Tum arrayi gormesi gerekmeyen algoritmalardir. Ozellikle streamlari sort etmede fayda saglar. Elemanlar en bastan itibaren birer birer verilir ve algoritma arrayi sorted olarak tutar. Insertion sort buna bir ornek olarak gosterilebilir. Surada guzel bir aciklama mevcut.
1. Timsort
Python default sorting algortimasi Timsort olup merge sort ve insertion sortun birlesiminden olusur. Sorted veya list uzerindeki .sort metodlari ile kendisine ulasabiliriz. Ozellikleri:
Best case: O(n)
Average: O(n logn)
Worst case: O(n logn)
Ekstra hafiza gereksinimi (auxilary space): O(n)
Stable: Evet
Adaptive: Evet (bir arrayin zaten sorted olup olmadigi bilgisini kullanabiliyorsa, adaptive sorting algorithms kumesine dahil oluyor)
2. Buble sort
En basit sorting algoritmasidir. Verilen dizi sorted olana kadar, ikilie elemanlarin yeri yanlis ise bunlari swap etme uzerine dayanir.
def buble_sort(arr):
# arraydaki her eleman icin bir pass yapmamiz gerekiyor
for i in range(len(arr)):
# her pass'ta yan yana duran iki elemani kiyasliyoruz
# ve her adimda ensondaki sorted eleman sayisi 1 artiyor
# yani i = 0 icin yapilan pass'te en buyuk eleman ensona tasinmis
# oluyor zaten
# i = 1 olan pass'te ise en buyu 2 eleman listenin en sonuna
# kayiyor. Bu acidan j icin 0'dan sona kadar degil de len(arr)-i-1'e
# kadar gitmek yeterli oluyor
for j in range(len(arr) - i - 1):
if arr[j] > arr[j+1]:
# indexi kucuk olanin
# daha kucuk olmasi gerekir:
# swap ediyoruz
arr[j], arr[j+1] = arr[j+1], arr[j]
Iki dongu ile arayi sort ettigimiz icin tas gibi bir O(n2) algoritma elde ettik. Avg, worst case, best case hepsi O(n2). Ama in-place, ekstra memory kullanimi yok: O(1) space compl.
Yakindan bakacak olursak, icerideki dongude, surekli bir elemani yanindaki eleman ile kiyasliyoruz ve eger order yanlis ise swap ile duzeltiyoruz. Peki bir pass icin, diyelim ki i = 0, ic dongude hic swap yapilmazsa? Bu demek oluyor ki verilen array zaten sorted. O zaman dis donguyu burada sonlandirabiliriz. Ya da pass'lerden birtanesi arrayi sort etti, o anda da islemi durdurabiliriz:
def modified_buble_sort(arr):
for i in range(len(arr)):
swapped = False
for j in range(len(arr) - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# ic dongude hic swap yapilmadi ise
# bu noktada array artik sorted olmus demektir
if swapped == False:
# hatta burada indexi kontrol ederek, (i==0 mi seklinde)
# verilen arrayin zaten sorted olup olmadigi da anlasilabilir
break
Almost sorted array
Modifiye buble sort icin best case time comp. O(n)'e indirgenmis oluyor bu sayede. Cunku sorted bir array verilirse, dis dongu sadece 1 kere calisacaktir. Ve hatta array, almost sorted ise yani mesela tek bir eleman order'i bozuyor [12, 1, 2, 3, 4] gibi, bu durumda da yine O(n) kalmaya devam ediyor.
3. Merge sort
Divide and conquer tipi bir sorting algoritmasidir. Arrayi recursive olarak her seferinde iki parcaya bolup, parcalari sort edip, sonra da yine recursive olarak birlestirme esasina dayanmaktadir.
Arrayi tam ortadan ikiye bolerek ise basliyoruz. Bu bolme islemi, parcalar 1 elemandan olusacak hale gelene kadar devam ediyor. Sonra birlestirme islemi basliyor. Wikipedia guzel ozetlemis:
Worst, best ve average case: O(n logn)
Ekstra space: O(n)
in-place: Hayir
Kullanim alanlari:
1. Linked list'lerin O(n logn) ile sort edilmesinde kullanilir. Cunku merge sort zaten komsu elemanlar ile calisir. Bu acidan random access gerektirmez. Linked liste'te de random access olmadigi icin, diger sorting algortmalari (quick sort mesela) kullanilamaktadir.
2. External sorting. Yani sort edilecek olan array bilgisayarin hafizasina sigmiyor ise, external bir yere yani diske yazilarak burada sort islemi yapilir.
4. Quick Sort
Merge sort gibi bu da divide and conquer tipinde bir algoritmadir. Merge sortta pivot olarak ortadaki eleman alinirken, quicksortta 3 farkli yontem ile alinabilir: en bastaki, en sondaki veya herhangi bir random eleman.
Worst case: Pivot olarak en buyuk veya en kucuk eleman secilmesi durumunda ortaya cikmaktadir. O(n2)
Best case: Partition olarak surekli en ortadaki elemani aldigimizda ortaya cikar. O(n logn)
Average case: O(n logn)
5. Counting Sort (Cakal Sort)
Karsilastirma bazli sorting algoritmalari (buble sort, merge sort, quick sort, ... ) icin alt limit O(n logn)'dir. Bundan daha iyisi yapilamiyor.
Counting sort ise farkli bir yontem izliyor. Ornegin 26'dan 153'e kadar olan sayilardan olustugunu bildigimiz bir array var. Bunu sort etmek icin bir kere traverse edip her elemandan kac tane olduguna bakmamiz yeterli. Daha sonra bu arrayin sorted halini kendimiz olusturabiliriz. Bu da O(n) gibi bir time compl. elde etmemizi sagliyor. Bir ornekle aciklayalim:
from collections import defaultdict
def counting_sort(arr, start, end):
# elemanlar unique ise bunu bile yapmaya gerek yok
counts = defaultdict(lambda: 0)
for n in array:
counts[n] += 1
# simdi sorted sekilde arrayi olusturalim
ret = []
for i in range(start, end):
# bu elemandan kac tane varsa o kadar ekle
for _ in range(counts[i]):
ret.append(i)
return ret
Sadece int arrayler icin calisacak ozel bir durum. Ancak runtime'a bakarsak O(n+k) seklinde gayet performansli. Burada n, arraydaki eleman sayisi, k ise kac farkli eleman olabilecegi. Space compl. ise yeni bir return array olusturdugumuz ve yda her bir sayinin sayisini tuttugumuz icin O(n+k) seklinde olacaktir. Peki ayni mantikla verilen bir stringin karakterlerini sort edebilir miyiz? Sonucta karakterler degeri de ancak belirli bir range icerisinde olmaktadir: 0 ile 26. (standart ingilizce karakterler icin).
def counting_sort_string(string):
# 26 tane karakter oldugu icin,
# her bir karakterin sayisini tuacak array de 26 uzunlukta olur
counts = [0] * 26
# char code'u shift ediyoruz.
# yani a => 0, b=>1, c=>2 ... seklinde
def get_char_index(char):
return ord(char) - ord('a')
for k in string:
counts[get_char_index(k)] += 1
# sorted olarak olusturalim
ret = [None] * len(string)
ind = 0
# eger char code shift yapmasa idik
# burada a'dan z'ye bir iterasyon gerekirdi
for i in range(26):
for _ in range(counts[i]):
ret[ind] = chr(ord('a') + i)
ind += 1
return ret
Goruldugu uzere eger elemanlarin alabilecekleri deger sinirli ise (k), ve bu sinir, arraydaki eleman sayisindan cok daha buyuk degil ise, counting sort cok performansli ve cakal bir yontem.
6. Radix Sort
Bir once gordugumuz counting sort algoritmasini bir subrutin olarak kullanir. Counting sortun kisitlamasi, bir elemanin alabilecegi deger sayisi eger array'deki eleman sayisinin cok uzerinde ise basliyordu. Array'de n eleman var iken her bir array O(n2) deger alabiliyorsa, toplamda O(n2) bir time compl. elde ediliyor. (O(n+k) olarak belirtmistik, burada k=n^2 olunca, O(n + n^2) = O(n^2) oluyor).
Radix sort ise verilen sayilari once birler basamagina bakarak ve counting sort kullanarak sort ediyor. Sonra 10lar basamagi sonra 100'ler ve bu sekilde devam ediyor. Disaridaki dongu, en fazla hane iceren eleman kadar donecek ve her bir donmesi de counting sort kullandigi icin O(n) mertebesinde olacaktir. Yani bir elemanin alabilecegi hane sayisi d ise sonucta O(n * d) gibi lineer bir cozum elde etmis oluruz.
7. Bucket sort
Belirli bir deger araliginda uniform olarak dagilmis elemanlardan olusan bir arrayi efektif sekilde sort etmemize yarar. 0 ile 1.0 arasinda float degelere sahip, uniform dagilimli bir array dusunelim. Karsilastirma tabanli sorting algoritmalari O(n logn)'den daha iyi performans gosteremeyecek. Peki biz bu sortingi O(n) ile yapabilir miyiz?
Verilen aralik (ornekte 0.0 ile 1.0 arasi), n adet bucket (kova)'ya bolunur. Arraydaki her bir eleman bucketlara dagitilir. (ancak bu islem O(1) olmalidir). Mesela 0 ile 1.0 arasini 10 bucketa bolup, 0.67'yi 6. bucketa gondermemiz gerekiyor.
Her bir bucket sifirdan olusacak ve sorted durmasi gerekecek. Bunun icin insertion sort kullanilabilir. Eger bucket icerisindeki elemanlari linked list uzerinde tutarsak, her bir adim O(n) seklinde olur ve bucket icerisi sorted kalir.
Son olarak da sortladigimiz bucketlari birlestirmek isi kaliyor. Bunu da yine O(n) ile yapabiliriz. Nihayetinde toplamda O(n) time compl. elde etmis oluyoruz.
Sorting Problemleri
1. Widest Vertical Area Between Points Problemi
Problem surada.
Verilen noktalar arasinda aslinda x-axis uzerine izdusumu alindigi zaman olusacak max araligi soruyor. Bu durumda verilen input noktalari x koordinatina gore sort edip aralarindaki maks diff'i bulursak, sonuca ulasmis oluruz.
Verilen noktalar arasinda aslinda x-axis uzerine izdusumu alindigi zaman olusacak max araligi soruyor. Bu durumda verilen input noktalari x koordinatina gore sort edip aralarindaki maks diff'i bulursak, sonuca ulasmis oluruz.
def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
# x koordinatlarini alalim ve sort edelim
xcoords = sorted([x[0] for x in points])
# tum koordinatlari donup en buyukaraligi bulalim
max_diff = 0
for i in range(len(nums)-2):
max_diff = max(max_diff, xcoords[i+1] - xcoords[i])
return max_diff
Bakacak olursak noktalari sort etmek O(n logn), uzerinde itere edip maks araligi bulmak O(n). Toplamda O(n logn) bir cozum elde ettik.
2. Largest Number Problemi
Problem surada.
Verilen sayilari yan yana birlestirip de en buyuk sayiyi elde etmek istiyorsak, en buyuk haneler en basa gelmelidir. Oyleyle verilen sayilari once stringe cevirip sonra buyukten kucuge sort edersek, birlestirdigimiz zaman en buyuk sayi olusur mu? Bir edge case disinda evet. O da su ki, 3 ve 30 icin basa 30'u koyarsak (303) ya da basa 3'u koyarsak (330) gibi bir durum yasiyoruz. Yani ayni hane ile baslayan sayilarda problem oluyor.
Verilen sayilari yan yana birlestirip de en buyuk sayiyi elde etmek istiyorsak, en buyuk haneler en basa gelmelidir. Oyleyle verilen sayilari once stringe cevirip sonra buyukten kucuge sort edersek, birlestirdigimiz zaman en buyuk sayi olusur mu? Bir edge case disinda evet. O da su ki, 3 ve 30 icin basa 30'u koyarsak (303) ya da basa 3'u koyarsak (330) gibi bir durum yasiyoruz. Yani ayni hane ile baslayan sayilarda problem oluyor.
Bunu da custom bir comparizon ile asabiliriz. 3 ve 30'u mu siralamak istiyoruz, o zaman birlestirilmis hallerini kiyaslarsak sorun ortadan kalkiyor. Yani "330" mu yoksa "303" mu buyuk? Bu kiyaslamayi kolayca yapabilmek icin custom bir class tanimlayip, __lt__metodunu override edebiliriz.
def largestNumber(self, nums: List[int]) -> str:
# kolaylik olsun diye custom classi stringden turetiyoruz
class StrKey(string):
def __lt__(self, other):
# burada self ve other string oldugu icin
# + islemi concat anlamina geliyor
return self+other > other+self
# simdi verilen sayilari string'e cevirip,
# stringlerden StrKey olusturup, one gore edelim
# map ile [str(x) for x in nums] kismini
# nasil da basite indirgedigimize dikkat!
sorteds = sorted(map(stri, nums), key=StrKey)
# 0,0 gibi bir edge case icin "00" dondurmeyelim
return "0" if sorteds[0] == "0" else "".join(sorteds)
Sadece custom sort kullandigimiz icin cozum O(n logn) time compl. ve O(n) space compl. sahip. Ne de olsa her bir sayidan string turetip hafizada tutuyoruz.
3. Insert Interval Problemi
Problem surada.
Verilen input intervallerin sorted olmasi cok guzel. Eger olmasalardi zaten sort etmemiz gerekirdi. Surasi acik ki, bir intervali insert etmek icin tum intervaller uzerinde bir kere donecegiz, O(n). Ilk karsimiza cikacak olan case ise su:
- - - - - - - - - - - - [ Yeni Interval ] - - - - >
- - - [Interval] - - - - - - - - - - - - - - - - - >
Bu durum kolay. Zaten intervaller sorted oldugu icin, egere birtanesi geride kaliyor ise, onunla artik tekrar overlap imkani yoktur. O aman [Interval] olani, return arrayina ekliyoruz.
Ikinci durum ise karsilastirma yaptigimiz interval, insert eymeye calistigimizin onunde ise:
- - [Yeni Interval ] - - - - - - - - - - - - - - - >
- - - - - - - - - - - - - - - - [ Interval ] - - - - >
Bu durumda, yeni intervali return arrayina ekleyip, yeni interval olarak [Interval]'i almamiz gerek. Cunku bu sekilde merge ede ede ilerlersek ancak dogru sonuca ulasabiliriz.
Son secenek de tabi yeni interval'in mevcut bir interval ile overlap olmasi. Bu durumda da [Yeni Interval]'i genisletmek gerekiyor.
- - - - [ Yeni Interval ] - - - - - - - - - - - - - >
- - - - - - - - - [ Interval ] - - - - - - - - - - - ->
Simdi implementasyona gecebiliriz.
# isler duzenli olsun diye Interval icin bir class olusturuyorum
# ama mecbur da degiliz
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
# baska bir interval ile overlap oluyor mu?
def overlaps(self, other):
# verilen bir nokta interval icerisine dusuyor mu?
def in_range(point, interval):
return point <= interval.end and point >= interval.start
# eger start veya end noktasi diger interval icerisine dusuyor ise
# overlap var demektir
return in_range(self.start, other) or in_range(self.end, other)
# eger baska bir interval ile overlap var ise
# bu intervali genisletmemiz gerekecek
def expand_with(self, other):
self.start = min(self.start, other.start)
self.end = max(self.end, other.end)
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new = Interval(newInterval[0], newInterval[1])
ret = []
for interval in intervals:
# interval geride, yukaridaki 1. case
if interval.end < new.start:
ret.append(interval)
# iterval onumuzde, 2.case
elif interval.start > new.end:
ret.append(new)
new = interval
elif new.overlaps(interval):
new.expand_with(interval)
# en sonda onumuzde bir interval kalmis ise onu eklemek gerekiyor
ret.append(new)
# leetcode arraylarin arrayi olarak cevap bekliyor bizden
return [[r.start, r.end] for r in ret]
Tek yaptigimiz tum intervalleri donmek. Dolayisi ile O(n) bir time compl. sozkonusu. Space compl. ise O(n) olarak goze carpiyor.
Diger bir algoritma postunda gorusmek dilegiyle. Stay hungry, stay foolish, stay healthy :)
Yorumlar
Yorum Gönder