InsertionSort: fikir ve trace
Elinde iskambil kartları var. Soldaki kartlar zaten sorted. Sağdan yeni bir kart alıp sola doğru götürüyorsun; ondan büyük her kart bir adım sağa çekiliyor. Kart, kendinden küçük ya da eşit bir karta (ya da elin başına) gelince duruyor ve oraya oturuyor.
CS161'in kodu (Python, 0-indexed). Sınavda bu kodu ya da Bilkent slaytlarındaki 1-indexed sürümü (key, for j = 2 to n) görebilirsin; ikisi aynı algoritma.
def InsertionSort(A):
for i in range(1, len(A)):
current = A[i]
j = i - 1
while j >= 0 and A[j] > current:
A[j+1] = A[j] # büyük olanı bir sağa kaydır (shift)
j -= 1
A[j+1] = current # current boşluğa oturur
- current: bu iteration'da insert edilen element,
A[i]. - shift:
A[j] > currentolduğu süreceA[j]bir sağa kopyalanır. Her shift constant time alır. - Inner loop iki sebepten durur:
j−1 olur (array'in başına geldik) ya daA[j] ≤ current. - Koşul strict
>: eşit bir element'in önünde durur, eşit element'lerin yeri değişmez.
Aşağıdaki lab'da kendi array'ini yaz ya da bir preset seç, sonra adım adım ilerlet. Lab'daki kod yukarıdakiyle aynı; tek fark, current yerine Bilkent sürümündeki adı, key'i kullanması. Mor kutu key, mavi comparison yapılan element, turuncu az önce shift edilen element, soluk hücre boşluk; yeşil kısım sorted prefix. Her hücrenin sağ üst köşesindeki küçük mor sayı, element'in input'taki ilk index'i: eşit key'lerin sırası korunuyor mu, ona bakarak görürsün. "Kalan inversion" sayacını şimdilik yalnızca izle, ne demek olduğunu 4. bölümde göreceğiz.
Önce tahmin et: Örnek array'de (6 4 3 8 5) shift sayacı kaçta biter, ve "kalan inversion + shift" toplamı adım adım değişir mi?
Inner loop'ta A[j+1] = A[j] çalışınca aynı değer bir an iki hücrede görünür. Bu bir hata değil: current bir değişkende saklı ve en sonda boşluğa yazılıyor. Sınavda ara durumu çizerken current'ı ayrıca yaz.
InsertionSort'u C A B üzerinde alfabetik sırayla çalıştırıyoruz. A'nın iteration'ı ($i = 1$) bitince array nasıl görünür?
Correctness: loop invariant ile proof
Animasyonda her iteration'ın sonunda yeşil kısma bak: A[:i+1] her zaman sorted. Bu cümle her iteration'da doğru kalıyor, o yüzden ona invariant diyoruz. Son iteration'dan sonra yeşil kısım bütün array olduğu için array sorted. Proof, bunu induction ile yazmaktan ibaret.
- Inductive hypothesis. Outer loop'un $i$. iteration'ından sonra
A[:i+1]sorted. - Base case. $i = 0$ (algoritma başlamadan önce):
A[:1]tek element'li ve tek element'li bir list sorted'dır. - Inductive step. Hypothesis $i-1$ için doğru olsun:
A[:i]sorted. $j^*$, $\{0,\dots,i-1\}$ içinde $A[j^*] \le A[i]$ olan en büyük index olsun (böyle bir index yoksa $j^* = -1$). Inner loop array'i şöyle değiştirir: $$[A[0],\dots,A[j^*],\ A[j^*+1],\dots,A[i-1],\ A[i]] \ \longrightarrow\ [A[0],\dots,A[j^*],\ A[i],\ A[j^*+1],\dots,A[i-1]]$$ $A[i] \ge A[j^*] \ge$ solundaki her şey (hypothesis: sol kısım sorted). $j^*$'ın seçiminden $A[i] < A[j^*+1] \le$ sağındaki her şey. Diğer element'lerin sırası değişmedi. O hâldeA[:i+1]sorted. - Conclusion. Hypothesis her $0 \le i \le n-1$ için doğru. $i = n-1$ olduğunda
A[:n], yani bütün array sorted. ∎
- Invariant "ilk $i+1$ element sorted" der, "son yerlerinde" demez. Slayt örneğinde 3. iteration'dan sonra array
[3, 4, 6, 8, 5]olur: ilk dört element sorted ama 6 ile 8 son yerlerinde değil, 5 gelince shift edilecekler. (Concept check sorusu.) - Base case'i $i = 1$ diye yazıp tek element dışında bir şey iddia etme. CS161'de base case $i = 0$, yani "algoritma başlamadan önce".
- El notu $j^*$ için $A[j^*] < A[k]$ yazıyor, ders notu $A[j^*] \le A[i]$. Kod
A[j] > currentyanlış olunca durduğu için eşit element'lerde doğru olan $\le$ sürümü; proof'u onunla yaz. - Conclusion'ı atlama. "Sonuçta sorted" diyebilmek için invariant'ın son iteration'da neye denk geldiğini söylemen gerekir.
"Why does the InsertionSort correctness proof need a loop invariant — what specifically would you fail to prove without one?"
İpucu 1
Inductive step'te $A[i]$'nin doğru yere oturduğunu gösterirken hangi bilgiyi kullandın? O bilgi nereden geliyordu?
İpucu 2
Sol kısım sorted olmasaydı "$A[j^*]$'ın solundaki her şey $\le A[j^*]$" diyebilir miydin?
Çözümü göster
Tek bir iteration'ı tek başına incelersen yalnızca "current, kendisinden büyükleri geçip durdu" diyebilirsin. Bunun sorted bir sonuç verdiğini söylemek için current'ın solundakilerin sorted olması gerekir: $A[i] \ge A[j^*]$ ve $A[j^*]$ solundakilerin hepsinden büyük ya da eşitse, $A[i]$ de hepsinden büyük ya da eşittir. Bu bilgi bir önceki iteration'dan gelir. Invariant, iteration'ları birbirine bağlayan cümledir. Onsuz (1) her iteration'ın bir öncekinin bıraktığı düzene dayandığını ifade edemezsin, (2) algoritma bittiğinde bütün array'in sorted olduğu sonucuna varamazsın.
InsertionSort proof'unda inductive hypothesis hangisi?
Running time: best case ve worst case
Bilkent sürümünde $t_j$, $j$. iteration'da while testinin kaç kez çalıştığını sayar (1-indexed, $j = 2..n$). Shift sayısı $t_j - 1$, çünkü son test hep "dur" der.
- Sorted input: her iteration'da ilk test başarısız olur, $t_j = 1$. $\sum_{j=2}^{n} t_j = n-1$ test, sıfır shift.
- Reverse sorted input: key her seferinde en başa gider, $t_j = j$. $\sum_{j=2}^{n} j = \frac{n(n+1)}{2} - 1$. $n = 8$ için 35.
$i$. iteration'da (CS161 index'iyle) inner loop en fazla $i$ shift yapar. Toplam:
$$\text{shifts} \le \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} \qquad\Rightarrow\qquad \text{worst case } \Theta(n^2)$$- Worst case (reverse sorted): $\frac{n(n-1)}{2}$ shift, $\Theta(n^2)$.
- Best case (sorted): $n-1$ comparison, 0 shift, $\Theta(n)$. Outer loop yine $n-1$ iteration döner.
- Average case (bütün permutation'lar equally likely): inner loop ortalama $i/2$ shift yapar, yine $\Theta(n^2)$.
- "InsertionSort $\Theta(n^2)$'dir" cümlesi eksik. Doğrusu: worst-case running time'ı $\Theta(n^2)$. Bütün input'lar için söylenebilecek olan: $O(n^2)$ ve $\Omega(n)$.
- Worst case analysis "algoritma hep yavaş" demek değil (Class Prep S12). InsertionSort'un worst case'i $n^2$, sorted input'ta ise linear. Aradaki fark input'a bağlı; bir sonraki bölüm bu farkı tek bir sayıyla ölçüyor.
InsertionSort'un worst-case running time'ı için hangisi doğru? (CS161 concept check)
Temel araç: inversion sayısı
Bir shift'te A[j] > current ve A[j] current'ın sağına geçiyor. Yani ters sırada duran tam bir pair düzeliyor, başka hiçbir pair'in sırası değişmiyor. O hâlde algoritmanın yaptığı shift sayısı, input'ta ters duran pair'lerin sayısına eşit.
1. bölümdeki lab'da "kalan inversion + yapılan shift" sayacı bu yüzden hiç değişmiyordu: her shift kalan inversion'ı tam bir azaltıp shift sayacını bir artırıyor. Başta shift 0, sonda kalan inversion 0; aradaki sabit de input'un inversion sayısı. Bir algoritma boyunca değişmeyen bu tür bir büyüklüğe invariant (korunan büyüklük) denir.
$i < j$ ve $A[i] > A[j]$ ise $(i, j)$ pair'i bir inversion. $I$ = input'taki inversion sayısı. $0 \le I \le \binom n2 = \frac{n(n-1)}{2}$.
[2, 3, 8, 6, 1]: inversion'lar $(2,1), (3,1), (8,6), (8,1), (6,1)$, yani $I = 5$. InsertionSort bu array'de tam 5 shift yapar.
- $n$ terimi: hiç shift olmasa bile outer loop $n-1$ iteration döner ve her iteration'da en az bir comparison yapılır.
- $I$ terimi: shift sayısı tam olarak $I$. Comparison sayısı $I$ ile $I + n - 1$ arasında.
Sınav tarifi: (1) input'un şeklini yaz, (2) hangi pair'lerin ters durduğunu say, (3) $\Theta(n + I)$ yaz, (4) dominant term'e sadeleştir.
Cevabı yalnızca $\Theta(I)$ diye yazma. Sorted array'de $I = 0$ ama running time sıfır değil, $\Theta(n)$. $n$ terimini ancak $I$ ondan büyükse düşürebilirsin.
Slayttaki [6, 4, 3, 8, 5] array'inde InsertionSort kaç shift yapar?
Özel input'lar: inversion say, running time'ı yaz
Hoca çoğu zaman "worst case" yerine belirli bir input verip InsertionSort'un running time'ını soruyor. Hepsinde tarif aynı: $I$'yı say, $\Theta(n + I)$ yaz.
| Input | Örnek | $I$ | Running time |
|---|---|---|---|
| Sorted | 1 2 3 4 5 6 | 0 | $\Theta(n)$ |
| Reverse sorted | 6 5 4 3 2 1 | $\frac{n(n-1)}{2}$ | $\Theta(n^2)$ |
| Bütün element'ler eşit | 4 4 4 4 4 | 0 (eşit element'ler inversion değil) | $\Theta(n)$ |
| Ardışık pair'ler swap edilmiş | 2 1 4 3 6 5 | $\lfloor n/2 \rfloor$ | $\Theta(n)$ |
| Circular shift $k$ | 5 6 1 2 3 4 ($k=2$) | $k(n-k)$ | $\Theta(n + k(n-k))$, sonraki bölüm |
Bütün element'ler eşitken $\Theta(n)$ çıkmasının sebebi koşulun strict > olması: A[j] > current eşitlikte yanlış olduğu için inner loop hemen durur. Koşul >= olsaydı her element bütün eşitlerini geçip başa giderdi: $\frac{n(n-1)}{2}$ shift, $\Theta(n^2)$. Sınavda kodu dikkatle oku.
Kodu kendin boz. Aşağıdaki lab 1. bölümdekiyle aynı, ama bir anahtarı var: koşulu A[j] >= key yapıyor. Önce strict hâliyle oynat, sonra anahtarı aç ve aynı input'u yeniden oynat. Köşedeki ilk index'lere ve "kalan inversion + shift" kutusuna bak: eşit element'ler birbirini geçtiğinde inversion azalmıyor ama shift artıyor, yani toplam artık sabit kalmıyor.
Önce tahmin et: 4 4 4 4 4 array'inde koşul A[j] >= key olunca shift sayacı kaça çıkar, ve sonunda köşedeki index'ler hangi sırada durur?
"What would the complexity of InsertionSort be if all the elements were equal? Explain in terms of the inner loop and shifting behavior."
İpucu 1
Inner loop'un koşulunu yaz: A[j] > current. Bütün değerler aynıyken bu koşul ilk kontrolde ne verir?
Çözümü göster
Her iteration'da A[i-1] > current eşitlik yüzünden yanlış; inner loop bir comparison yapıp hiç shift etmeden çıkar. Toplam: $n-1$ iteration, her biri $O(1)$, sıfır shift. Inversion sayısı da 0. Running time $\Theta(n)$, best case ile aynı.
"What is the complexity of Insertion sort for an input scenario where two numbers inside every consecutive pair of a sorted array are switched. For example, A = [7, 6, 9, 8, 11, 10, 12, 11, …, aj, aj-1, …, an, an-1]."
İpucu 1
Aynı pair'in içindeki iki element ters mi? Farklı pair'lerden iki element ters olabilir mi? $(7,6)$ pair'inin her element'ini $(9,8)$ pair'inin her element'iyle karşılaştır.
İpucu 2
Her pair tam bir inversion veriyor. Kaç pair var?
Çözümü göster
- Şekil: sorted array $a_1 < a_2 < \dots < a_n$, input $a_2, a_1, a_4, a_3, \dots$
- Pair içi: $a_{2m} > a_{2m-1}$ ve önde duruyor, yani her pair 1 inversion.
- Pair'ler arası: $p$. pair'in iki element'i de $(p+1)$. pair'in iki element'inden küçük; buradan inversion çıkmaz.
- $I = \lfloor n/2 \rfloor$. Her inner loop en fazla 1 shift yapar.
- $T(n) = \Theta(n + n/2) = \Theta(n)$.
$n = 10$ için Python: 5 shift, 13 comparison. $n$ tek ise son element tek başına kalır ve zaten yerindedir; sonuç değişmez.
Koddaki A[j] > current koşulunu A[j] >= current yaparsak, $n$ eşit element'li bir array'de running time ne olur?
Sınav kalıbı: circular shift
2019-20 quiz'inde ve 2020-21 vizesinde aynı soru çıktı: sorted bir array $k$ konum sağa circular shift edilmiş, InsertionSort ne kadar sürer? Önce ölçelim. Aşağıda $n = 10$ element'li sorted array her $k$ için döndürülüyor, InsertionSort gerçekten çalıştırılıyor ve shift'ler sayılıyor.
Sağa $k$ konum circular shift edince en büyük $k$ element başa gelir. Input iki sorted block'tan oluşur: önce büyükler ($k$ tane), sonra küçükler ($n-k$ tane).
- Block içinde inversion yok (iki block da sorted).
- Her büyük element her küçük element'ten önde ve ondan büyük: $k \cdot (n-k)$ inversion.
Durumlar: $k$ constant ya da $n-k$ constant ⇒ $\Theta(n)$. $k = n/2$ ⇒ $n^2/4$ ⇒ $\Theta(n^2)$. $k \le n/2$ iken $\frac{nk}{2} \le k(n-k) \le nk$, yani $\Theta(nk)$.
"A bank keeps record of its customers in an array A[1...n] sorted by account numbers. However, a bank accountant accidentally shifts the array elements k positions to the right in a circular fashion. For example, if A=[9, 12, 17, 21, 33, 41], it becomes [33, 41, 9, 12, 17, 21] when shifted k=2 positions, and becomes [17, 21, 33, 41, 9, 12] when shifted k=4 positions. The accountant realizes the problem and wants to fix it by sorting the array again using insertion sort. Find the complexity of insertion sort for such an input scenario?"
İpucu 1
$k = 2$ örneğinde inversion'ları tek tek yaz. 33 hangi element'lerden önde ve onlardan büyük? 41?
İpucu 2
Array'i iki sorted block olarak düşün. Inner loop'ta current olan küçük element kaç büyük element'i geçmek zorunda?
İpucu 3
Cevabı hem $n$ hem $k$ cinsinden yaz, sonra $k$ constant ve $k = n/2$ durumlarını ayrıca söyle.
Çözümü göster
- Input şekli: $[a_{n-k+1}, \dots, a_n,\ a_1, \dots, a_{n-k}]$. İlk $k$ element en büyükler, sonra kalan $n-k$ küçük element geliyor; iki block da kendi içinde sorted.
- İlk $k$ iteration: büyük block sorted, hiç shift yok.
- Kalan $n-k$ iteration: her küçük element current olduğunda $k$ büyük element'in hepsini geçer (hepsi ondan büyük), sonra önündeki küçük element'te durur. Her iteration'da $k$ shift.
- Toplam: $k(n-k)$ shift $= I$, artı $n-1$ outer loop iteration'ı. $T(n,k) = \Theta(n + k(n-k))$.
- Örnekte: $n = 6,\ k = 2$: $I = 8$, inversion'lar $(33,9), (33,12), (33,17), (33,21), (41,9), (41,12), (41,17), (41,21)$.
- Sonuç: $k$ ya da $n-k$ constant ise $\Theta(n)$; $k = \Theta(n)$ ve $n - k = \Theta(n)$ ise (örneğin $k = n/2$) $\Theta(n^2)$.
Sorudaki ikinci örnek de aynı formüle uyuyor: $k = 4$ için [17, 21, 33, 41, 9, 12], $I = 4 \cdot 2 = 8$. $k$ ile $n-k$ yer değiştirince inversion sayısı aynı kalır.
Altungöz'ün puanlanmış kâğıdı $n = 6$ için $k = 1..5$ değerlerinde 5, 8, 9, 8, 5 inversion sayıp $O(n + k(n-k))$ yazıyor. Bu sayılar $k(6-k)$ ile birebir aynı.
"Suppose you are given an Array A[1….n] of sorted integers that has been circularly shifted k positions to the right. a. Complexity of insertion sort?" (sorunun bu bölümle ilgili kısmı; (b) QuickSort dersinde, (c) 9. bölümde)
İpucu 1
Bu, banka sorusunun örneksiz hâli. Input'u iki sorted block olarak yaz ve hangi pair'lerin ters durduğunu say.
İpucu 2
Cevabı $\Theta(n + I)$ kalıbıyla ver; $k$ küçükken ve $k \approx n/2$ iken ne olduğunu ayrıca söyle.
Çözümü göster
- Shift sonrası array: önce en büyük $k$ element (sorted), sonra kalan $n-k$ element (sorted).
- Block'ların içinde inversion yok. Büyük block'taki her element, küçük block'taki her element'ten önde ve büyük: $I = k(n-k)$.
- InsertionSort'un shift sayısı $I$'ya eşit, outer loop da $n-1$ kez döner: $T(n) = \Theta(n + k(n-k))$.
- $k = O(1)$ ya da $n - k = O(1)$ ⇒ $\Theta(n)$. $k = n/2$ ⇒ $I = n^2/4$ ⇒ $\Theta(n^2)$. Genel olarak $k \le n/2$ için $\Theta(nk)$.
$k \ge n$ ise shift $k \bmod n$ ile aynı sonucu verir. Array'de tekrar eden değer varsa eşit pair'ler inversion sayılmaz, $I \le k(n-k)$ olur; upper bound değişmez.
Sorted bir array'de $p$ konumundan başlayan $k$ ardışık element'lik bir block reverse edilmiş ($k \ll n$ ama constant olmak zorunda değil). InsertionSort'un bu input'taki complexity'sini analiz et.
İpucu 1
Yine $\Theta(n + I)$. Bir inversion'ın iki element'i nerede olabilir: ikisi de block'un içinde mi, biri içinde biri dışında mı, ikisi de dışında mı? Her durumu ayrı düşün.
İpucu 2
Block'un solundaki bir element, block'taki her element'ten küçük mü büyük mü? Sağındaki? Reverse sorted $k$ element'lik bir array'de kaç inversion olduğunu 5. bölümdeki tablodan hatırla.
Sorted array $k = \sqrt n$ konum sağa circular shift edilirse InsertionSort'un running time'ı ne olur?
MergeSort ve Merge adımı
Masada iki sorted deste var, her destenin en küçük kartı üstte. İki üst karttan küçüğünü alıp output'a koyuyorsun. Her adımda bir kart çıkıyor; $m$ kartlık iş $m$ adımda bitiyor. MergeSort bu fikri divide and conquer ile kullanır.
def MergeSort(A):
n = len(A)
if n <= 1:
return A # taban: 0 ya da 1 eleman zaten sıralı
L = MergeSort(A[:n//2]) # divide + conquer: sol yarı
R = MergeSort(A[n//2:]) # sağ yarı
return Merge(L, R) # combine
Merge'ü izle. İki sorted list'i kendin yazabilir ya da bir preset seçebilirsin. ↑i ve ↑j her list'te sıradaki en küçük element'i gösterir; pointer'lar yalnızca ileri gider. İki list'te de geçen bir değer 2ᴸ (soldan) ve 2ᴿ (sağdan) diye işaretlenir. Comparison'ın < ya da <= olması, eşit element'lerin output'taki sırasını değiştiriyor.
Önce tahmin et: L = 3 4 6 8, R = 1 2 5 7 için kaç comparison yapılır? Toplam 8 element var; cevap her zaman 7 mi?
$k$ adım sonra $S$, $L \cup R$'nin en küçük $k$ element'ini sorted olarak içerir; $L[i]$ ve $R[j]$ kendi list'lerinde kalanların en küçüğüdür. Sıradaki en küçük element bu ikisinden biri olmak zorunda, o yüzden ikisinin küçüğünü almak invariant'ı korur. $m = |L| + |R|$ adımdan sonra $S$ bütün element'leri sorted olarak içerir.
Running time: her adım bir element ekler ve constant iş yapar: Merge $\Theta(m)$.
- CS161 notlarındaki Merge pseudocode'u bilerek eksik bırakılmış: list'lerden biri bitince
L[i]array'in dışına taşar. Düzeltme: bir list bitince diğerinin kalanını olduğu gibi ekle (animasyondaki son satır). - CS161 sürümü
if L[i] < R[j]kullanıyor ve eşitlikte sağdan alıyor. Bu, eşit key'li element'lerin sırasını bozar. CLRS sürümü<=ile soldan alır ve stable olur (9. bölüm).
İki sorted array'in toplam uzunluğu $n$. Merge için en iyi (en tight) upper bound hangisi? (CS161 concept check)
MergeSort: correctness ve recursion tree
- Inductive hypothesis. MergeSort uzunluğu $\le i$ olan bir array döndürdüğünde o array sorted'dır.
- Base case. $i = 1$: 0 ya da 1 element'li array sorted'dır.
- Inductive step. Uzunluğu $i$ olan bir input'ta $L$ ve $R$'nin uzunluğu $\le i-1$; hypothesis'ten ikisi de sorted döner. Merge iki sorted array'i sorted şekilde birleştirir (Merge invariant'ı). Sonuç sorted.
- Conclusion. Her $n$ için MergeSort sorted bir array döndürür.
Şimdi running time. Oynat: önce divide level'ları aşağı iner, sonra Merge'ler yukarı çıkar. Her level'da toplam kaç element yazıldığına bak.
- Level $t$: $2^t$ subproblem, her biri $n/2^t$ uzunluğunda.
- Bir node'un işi (uzunluk $m$): base case kontrolü 2, yarıları kopyalama $m+2$, Merge $4m+2$ işlem; toplam $\le 11m$.
- Level başına: $2^t \cdot 11\frac{n}{2^t} = 11n$. Bu sayı level'dan bağımsız.
- Level sayısı: $n$, 1'e inene kadar $\log n$ kez yarıya bölünür: level'lar $0, 1, \dots, \log n$, yani $\log n + 1$ tane.
Aynı şeyin recurrence hâli: $T(n) \le 2T(n/2) + 11n$. Bir sonraki ders bunu Master theorem ile çözüyor.
"Where exactly does the 'log n' in MergeSort's $\Theta(n\log n)$ come from — connect it to the recursion tree's depth."
İpucu 1
Level $t$'deki subproblem'lerin uzunluğu $n/2^t$. Bu ne zaman 1 olur?
Çözümü göster
$n/2^t = 1 \iff t = \log n$: tree'nin depth'i $\log n$, level sayısı $\log n + 1$. Her level'da subproblem sayısı ikiye katlanır, uzunluk yarıya iner; ikisi birbirini götürür ve her level $\Theta(n)$ iş yapar. Toplam = level başına iş × level sayısı = $\Theta(n) \cdot (\log n + 1)$. Log, "kaç kez yarıya bölebilirim" sorusunun cevabı.
(a) MergeSortThirds array'i üçe böler, üç parçayı recursive olarak sort eder, Merge(Merge(L, M), R) ile birleştirir. Normal MergeSort'tan asymptotic olarak hızlı mı? (b) MergeSortN array'i $n$ tane tek element'li parçaya ayırır, sonra sortedA = Merge(sortedA, sublist) ile tek tek birleştirir. Pepper "her Merge $O(1)$, toplam $O(n)$" diyor. Hata nerede?
İpucu 1
(a) Recurrence'ı yaz: kaç subproblem var, uzunlukları ne, combine adımı ne kadar sürüyor? İki Merge'ün maliyetini ayrı ayrı topla.
İpucu 2
(b) sortedA'nın uzunluğu her iteration'da ne oluyor? Merge'ün running time'ı iki list'in toplam uzunluğuna bağlı.
Çözümü göster
(a) Merge(L, M) $2n/3$, Merge(temp, R) $n$ element yazar: $T(n) = 3T(n/3) + \Theta(n)$. Level $t$'de $3^t$ subproblem var, her biri $n/3^t$: level başına $\Theta(n)$, $\log_3 n + 1$ level ⇒ $\Theta(n\log n)$. $\log_3 n = \log n / \log 3$, yani fark yalnızca bir constant factor; asymptotic olarak daha hızlı değil.
(b) Merge $O(\text{iki listenin toplam boyu})$. sortedA büyüyor: $k$. Merge'de $(k-1) + 1 = k$ element yazılır. Toplam $\sum_{k=1}^{n} k = \frac{n(n+1)}{2} = \Theta(n^2)$. Pepper sol list'in uzunluğunu $O(1)$ sanmış. Bu algoritma aslında InsertionSort'un bir biçimi.
$n$ element'li bir array'de MergeSort, Merge'ü toplam kaç kez çağırır? (CS161 concept check)
Dört n/4 parça; iki n/2 parçayı ikişer kez çözme; 1 ve n−1 bölme; Θ(n²) merge. Her birinin running time’ını bul.
İpucu
Çözümü göster
Sırasıyla 4T(n/4)+Θ(n) → Θ(n log n); 4T(n/2)+Θ(n) → Θ(n²); T(n−1)+Θ(n) → Θ(n²); 2T(n/2)+Θ(n²) → Θ(n²). Sonuncuda level işleri n²,n²/2,…; fazladan log çarpanı yok.
Input'a bakmamak, stability ve pratikte seçim
MergeSort input'a "bakmaz": array'i değerlerden bağımsız olarak hep ortadan böler ve her Merge, merge ettiği her element'i bir kez yazar. CS161 notlarındaki örnek: [1, 2, 3, 5, 4, 6, 7, 8] neredeyse sorted, ama MergeSort yine $\log n + 1$ level'ın hepsini yapar.
- MergeSort her input'ta $\Theta(n\log n)$: best = worst = average. Recursion tree input'tan bağımsız, her level $\Theta(n)$.
- InsertionSort $\Theta(n + I)$: input'a çok bağlı, $\Theta(n)$ ile $\Theta(n^2)$ arasında.
- Stability: eşit key'li element'lerin input'taki göreli sırası korunuyorsa sorting stable'dır. InsertionSort (strict
>) stable. MergeSort, Merge eşitlikte soldan alırsa (<=) stable.
"Suppose you are given an Array A[1….n] of sorted integers that has been circularly shifted k positions to the right. c. Complexity of merge sort?" (sorunun bu bölümle ilgili kısmı; (a) 6. bölümde)
İpucu 1
MergeSort array'i nereden böler? Bu karar $k$'ya ya da değerlere bağlı mı?
İpucu 2
Uzunluğu $m$ olan bir Merge, input ne olursa olsun output'a kaç element yazar? Bir level'da toplam kaç element yazılır?
Çözümü göster
- MergeSort her zaman ortadan böler; recursion tree'nin şekli yalnızca $n$'ye bağlı, $k$'ya bağlı değil. $\log n + 1$ level var.
- Uzunluğu $m$ olan bir Merge $m$ element yazar; comparison sayısı input'a göre değişse de $\min(|L|, |R|)$ ile $m - 1$ arasında kalır. Yani her Merge $\Theta(m)$.
- Her level'da Merge'lerin toplam uzunluğu $n$: level başına $\Theta(n)$.
- Sonuç: $T(n) = \Theta(n\log n)$, her $k$ için. Recurrence: $T(n) = 2T(n/2) + \Theta(n)$.
InsertionSort'la farkı: orada cevap $k$'ya bağlıydı ($\Theta(n + k(n-k))$), burada değil. $k$ küçükse InsertionSort daha hızlı ($\Theta(n)$), $k \approx n/2$ ise MergeSort daha hızlı.
Python, $n = 1024$: her $k$ için tam $10240 = n\log n$ element yazıldı; comparison sayısı $k$'ya göre 5120 ile 6133 arasında değişti.
"(a) (9 points) Give the asymptotic time-complexities of Insertion-, Merge-, and Quick-sort (i.e., with Hoare) when all the elements are identical." (2023-24 vizesinde S4(a) olarak 10 puanla aynı soru çıktı.)
İpucu 1
InsertionSort: eşit element'ler inversion mı? Inner loop'un koşulu eşitlikte ne verir?
İpucu 2
MergeSort: recursion tree'nin şekli değerlere bağlı mı? Eşitlik varken Merge daha az element mi yazıyor?
Çözümü göster
InsertionSort: $\Theta(n)$. A[j] > current eşitlikte yanlış; her iteration'da bir comparison, sıfır shift. $I = 0$, $\Theta(n + 0)$.
MergeSort: $\Theta(n\log n)$. Divide adımı değerlere bakmaz, tree yine $\log n + 1$ level. Her Merge, merge ettiği $m$ element'in hepsini output'a yazar: level başına $\Theta(n)$. (CS161 Merge'ü eşitlikte hep sağdan alır; comparison sayısı $\frac n2 \log n$ olur, $n = 8$ için 12. Yine $\Theta(n\log n)$.)
QuickSort (Hoare): $\Theta(n\log n)$. Hoare partition'da i A[i] >= pivot'ta, j A[j] <= pivot'ta durur. Bütün element'ler eşitken ikisi de her adımda hemen durur, swap yapılır ve pointer'lar ortada buluşur. Split dengeli: $T(n) = 2T(n/2) + \Theta(n)$. (Lomuto partition'da ise bütün element'ler pivot'tan küçük ya da eşit sayılır, split $n-1$ ile 0 olur ve $\Theta(n^2)$ çıkar. Ayrıntı QuickSort dersinde.)
| Durum (Class Prep S16) | Seçim | Neden |
|---|---|---|
| Küçük $n$ | InsertionSort | Constant'ları küçük. Bu ders notunun kaba constant'larıyla $n^2/2$, $11n(\log n + 1)$'i ancak $n = 189$ civarında geçiyor. |
| Neredeyse sorted (az inversion) | InsertionSort | $\Theta(n + I)$; $I$ küçükse neredeyse linear. MergeSort yine $n\log n$. |
| Memory kısıtlı | InsertionSort | In-place, constant extra memory. MergeSort'un Merge'ü $\Theta(n)$ boyunda ek bir array ister. |
| Büyük, rastgele ya da kötü input | MergeSort | Worst-case garantisi $\Theta(n\log n)$. |
| İkisi birden | Hybrid | MergeSort, subarray'ler küçülünce InsertionSort'a geçer (CLRS 4e Problem 2-1). |
MergeSort'un worst case'i asymptotic olarak daha iyi, ama MergeSort her input'ta daha hızlı değil: sorted array'de InsertionSort $\Theta(n)$, MergeSort $\Theta(n\log n)$. Ters yön de geçerli: A bazı input'larda B'den hızlı diye A'nın worst case'i daha iyi olmaz.
Hangisi doğru? (CS161 concept check)
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
Reverse sorted, 8 element'li bir array'de InsertionSort kaç shift yapar?
[33, 41, 9, 12, 17, 21] ($k = 2$ circular shift) için InsertionSort'un shift sayısı kaç?
MergeSort zaten sorted olan bir array'de ne kadar sürer?
InsertionSort proof'unun inductive step'inde $j^*$ neden "$A[j^*] \le A[i]$ olan en büyük index" olarak seçiliyor?
Merge if L[i] < R[j] ile yazılmışsa, eşit key'li iki element'ten hangisi önce çıkar?