Comparison model
CS161'in şakası: $n$ çubuğu boyuna göre sıralamak için hepsini dikey tutup masaya bırak. Hepsi masaya değer ve üst uçlarına bakınca sorted order görünür. "$O(1)$'de sıraladım!"
Hile nerede? Çubuklar array'deki sayılar değil ve "masaya bırakmak" bir bilgisayarın yapabildiği bir işlem değil. Yani sonucu hangi işlemlere izin verdiğin belirliyor. Buna model of computation denir.
Algoritma elemanların değerini göremez. Elemanlar hakkında bilgi almanın tek yolu bir genie'ye soru sormak: "$a_i \le a_j$ mi?" Cevap evet ya da hayır.
Şimdiye kadar gördüğümüz bütün sorting algorithm'lar böyle çalışır: InsertionSort, MergeSort, QuickSort. QuickSort partition sırasında "7, pivot 5'ten büyük mü?" diye sorar, başka bir şey yapmaz.
- Comparison model: her algoritma worst case'te en az $\Omega(n\log n)$ adım atar. Buna karşılık comparable olan her nesneyi (string, tarih, kesir…) sıralayabilir.
- Değerleri kullanan model: elemanlar küçük integer'lar ise değeri array index'i olarak kullanabilirsin (CountingSort, RadixSort). Burada $O(n)$ mümkün.
Bir algoritmanın comparison-based olup olmadığını kodda < var mı diye bakarak anlayamazsın. Asıl soru şu: algoritma elemanlar hakkındaki bilgiyi nereden alıyor? CountingSort'taki C[A[j]] değeri index olarak kullanır. Bu bir comparison sayılmaz, değere doğrudan erişimdir.
Hangisi comparison-based bir sorting algorithm değildir?
Decision tree
Algoritmayı ve $n$'i sabit tut. Algoritmanın sorduğu her soru bir branch: cevap "≤" ise bir yöne, ">" ise öbür yöne gidilir. Bütün olası çalışmaları üst üste koyunca bir binary tree çıkar.
Aşağıdaki tree, InsertionSort'u 3 elemanın 6 permutation'ı üzerinde gerçekten çalıştırıp sorduğu soruları birleştirerek üretiliyor. Bir input seç ve oynat.
- Internal node $i\!:\!j$ = "$a_i$ ile $a_j$'yi karşılaştır". İki child'ı var: $a_i \le a_j$ ve $a_i > a_j$.
- Leaf = output: elemanların hangi sırayla dizileceği. Örneğin $\langle 2,3,1\rangle$ "önce $a_2$, sonra $a_3$, sonra $a_1$" demek.
- Bir input üzerinde çalıştırmak = root'tan bir leaf'e giden tek bir path.
- O input'taki comparison sayısı = path'in uzunluğu. Worst-case = tree'nin height'ı (en uzun path).
- Her algoritma ve her $n$ için ayrı bir tree vardır. "MergeSort'un tree'si" diye tek bir tree yok. $n = 3$ için bir tane, $n = 4$ için başka bir tane var.
- Tree sadece comparison'ları sayar. Atama, kaydırma gibi işler görünmez. Bu sorun değil: running time en az comparison sayısı kadardır, yani comparison sayısı için bulunan lower bound running time için de lower bound'dur.
Input $\langle a_1, a_2, a_3\rangle = \langle 5, 8, 2\rangle$. InsertionSort'un tree'sinde hangi leaf'e, kaç comparison'la varılır?
n! leaf, height en az log₂ n!
3 farklı eleman $3! = 6$ farklı sırada gelebilir. Doğru bir algoritma bu 6 durumda 6 farklı şey yapmak zorunda, çünkü her birinde elemanları başka bir düzende yeniden dizmesi gerekiyor.
- En az $n!$ leaf. İki farklı input sırası $\pi \ne \sigma$ aynı leaf'e düşseydi, algoritma ikisinde de aynı yeniden dizmeyi yapardı. Bu dizme en fazla birini sıralar, öbüründe output yanlış olur. Yani her permutation'ın kendi leaf'i var.
- Height'ı $h$ olan bir binary tree'nin en fazla $2^h$ leaf'i vardır (her level'da node sayısı en fazla ikiye katlanır).
- Birleştir: $2^h \ge n!$, yani $h \ge \log_2(n!)$. $h$ integer olduğundan $h \ge \lceil \log_2 n! \rceil$.
| $n$ | $n!$ | $\log_2 n!$ | En az comparison | Gerçek algoritmalar (worst case) |
|---|---|---|---|---|
| 3 | 6 | ≈ 2.585 | 3 | InsertionSort 3 → optimal |
| 4 | 24 | ≈ 4.585 | 5 | MergeSort 5 ($1+1+3$), InsertionSort 6 |
Aynı argümanı bir oyun olarak da kurabilirsin. Karşında bir adversary var: kutulardaki değerleri baştan seçmiyor. Her soruda, o ana kadar verdiği cevaplarla uyumlu sıralamalardan daha kalabalık grubu ayakta tutacak cevabı veriyor. Tek bir comparison kalan sıralamaları en iyi ihtimalle yarıya indirdiği için $n!$ sıralamadan bire inmek en az $\lceil\log_2 n!\rceil$ soru ister.
Önce tahmin et: 4 kutuda, adversary ne yaparsa yapsın, sıralamayı en az kaç comparison'la kesinleştirebilirsin?
Kutulardaki değerler gizli ve hepsi farklı. Bir kutuya, sonra başka bir kutuya tıkla: adversary ikisinden hangisinin küçük olduğunu söyler. Tek bir sıralama kalınca oyun biter.
- "Tree'nin tam $n!$ leaf'i var" deme. Doğrusu en az $n!$: bazı algoritmalar gereksiz soru sorar, hiç ulaşılmayan leaf'ler olabilir.
- Lower bound worst case için geçerli. Bazı input'lar kısa yoldan biter: InsertionSort sorted input'ta sadece $n-1$ comparison yapar. Bu, bound ile çelişmez.
- Leaf sayısı ile height'ı karıştırma: $n = 4$'te 24 leaf var ama gereken comparison sayısı 5.
4 farklı elemanı sıralayan her comparison-based algoritma worst case'te en az kaç comparison yapar?
log n! = Ω(n log n) ve theorem
$n! = n\cdot(n-1)\cdots 2\cdot 1$. Çarpanların büyük yarısının her biri en az $n/2$. $n=8$: $8\cdot7\cdot6\cdot5 \ge 4^4$. Yani $n!$ en az $(n/2)^{n/2}$ kadar.
En büyük $\lceil n/2\rceil$ çarpanın her biri $\ge n/2$, geri kalanlar $\ge 1$:
$$n! \ \ge\ \left(\tfrac n2\right)^{n/2} \quad\Rightarrow\quad \log n! \ \ge\ \tfrac n2 \log\tfrac n2 = \tfrac n2(\log n - 1).$$$n \ge 4$ iken $\log n \ge 2$, yani $\log n - 1 \ge \tfrac12 \log n$. O zaman $\log n! \ge \tfrac n4 \log n$. $c = \tfrac14,\ n_0 = 4$ ile $\log n! = \Omega(n\log n)$.
Upper bound: $n! \le n^n$, yani $\log n! \le n\log n$. İkisi birlikte: $\log n! = \Theta(n\log n)$.
Bilkent slaytı (2025-26) Stirling'i kullanır: $n! \ge (n/e)^n$, yani $\log n! \ge n\log n - n\log e = \Omega(n\log n)$. Sınavda yukarıdaki yarıya bölme proof'u yeterli ve ezber gerektirmiyor.
- Her deterministic comparison-based sorting algorithm worst case'te $\Omega(n\log n)$ adım atar.
- Her randomized comparison-based sorting algorithm in expectation $\Omega(n\log n)$ adım atar. Yani bound expected running time için de geçerli ve random pivot, QuickSort'u $n\log n$'in altına indiremez. Proof'undan sorumlu değilsiniz (slayt 20).
- Sonuç: MergeSort (ve HeapSort) asymptotically optimal. Daha iyisini aramaya gerek yok.
Theorem "her sorting algorithm $\Omega(n\log n)$" demiyor. Sadece comparison model'deki algoritmalar için geçerli. CountingSort ve RadixSort bu modelin dışında kalıyor, o yüzden $O(n)$ olabiliyorlar.
"Show that $\log(n!) = \Theta(n\log n)$." Handout upper bound'u $n! \le n^n$ ile gösteriyor, lower bound'u size bırakıyor.
İpucu 1
$\log(n!) = \log n + \log(n-1) + \dots + \log 1$. Bu toplamın sadece ilk yarısını tut, gerisini at (hepsi $\ge 0$).
İpucu 2
Tuttuğun $n/2$ terimin her biri $\ge \log(n/2)$. Sonra $\log(n/2) \ge \frac12\log n$ eşitsizliğinin hangi $n$'den itibaren doğru olduğunu bul.
Çözümü göster
$\log n! \ge \sum_{i=\lceil n/2\rceil}^{n} \log i \ge \frac n2\log\frac n2$. $n \ge 4$ için $\log\frac n2 = \log n - 1 \ge \frac12\log n$. Yani $\log n! \ge \frac14 n\log n$ ($c = \frac14$, $n_0 = 4$). Upper bound: $\log n! \le \log n^n = n\log n$ ($c = 1$, $n_0 = 1$). İkisi birlikte Θ verir. ∎
Bir arkadaşın "random pivot seçen bir comparison sort yazdım, expected running time'ı $O(n)$" diyor. Ne dersin?
Lower bound'u kullanmak
Sınavlarda lower bound çoğu zaman ispatlanmaz, kullanılır: "Şu şey mümkün olsaydı, $n$ elemanı $o(n\log n)$ comparison'la sıralardım. Bu imkânsız, o halde o şey de imkânsız."
Elinde 3 elemanı sıralayan bir 3-sort fonksiyonu var ve array'e sadece onunla dokunabiliyorsun. Kaç çağrı gerekir?
İpucu 1
Bir 3-sort çağrısının kaç farklı cevabı olabilir? 3 elemanın kaç sırası var?
İpucu 2
Decision tree artık binary değil, her node'un en fazla 6 child'ı var. Height'ı $h$ olan böyle bir tree'nin kaç leaf'i olabilir?
Çözümü göster
Her çağrı en fazla $3! = 6$ farklı cevap verir, yani tree'nin en fazla $6^h$ leaf'i var. $6^h \ge n!$ ⇒ $h \ge \log_6 n! = \dfrac{\log_2 n!}{\log_2 6} = \Omega(n\log n)$. Cevap $\Omega(n\log n)$; $\log_2 6$ sadece bir constant factor. Örneğin $n = 100$ için en az 204 çağrı.
Lucky'nin luckyTree'si comparable nesneleri tutan bir BST: luckyInsert $O(1)$, search ve delete $O(\log n)$, hepsi deterministic. Bu neden yanlış?
İpucu 1
Elinde $n$ eleman var. Hepsini luckyTree'ye koymak ne kadar sürer?
İpucu 2
Bir BST'den elemanları sorted order'da nasıl okursun, bu kaç comparison yapar?
Çözümü göster
Sorting algorithm şöyle: $n$ elemanı tek tek luckyInsert et ($n \cdot O(1) = O(n)$), sonra in-order traversal yap ($O(n)$, hiç comparison yok; BST property sayesinde output sorted). Toplam $O(n)$, deterministic ve sadece comparison kullanıyor (luckyTree her comparable nesneyi kabul ediyor). Bu, comparison-based sorting için $\Omega(n\log n)$ lower bound'uyla çelişir. O halde luckyTree var olamaz. ∎
Sınav: "Her eleman, sorted array'deki yerinden en fazla $k$ uzakta. Min-heap ile sırala ve tight upper bound'u ver." Biz bir adım ileri gidip hiçbir comparison-based algoritmanın bundan asymptotically daha iyisini yapamayacağını gösterelim.
İpucu 1
Önce sınavın cevabı: heap'te en fazla $k+1$ eleman var. $n$ kez "en küçüğü çıkar, sıradakini ekle" yapıyorsun. Her işlem kaç adım?
İpucu 2
Lower bound için: bu kurala uyan kaç farklı input sırası var, en azından kabaca? Sorted array'i $k$'lık bloklara böl ve her bloğun içini istediğin gibi karıştır.
İpucu 3
Decision tree'nin o kadar farklı leaf'i olmalı. $\log_2$'sini al ve önceki bölümdeki $\log k! \ge \frac k2\log\frac k2$ eşitsizliğini kullan.
Çözümü göster
Upper bound (sınavın sorusu). İlk $k+1$ elemandan bir min-heap kur: $O(k)$. Sonra $n$ kez: root'u çıkar ve output'a yaz, array'den sıradaki elemanı heap'e ekle. Heap'in boyutu hep $\le k+1$, her işlem $O(\log k)$. Toplam $O(k + n\log k) = O(n\log k)$. Algoritma doğru çalışır, çünkü sorted array'in $i$. elemanı input'ta en geç $i+k$. konumdadır; onu çıkarma sırası geldiğinde heap'in içindedir.
Lower bound. $k$, $n$'i bölsün. Sorted array'i $k$ uzunluğunda $n/k$ bloğa ayır ve her bloğun içini istediğin gibi karıştır. Her eleman en fazla $k-1 \le k$ yer kayar, yani her biri geçerli bir input. Böyle $(k!)^{n/k}$ farklı input var ve hepsinin doğru output'u farklı, dolayısıyla her birinin kendi leaf'i olmalı:
$$h \ \ge\ \log_2 (k!)^{n/k} = \tfrac nk \log k! \ \ge\ \tfrac nk\cdot\tfrac k2\log\tfrac k2 = \tfrac n2(\log k - 1) \ \ge\ \tfrac n4 \log k \quad (k \ge 4).$$Yani her comparison-based algoritma $\Omega(n\log k)$ comparison yapar ve heap algoritması optimal. $k = n$ olunca genel $\Omega(n\log n)$ bound'u geri gelir.
"Minimumu bulmak neden $\Omega(n)$?" sorusu decision tree ile değil, başka bir argümanla çözülür: minimum olmayan her eleman en az bir comparison kaybetmeli ve her comparison tek bir kaybeden üretir, yani en az $n-1$ comparison gerekir (S4 handout'u, problem 4.1). Decision tree burada sadece $\log_2 n$ verirdi (n olası cevap var), bu zayıf bir bound. Hangi argümanın daha güçlü bound verdiğine bak.
Concept check: comparable nesneler için insert, remove ve "en küçüğü döndür" işlemlerinin üçünün de $O(1)$ olduğu bir data structure mümkün mü?
CountingSort
$n$ öğrenciyi doğum ayına göre sırala. MergeSort $O(n\log n)$ sürer. Ama sadece 12 ay var: 12 bucket aç, her öğrenciyi kendi ayının bucket'ına at, bucket'ları Ocak'tan Aralık'a birleştir. Tek pass, $O(n + 12) = O(n)$.
CS161 bunu bucket'larla (FIFO linked list) anlatır. Bilkent slaytları ve CLRS aynı fikri bucket yerine counter ve prefix sum ile uygular. Aşağıdaki animasyon slayttaki örneği gerçekten çalıştırıyor: $A = [4,1,3,4,3]$, değerler $1..k$, $k = 4$. Aynı değerleri ayırt edebilmek için subscript koyduk.
- $C[1..k] = 0$. $\Theta(k)$
- Her $j$ için $C[A[j]]$++. Artık $C[i]$ = "değeri $i$ olan eleman sayısı". $\Theta(n)$
- Prefix sum: $C[i] \mathrel{+}= C[i-1]$. Artık $C[i]$ = "değeri $\le i$ olan eleman sayısı" = değeri $i$ olan son elemanın gideceği yer. $\Theta(k)$
- $j = n$'den $1$'e: $B[C[A[j]]] = A[j]$, sonra $C[A[j]]$−−. $\Theta(n)$
Toplam $\Theta(n+k)$, extra space $\Theta(n+k)$. $k = O(n)$ ise $\Theta(n)$.
- $k$ eleman sayısı değil, değerlerin range'i. $n$ sayı $[1, n^3)$ range'indeyse CountingSort $\Theta(n + n^3) = \Theta(n^3)$ sürer, MergeSort'tan çok daha kötü (concept check).
- Değerlerin integer olması ve range'in baştan bilinmesi gerekir. $[2,\ 12345,\ 21000,\ 100000000]$ gibi seyrek değerlerde yüz milyon bucket açarsın (CS161 slayt 29).
- 4. adımda sağdan sola gitmek keyfi bir seçim değil. Stability'yi bu sağlar (sonraki bölüm).
$A[i] \in \{1,\dots,k\}$. Array'i göremiyorsun, Siggi'ye sadece evet/hayır sorusu sorabiliyorsun. Sorted $A$'yı $O(k\log n)$ soruyla yaz.
İpucu 1
Sorted $A$'yı yazmak için neyi bilmen yeter? CountingSort'un 2. adımından sonra elinde ne vardı?
İpucu 2
Her $v$ değeri için "$A$'da en az $c$ tane $v$ var mı?" sorusu evet/hayır cevaplı ve $c$'ye göre monotonic. $c \in [0, n]$ üzerinde binary search yap.
Çözümü göster
Her $v = 1..k$ için $v$'nin sayısı $c_v$'yi binary search ile bul: "en az $c$ tane $v$ var mı?" sorusuyla $[0,n]$ aralığını yarıya böl, $O(\log n)$ soru. Toplam $k\cdot O(\log n)$. Sonra kâğıda $c_1$ tane 1, $c_2$ tane 2, … yaz. Bu, CountingSort'un sayma adımı; sayıları bilince sorted output bedavaya gelir.
Prefix sum'dan sonra $C = [1, 1, 3, 5]$. Loop $j = 5$'ten başlıyor ve $A[5] = 3$. Bu eleman $B$'de nereye yazılır, $C$ ne olur?
Stability (stable sorting)
Input: (Plucky, Oca), (Lucky, Oca), (Siggi, Nis), (Ollie, May). Hem {Plucky, Lucky, Siggi, Ollie} hem {Lucky, Plucky, Siggi, Ollie} doğru bir sıralama. Stable bir sorting algorithm her zaman ilkini verir: key'i eşit olanlar input'taki sıralarını korur.
Bir sorting algorithm şu durumda stable'dır: key'i eşit iki eleman $x, y$ için, $x$ input'ta $y$'den önceyse output'ta da $y$'den önce gelir.
Neden önemli? (1) RadixSort'un correctness'ı buna dayanır (sonraki bölümler). (2) Birden çok key'le sıralama: önce isme göre sırala, sonra aya göre stable sırala; her ayın içinde isimler alfabetik kalır.
| Algoritma | Stable mı? | Neden |
|---|---|---|
| InsertionSort | Evet | Sadece A[i] > key olanları kaydırır; eşit eleman key'in önünde kalır. |
| MergeSort | Evet | Eşitlik durumunda soldan alıyorsa (L[i] ≤ R[j]). |
| QuickSort (Hoare/Lomuto) | Genelde hayır | Partition'daki uzak swap'lar eşit elemanların sırasını bozabilir. |
| CountingSort (CLRS) | Evet | Son loop sağdan sola gider: her değerin son elemanı bloğun en sağına yazılır. |
| CS161 CountingSort (bucket'lar) | Evet | Bucket'lar FIFO: ilk giren ilk çıkar. |
- InsertionSort'ta koşulu
A[i] ≥ keyyaparsan eşitleri de kaydırırsın ve stability gider. MergeSort'ta eşitlikte sağdan alırsan aynı şey olur. - CountingSort'un son loop'unu soldan sağa çalıştırırsan eşitler ters sıraya girer: $[4_1,1,3_1,4_2,3_2]$ → $[1, 3_2, 3_1, 4_2, 4_1]$.
2023-24 vizesi S4(b)'deki SlowSort: rastgele bir $x$ seç, $S$'te $x$'ten küçük bir $y$ yoksa $x$ minimumdur; onu başa koy ve $S\setminus\{x\}$'i sırala. "Stable mı? $S$ bir set olarak tanımlanmışken stability anlamlı mı?"
İpucu 1
Stability tanımı hangi elemanlardan bahsediyor? Bir set'te böyle elemanlar olabilir mi?
İpucu 2
Şimdi duplicate değerlere izin ver. Minimum değerden iki kopya varsa test (y < x) ikisini de kabul eder mi? Hangisinin seçileceğini ne belirler?
Çözümü göster
Set olarak tanımlıysa eşit eleman yoktur, stability sorusu boşa düşer. Duplicate'lere izin verirsek: minimum değerin iki kopyası $m_1, m_2$ olsun. Test sadece "$y < x$ mi?" diye sorduğu için ikisi de minimum kabul edilir. Hangisinin önce yerleşeceğini input sırası değil, rastgele seçim belirler. $m_2$ önce seçilirse output'ta $m_1$'in önüne geçer. Yani SlowSort stable değil.
Hangi değişiklik CLRS CountingSort'u stable olmaktan çıkarır?
BucketSort fikri
CS161'in notebook'undaki bucketSort, slaytlardaki "CountingSort" ile aynı şey: integer key'ler, her değere bir FIFO bucket. CLRS 8.4'teki BucketSort ise başka bir algoritma, $[0, 1)$ aralığındaki real number'lar için. Sınavda hangisinin sorulduğuna bak.
$[0.42,\ 0.07,\ 0.91,\ 0.33,\ 0.38,\ 0.75,\ 0.04,\ 0.58]$. Bucket numarası $\lfloor n\cdot x\rfloor = \lfloor 8x\rfloor$:
bucket 0: $0.07,\ 0.04$ · bucket 2: $0.33$ · bucket 3: $0.42,\ 0.38$ · bucket 4: $0.58$ · bucket 6: $0.75$ · bucket 7: $0.91$
Her bucket'ı InsertionSort ile sırala ve birleştir: $0.04,\ 0.07,\ 0.33,\ 0.38,\ 0.42,\ 0.58,\ 0.75,\ 0.91$.
- $n$ bucket aç, $x$'i $\lfloor n x\rfloor$ numaralı bucket'a at: $O(n)$.
- Her bucket'ı InsertionSort ile sırala, sonra bucket'ları sırayla birleştir.
- Input $[0,1)$'de uniform dağılıyorsa bir bucket'a ortalama 1 eleman düşer ve expected running time $\Theta(n)$ olur.
- Worst case: hepsi aynı bucket'a düşerse InsertionSort $\Theta(n^2)$ sürer.
$n$ sayı $1..M$ aralığında, $M$ büyük ama constant. Aralarındaki fark en fazla $T$ olan iki eleman var mı? Soru $O(n^2)$, $O(n\log n)$ ve $O(n)$ çözüm istiyor.
İpucu 1
$O(n\log n)$: sıraladıktan sonra hangi çiftlere bakman yeter?
İpucu 2
$O(n)$: genişliği $T$ olan bucket'lar aç, $i$. bucket $[iT, (i+1)T)$ olsun. İki eleman aynı bucket'a düşerse ne söyleyebilirsin?
Çözümü göster
(1) Bütün çiftleri dene, $O(n^2)$. (2) Sırala, sadece yan yana duran çiftlere bak: yakın bir çift varsa sorted array'de yan yana duran bir çift de yakındır. (3) Genişliği $T$ olan $O(M/T)$ bucket aç; bu sayı constant, yerleştirme $O(n)$. Bir bucket'ta 2 eleman varsa farkları $< T$, cevap evet. Yoksa her bucket'ta en fazla 1 eleman var ve arada bir bucket bulunan iki elemanın farkı $T$'den büyük. Sadece komşu bucket'lardaki çiftlere bak, en fazla $n-1$ çift. Toplam $O(n)$.
BucketSort içeride InsertionSort ile comparison yapıyor. O halde neden $\Omega(n\log n)$ lower bound'una takılmıyor?
RadixSort: en sağdaki digit'ten başla
CountingSort'un sorunu büyük range. RadixSort'un çözümü: sayıyı digit'lerine ayır, her pass'te tek bir digit'e göre CountingSort yap. Bir digit 0 ile 9 arasında olduğu için her pass'te sadece 10 bucket var. En önemsiz digit'ten (least significant digit, LSD) başla.
Aşağıda CS161 slaytındaki array gerçekten sıralanıyor. Turuncu digit o pass'in key'i. Base 100'e geçince her "digit" iki decimal haneden oluşur.
Invariant: $t$. pass'ten sonra array, sayıların son $t$ digit'ine göre sorted.
- Base case ($t=0$): "Son 0 digit'e göre sorted" boş bir iddia, doğru.
- Inductive step: İddia $t-1$ için doğru olsun. $t$. pass'ten sonra herhangi iki sayıya bak: $x$'in son $t$ digit'i $y$'ninkinden küçük olsun. İki durum var:
- $x_t < y_t$: $x$ daha önceki bir bucket'a düşer, output'ta $y$'den önce gelir.
- $x_t = y_t$: O zaman son $t-1$ digit'te $x < y$. Inductive hypothesis'e göre $x$ bu pass'in input'unda $y$'den önceydi. İkisi aynı bucket'a düşüyor ve sıralama stable olduğu için $x$ yine önde kalır.
- Sonuç: $t = d$'de array bütün digit'lere göre, yani tamamen sorted. ∎
Proof'ta stability sadece ikinci durumda kullanıldı, ama orada vazgeçilmez: bir pass, digit'i eşit elemanların sırasını değiştirebilseydi önceki pass'lerin kurduğu düzen kaybolurdu. Somut bir örnek: 3. pass'te $1, 13, 21, 50$'nin hundreds digit'i hep 0. 2. pass onları doğru sıraya koymuştu. Stable olmayan bir sıralama bu dört sayıyı istediği sırada bırakabilir (örneğin $50, 1, 21, 13$) ve sonuç yanlış olur.
Hollerith'in kart makinesi en önemli digit'ten (most significant digit, MSD) başlıyordu: önce hundreds digit'ine göre 10 desteye ayır, sonra her desteyi ayrı ayrı recursive olarak sırala. 3 digit'te worst case'te 111 pass ve 99 ara deste gerekir. LSD ise tek desteyle sadece $d$ pass yapar; bedeli her pass'in stable olması.
Proof iki şarta dayanıyordu: pass'ler en önemsiz digit'ten başlar ve her pass stable'dır. Aşağıda ikisini de bozabilirsin. Non-stable seçeneğinde yeni eleman bucket'ın önüne eklenir, yani aynı digit'e sahip elemanlar bucket'tan ters sırayla çıkar. MSD-first aynı tek desteli yöntemi en soldaki digit'ten başlatır, Hollerith'in recursive destelerini kullanmadan.
Önce tahmin et: dört kombinasyondan (LSD ya da MSD-first, stable ya da non-stable) hangilerinde sonuç her input için sorted çıkar?
$[21, 345, 13, 101, 50, 234, 1]$'e base 10'da iki pass uygulandı. Array ne olur?
RadixSort'un running time'ı ve base seçimi
$n$ integer, en büyüğü $M$, base $r$:
- Digit sayısı $d = \lfloor \log_r M\rfloor + 1$.
- Her pass: $r$ bucket aç, $n$ sayıyı yerleştir: $O(n + r)$.
Büyük $r$ = daha az pass ama daha çok bucket. Örnekteki array'de base 10 ile 3 pass × 10 bucket, base 100 ile 2 pass × 100 bucket (yukarıdaki animasyonda dene).
Base 10 genelde kötü bir seçim: $\{1,\dots,n\}$'deki sayılar için $d = \lfloor\log_{10} n\rfloor + 1$ (örneğin $n = 1234$ → 4 digit), running time $O(n\log n)$. MergeSort'tan farkı yok.
$n$ ile $r$'yi dengele: $r = n$ ⇒ her pass $O(n)$ ve $$T = O\big(n\cdot(\lfloor\log_n M\rfloor + 1)\big).$$
- Kazandığı yer: $M \le n^c$ ve $c$ constant ⇒ en fazla $c+1$ pass ⇒ $O(n)$. CS161: "$n^{100}$'e kadar olan sayıları $O(n)$'de sıralar." 100 yerine herhangi bir constant olabilir.
- Kaybettiği yer: $M = 2^n$ ⇒ $\log_n 2^n = n/\log n$ pass ⇒ $O(n^2/\log n)$, MergeSort'tan kötü. Sayılar $n$'e göre çok büyükse RadixSort kullanma.
Bilgisayarda key'ler bit'lerden oluşur, bu yüzden base'i $r = 2^b$ seçmek doğal: her "digit" $b$ bit'lik bir parça olur. $w$ bit'lik key'lerde (en büyük key $2^w - 1$) $d = \lceil w/b\rceil$ pass var ve toplam iş $d\,(n + 2^b)$ mertebesinde. Aşağıda $n$ ve $w$ değerlerini değiştirip hangi $b$'nin kazandığına bak.
Önce tahmin et: 10⁶ sayı, her biri 32 bit. Toplam işi en aza indiren b hangisi: 1, 8, 16, 20 ya da 32?
| b | r = 2b | d = ⌈w/b⌉ | d·(n + r) | göreli maliyet (log ölçek) |
|---|
RadixSort iki elemanı hiç karşılaştırmaz; digit'i okur ve bucket index'i olarak kullanır. Yani comparison model'in dışında kalır ve $\Omega(n\log n)$ onu bağlamaz. Bedeli şu: sadece integer (ya da digit'lere ayrılabilen) key'lerde çalışır ve running time'ı $M$'ye bağlıdır.
- "RadixSort her zaman $O(n)$" yanlış. $d$, $M$'ye ve $r$'ye bağlı.
- Base'i büyütmek her zaman iyi değil: $r = n^2$ ile pass sayısı azalır ama her pass $O(n^2)$ olur.
- $\log_n M$'deki "+1"i atma: $M < n$ iken $\log_n M < 1$ ama yine bir pass gerekir.
$A$'da $n$ pozitif integer var, hepsi $[1, n^3)$ range'inde. (a) CountingSort'un running time'ı? (b) Base 10 RadixSort'un running time'ı? (c) Hangi base en hızlısı: 2, 10, $n$, $n^2$?
İpucu 1
(a) CountingSort'ta $k$ ne? (b) $n^3$'ün decimal digit sayısı $\log_{10} n$ cinsinden ne?
İpucu 2
(c) Her base için iki sayıyı ayrı hesapla: pass sayısı $d$ ve pass başına maliyet $n + r$. Sonra çarp.
Çözümü göster
(a) $k = n^3$ ⇒ $\Theta(n + n^3) = \Theta(n^3)$.
(b) $d \approx 3\log_{10} n$, pass başına $\Theta(n + 10)$ ⇒ $\Theta(n\log n)$.
(c) Base 2: $\approx 3\log_2 n$ pass, $\Theta(n\log n)$. Base $n$: 3 pass × $\Theta(n)$ = $\Theta(n)$. Base $n^2$: 2 pass × $\Theta(n + n^2)$ = $\Theta(n^2)$. En hızlısı base $n$.
$W = [$the, quick, brown, fox, jumps, over, the, lazy, dog$]$, kelimeler boşlukla aynı uzunluğa tamamlanıyor (boşluk 'a'dan önce gelir). RadixSort $O(d(n+r))$.
- 2.1: $d$, $n$, $r$ neyi ifade eder, değerleri ne?
- 2.2: Her karakter 8 bitlik ASCII'ye çevrilip bit string olarak sıralanırsa?
- 2.3: Önce ilk yayın tarihine, eşitlikte alfabeye göre sıralamak için "jumps" (19 Kasım 1562) nasıl yazılmalı?
- 2.4: $n > 2$ kelimelik $V$'deki kelimeler 0, 1, 10, 11, … diye binary sayılarla kodlanırsa running time ne olur?
- 2.5: Kelimeler uzunluğu $n$ olan one-hot vektörlerle kodlanırsa running time ne olur?
İpucu 1
$n$ = sıralanan eleman sayısı, $d$ = bir elemandaki "digit" (karakter ya da bit) sayısı, $r$ = bir digit'in alabileceği değer sayısı.
İpucu 2
2.3'te LSD sırası önemli: en önemli key (tarih) string'in başında olmalı ve her tarih aynı uzunlukta yazılmalı. 2.4'te $n-1$'in binary gösteriminde kaç bit var?
Çözümü göster
2.1: $n = 9$ kelime, $d = 5$ (en uzun kelimeler "quick", "brown", "jumps"), $r = 27$ (26 harf + boşluk).
2.2: $n = 9$, $d = 5 \cdot 8 = 40$ bit, $r = 2$.
2.3: 15621119jumps: önce YYYYMMDD, sonra kelime. Tarih en önde olduğu için son (en önemli) pass'ler onu sıralar; tarih eşitse kelime kısmının kurduğu sıra bozulmaz. "brainrot" (2024) bu yüzden sonra gelir.
2.4: $r = 2$, $d = \Theta(\log n)$ bit ⇒ $O(n\log n)$.
2.5: $r = 2$, $d = n$ ⇒ $O(n(n+2)) = O(n^2)$.
$n$ sayı var, hepsi $0 \le x < n^{2}$. En iyi seçim hangisi, running time ne?
n³−1’e kadar sayıları base n ile, n−1’e kadar sayıları base 2 ile ve n^(log₂n)−1’e kadar sayıları base n ile sırala. Süreler aynı mı?
İpucu
Çözümü göster
İlkinde 3 pass: Θ(n). İkincide ⌈log₂n⌉ pass: Θ(n log n). Üçüncüde yine ⌈log₂n⌉ pass: Θ(n log n). Stable CountingSort LSD RadixSort için gereklidir.
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
Bir algoritma 3 farklı elemanı her input'ta en fazla 2 comparison'la sıraladığını iddia ediyor. Doğru olabilir mi?
Concept check: $n$ comparable elemanı, her biri $\log n$ büyüklüğünde $n/\log n$ gruba $O(n)$'de bölmek (her $i < j$ için $i$. gruptakiler $\le$ $j$. gruptakiler) mümkün mü?
LSD RadixSort'un her pass'te stable bir sorting algorithm kullanması neden şart?
CS161'e göre $r = n$ base'li RadixSort hangi durumda MergeSort'tan kötüdür?