Sorting limits and review

Hazırlık: Somunlar ve cıvatalar

You have n bolts of different widths and the n matching nuts. You can test a nut against a bolt (too big, too small, or a fit), but you cannot compare two nuts or two bolts directly. Match them all.

Farklı genişliklerde n cıvatanız ve bunlarla eşleşen n somununuz var. Bir somunu bir cıvatada deneyebilirsiniz (çok büyük, çok küçük veya tam uyumlu), fakat iki somunu ya da iki cıvatayı doğrudan karşılaştıramazsınız. Hepsini eşleştirin.

O(n²): for each bolt, try every nut until one fits.

O(n²): Her cıvata için uygun somunu bulana kadar tüm somunları deneyin.

Smallest bolt and its nut in 2n − 2 tests: test the first bolt against every nut (n − 1 tests) while remembering the smallest nut that was still too small or the fit. Whichever nut comes out smallest belongs to the smallest bolt; find that bolt with n − 1 more tests.

En küçük cıvatayı ve somununu 2n − 2 denemede bulma: İlk cıvatayı her somunda deneyin (n − 1 deneme); hâlâ küçük kalan veya tam uyan somunların en küçüğünü aklınızda tutun. En küçük çıkan somun en küçük cıvataya aittir; o cıvatayı n − 1 ek denemeyle bulun.

Expected O(n log n): quicksort in disguise. Pick a random bolt as pivot and partition the nuts around it into “smaller”, “the match”, “larger”. The matching nut then partitions the bolts the same way. Recurse on both sides. It is exactly randomised quicksort, with nuts and bolts taking turns as pivots.

Beklenen O(n log n): Farklı bir görünüm altında hızlı sıralama. Rastgele bir cıvatayı pivot seçin ve somunları onun çevresinde “küçük”, “eşleşen”, “büyük” olarak bölümleyin. Ardından eşleşen somun, cıvataları aynı biçimde bölümler. İki tarafta da özyinelemeye devam edin. Bu, somunlarla cıvataların sırayla pivot olduğu rastgeleleştirilmiş hızlı sıralamanın aynısıdır.

n log n’den daha hızlı sıralayabilir miyiz?

All the sorts so far (heapsort, mergesort, quicksort, insertion sort) are comparison-based: their only way to learn about the input is to ask “is x before y?”. Think of any such program as a decision tree. Each internal node is a comparison, with two branches for the two answers; each leaf is a final output, a particular reordering of the input. Running the program on a given input traces one path from the root to a leaf. For three items the tree starts with “a₁ < a₂?”, then “a₂ < a₃?” or “a₁ < a₃?”, and so on, down to leaves labelled with the six possible orders.

Şimdiye kadarki bütün sıralamalar (öbek, birleştirmeli, hızlı ve eklemeli sıralama) karşılaştırmaya dayalıdır: girdi hakkında bilgi edinmelerinin tek yolu “x, y’den önce mi gelir?” sorusudur. Böyle bir programı karar ağacı olarak düşünün. Her iç düğüm bir karşılaştırmadır ve iki yanıt için iki dalı vardır; her yaprak, girdinin belirli bir yeniden sıralanışı olan son çıktıdır. Programın belirli bir girdide çalıştırılması, kökten bir yaprağa giden yolu izler. Üç eleman için ağaç “a₁ < a₂?” ile başlar; ardından “a₂ < a₃?” veya “a₁ < a₃?” gelir ve olası altı sıralamayla etiketlenmiş yapraklara kadar sürer.

The height of this tree (the longest root-to-leaf path) is the number of comparisons in the worst case.

Bu ağacın yüksekliği (kökten yaprağa en uzun yol), en kötü durumdaki karşılaştırma sayısıdır.

The counting argument. Different input orders must lead to different outputs, so the tree needs at least one leaf per possible order: at least n! leaves. A binary tree of height h has at most 2ʰ leaves. Therefore

Sayma argümanı. Farklı girdi sıraları farklı çıktılara yol açmalıdır; dolayısıyla ağacın her olası sıra için en az bir yaprağa, yani en az n! yaprağa ihtiyacı vardır. Yüksekliği h olan ikili bir ağaç en fazla 2ʰ yaprak içerir. Bu nedenle:

How big is lg(n!)? The last n/2 factors of n! are each bigger than n/2, so n! > (n/2)^(n/2) and

lg(n!) ne kadar büyüktür? n! içindeki son n/2 çarpanın her biri n/2’den büyüktür; dolayısıyla n! > (n/2)^(n/2) ve

Stirling’s approximation gives the sharper n! > (n/e)ⁿ, hence h ≥ n lg n − n lg e = Ω(n log n). Either way: any comparison-based sort needs Ω(n log n) comparisons in the worst case, so mergesort and heapsort are optimal up to constants. This is the course’s first lower bound, a statement about every possible algorithm rather than one particular algorithm.

Stirling yaklaşımı daha sıkı olan n! > (n/e)ⁿ eşitsizliğini verir; buradan h ≥ n lg n − n lg e = Ω(n log n) elde edilir. Her iki yolla da sonuç aynıdır: karşılaştırmaya dayalı her sıralama, en kötü durumda Ω(n log n) karşılaştırma gerektirir. Dolayısıyla birleştirmeli ve öbek sıralaması, sabit çarpanlar dışında optimaldir. Bu, dersin ilk alt sınırıdır: belirli bir algoritma hakkında değil, olası bütün algoritmalar hakkında bir önermedir.

Karşılaştırmasız sıralama: İskambil kartları

How would you sort a shuffled deck of cards? Not by comparing pairs. You would lay out 13 piles, one per rank, drop each card onto its pile, tidy the few cards in each pile by suit, and stack the piles up. If finding the right pile takes O(1) and each pile holds O(1) cards, the whole thing takes O(n). The trick is that dropping a card onto “the 7 pile” uses the value of the card directly, which is more information than a yes/no comparison gives.

Karıştırılmış bir iskambil destesini nasıl sıralarsınız? Çiftleri karşılaştırarak değil. Her kart değeri için bir tane olmak üzere 13 yığın oluşturur, her kartı kendi yığınına koyar, her yığındaki birkaç kartı türlerine göre düzenler ve yığınları üst üste toplarsınız. Doğru yığını bulmak O(1) sürüyor ve her yığın O(1) kart tutuyorsa işlemin tamamı O(n) sürer. Buradaki püf noktası, bir kartı “7’ler yığınına” bırakmanın kartın değerini doğrudan kullanmasıdır; bu, evet/hayır karşılaştırmasının sağladığından daha fazla bilgi verir.

Kova sıralaması (bucketsort)

Suppose we sort n numbers drawn from 1 to m, and we know they are spread roughly evenly over that range. Set up n buckets, bucket i covering the interval of numbers from (i − 1)m/n + 1 to i·m/n. A number x goes into bucket ⌈xn/m⌉, which is a single arithmetic operation, O(1). Then sort each bucket (with anything, even insertion sort) and concatenate the buckets in order.

1 ile m arasında seçilmiş n sayıyı sıraladığımızı ve bu aralığa yaklaşık eşit dağıldıklarını bildiğimizi varsayın. n kova oluşturun; i. kova, (i − 1)m/n + 1 ile i·m/n arasındaki sayıları kapsasın. x sayısı ⌈xn/m⌉ kovasına gider; bu tek bir aritmetik işlem, yani O(1)’dir. Ardından her kovayı (herhangi bir yöntemle, eklemeli sıralamayla bile) sıralayın ve kovaları sırayla art arda ekleyin.

With evenly spread keys the expected number of items per bucket is 1, so sorting each bucket is O(1), and the total for bucketing, sorting and concatenating is O(n).

Anahtarlar eşit dağıldığında kova başına beklenen eleman sayısı 1’dir; dolayısıyla her kovayı sıralamak O(1), kovalara dağıtma, sıralama ve birleştirme işlemlerinin toplamı O(n)’dir.

What happened to the Ω(n log n) lower bound? Nothing: bucketsort is not comparison-based, so the bound does not apply to it. But it bought linear time with an assumption about the data.

Ω(n log n) alt sınırına ne oldu? Hiçbir şey: kova sıralaması karşılaştırmaya dayalı değildir; dolayısıyla sınır ona uygulanmaz. Ancak doğrusal zamanı, veri hakkında bir varsayım karşılığında elde etmiştir.

Varsayım yanlış olduğunda

If the data is not evenly spread, all the items may land in one or two buckets. We spend linear time distributing them and learn nothing; sorting the one big bucket is the whole original problem again. This is precisely why the course insists on worst-case analysis: the “expected” case is only as good as the assumption behind it.

Veri eşit dağılmıyorsa bütün elemanlar bir veya iki kovaya düşebilir. Elemanları dağıtmak için doğrusal zaman harcar ve hiçbir şey öğrenemeyiz; tek büyük kovayı sıralamak, başlangıçtaki problemin aynısıdır. Dersin en kötü durum analizinde ısrar etmesinin nedeni tam olarak budur: “beklenen” durum, ancak arkasındaki varsayım kadar iyidir.

Skiena’s example is a phone book. Are there many Skienas? No. Many Smiths? Yes. Many Shiffletts? In Charlottesville, Virginia, the Shifflett family fills pages of the directory (the slide shows the columns), while the 1,000-page Manhattan directory has seven. Real-world distributions are lumpy in ways you cannot predict from the name alone. Either understand your data’s distribution, or use an algorithm with a good worst-case or randomised guarantee.

Skiena’nın örneği bir telefon rehberidir. Çok sayıda Skiena var mı? Hayır. Çok sayıda Smith? Evet. Peki Shifflett? Virginia’nın Charlottesville kentinde Shifflett ailesi rehberin sayfalarını doldurur (slayt bu sütunları gösterir), oysa 1,000 sayfalık Manhattan rehberinde yedi tane vardır. Gerçek dünyadaki dağılımlar, yalnızca isme bakılarak öngörülemeyecek biçimde kümelenir. Ya verinizin dağılımını anlayın ya da en kötü durum veya rastgeleleştirilmiş performans garantisi iyi olan bir algoritma kullanın.

Basamak sıralaması ve alt sınırın neden geçerliliğini koruduğu

Radix sort sorts strings (or numbers viewed as digit strings) by bucketing on the last character, then re-bucketing on the second-to-last while preserving the order from the previous pass, and so on to the first character. Ties are broken by the earlier passes. Sorting n strings of length m takes O(nm), which is linear in the total size of the input.

Basamak sıralaması, dizeleri (veya rakam dizeleri olarak görülen sayıları) son karakterlerine göre kovalara dağıtır; ardından önceki geçişin sırasını koruyarak sondan ikinci karaktere göre yeniden dağıtır ve ilk karaktere kadar sürdürür. Eşitlikler önceki geçişlerle çözülür. Uzunluğu m olan n dizeyi sıralamak O(nm) sürer; bu, girdinin toplam boyutunda doğrusaldır.

Does this beat the bound? No. For n keys to be distinct they need at least lg n characters each (otherwise there are not enough different strings), so m must be Ω(log n), and O(nm) is O(n log n) again. Sorting n arbitrary distinct keys cannot be done faster than Θ(n log n); linear-time sorts win only by exploiting structure that arbitrary keys do not have.

Bu, sınırın altına iner mi? Hayır. n anahtarın farklı olabilmesi için her birinin en az lg n karaktere ihtiyacı vardır (aksi hâlde yeterince farklı dize yoktur). Dolayısıyla m, Ω(log n) olmalıdır ve O(nm) yeniden O(n log n) olur. Keyfî n farklı anahtarı Θ(n log n)’den daha hızlı sıralamak mümkün değildir; doğrusal zamanlı sıralamalar ancak keyfî anahtarlarda bulunmayan bir yapıdan yararlanarak üstünlük sağlar.