What's the fastest way to alphabetize your bookshelf? - Chand John

Kitaplığınızı alfabetik sıralamanın en hızlı yolu nedir? - Chand John

Çeviri: Ahmet Mesut ATEŞ Gözden geçirme: Selda Yener

You work at the college library.

Üniversite kütüphanesinde çalışıyorsunuz.

You're in the middle of a quiet afternoon

Sakin bir öğle sonrasının ortasındasınız

when suddenly a shipment of 1,280 different books arrives.

derken 1280 adet farklı kitap sevkiyatı geliyor.

The books have been dropped of in one long straight line,

Kitaplar, uzun düz bir sıra hâlinde indiriliyor

but they're all out of order,

ancak sıraları bozuk hâlde,

and the automatic sorting system is broken.

üstelik otomatik sıralama sistemi de arızalı.

To make matters worse, classes start tomorrow,

Bu da yetmezmiş gibi dersler yarın başlıyor,

which means that first thing in the morning,

yani sabah erkenden

students will show up in droves looking for these books.

öğrenciler bu kitaplar için sıraya girmeye başlayacak.

How can you get them all sorted in time?

Hepsini vaktinde nasıl sıralayabilirsiniz?

One way would be to start at one end of the line with the first pair of books.

İlk yol sıranın bir ucundan ilk iki kitapla başlamak olur.

If the first two books are in order, then leave them as they are.

Eğer ilk iki kitap sıralı ise oldukları gibi bırakın.

Otherwise, swap them.

Değilse değiştirin.

Then, look at the second and third books,

Sonra ikinci ve üçüncü kitaplara bakın,

repeat the process,

işlemi tekrar edin

and continue until you reach the end of the line.

ve sıranın sonuna gelene kadar devam edin.

At some point, you'll come across the book that should be last,

Bir noktada, en sonda olması gereken kitaba denk gelirsiniz

and keep swapping it with every subsequent book,

ve onu, sonrasında gelen her kitapla değiştirip

moving it down the line until it reaches the end where it belongs.

kitap doğru yere gelene kadar aşağıya kaydırarak devam edin.

Then, start from the beginning and repeat the process

Sonra en başa dönün ve işlemi

to get the second to last book in its proper place,

sondan ikinci kitap yerini bulana kadar tekrarlayın

and keep going until all books are sorted.

ve bütün kitaplar sıralanana kadar devam edin.

This approach is called Bubble Sort.

Bu yönteme "kabarcık sıralama" denir.

It's simple but slow.

Basit ama yavaştır.

You'd make 1,279 comparisons in the first round,

İlk seferde 1279 karşılaştırma yapmış olursunuz,

then 1,278, and so on,

sonra 1278 olur ve toplamda

adding up to 818,560 comparisons.

818.560 karşılaştırmaya ulaşır.

If each took just one second, the process would take over nine days.

Her karşılaştırma bir saniye alsa işlem dokuz günden fazla sürer.

A second strategy would be to start by sorting just the first two books.

İkinci bir yol sadece ilk iki kitabı sıralayarak başlamak olur.

Then, take the third book and compare it with the book in the second spot.

Sonra üçüncü kitabı alıp ikinci sıradaki kitapla karşılaştırın.

If it belongs before the second book, swap them,

İkinci kitaptan önce ise yerlerini değiştirin,

then compare it with the book in the first spot,

sonra onu ilk sıradaki kitapla karşılaştırın,

and swap again if needed.

gerekirse yerini değiştirin.

Now you've sorted the first three books.

Şimdilik ilk üç kitabı sıraladınız.

Keep adding one book at a time to the sorted sub-line,

Her seferinde, sıralanan tarafa yeni bir kitap eklemeye devam edin,

comparing and swapping the new book with the one before it

yeni kitabı bir önceki kitapla karşılaştırıp değiştirerek

until it's correctly placed among the books sorted so far.

o zamana kadar sıralananların arasına doğru şekilde yerleşene kadar.

This is called Insertion Sort.

Buna "eklemeli sıralama" denir.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Kabarcık sıralamanın aksine, her çifti karşılaştırmayı gerektirmez.

On average, we'd expect to only need to compare each book

Ortalama olarak her kitabı, sadece kendinden önce gelen kitapların

to half of the books that came before it.

yarısıyla karşılaştırmamız gerekir.

In that case, the total number of comparisons

Bu durumda toplam karşılaştırma sayısı

would be 409,280,

409.280 olup

taking almost five days.

yaklaşık beş gün sürer.

You're still doing way too many comparisons.

Hâlâ çok fazla karşılaştırma yapıyorsunuz.

Here's a better idea.

İşte size daha iyi bir fikir:

First, pick a random book.

Önce rastgele bir kitap seçin.

Call it the partition and compare it to every other book.

Buna "parça" deyin ve diğer bütün kitaplarla karşılaştırın.

Then, divide the line

Sonra sırayı ikiye bölün,

by placing all the books that come before the partition on its left

parçadan önce gelen bütün kitapları sol tarafa,

and all the ones that come after it on its right.

parçanın ardından gelen bütün kitapları da sağ tarafa koyun.

You've just saved loads of time

Soldaki bütün kitapları

by not having to compare any of the books on the left

sağdaki kitaplarla tekrar tekrar karşılaştırmak zorunda kalmayıp

to any of the ones on the right ever again.

hayli zaman kazandınız.

Now, looking only at the books on the left,

Şimdi de sadece soldaki kitaplara bakın,

you can again pick a random partition book

yine rastgele bir parça kitap seçebilir

and separate those books that come before it from those that come after it.

ve öncesinde kalan kitapları sonra gelenlerden ayırabilirsiniz.

You can keep creating sub-partitions like this

Bu şekilde alt parçalar oluşturmaya

until you have a bunch of small sub-lines,

küçük bir alt grup elde edene kadar devam edip

each of which you'd sort quickly using another strategy, like Insertion Sort.

bunları "yerleştirmeli sıralama" gibi bir yöntemle hızlıca sıralayabilirsiniz.

Each round of partitioning requires about 1,280 comparisons.

Her parçalama işlemi yaklaşık 1280 karşılaştırma gerektirir.

If your partitions are pretty balanced,

Eğer parçalar eşit dağılmışsa

dividing the books into 128 sub-lines of ten would take about seven rounds,

kitapları on kitaplık 128 alt gruba bölmek yedi sefer

or 8,960 seconds.

ya da 8960 saniye gerektirir.

Sorting these sub-lines would add about 22 seconds each.

Alt grupları tasnif etmek her birine yaklaşık 22 saniye ekler.

All in all, this method known as QuickSort

Neticede, "hızlı sıralama" olarak bilinen bu yöntem

could sort the books in under three and a half hours.

kitapları üç buçuk saatin altında sıralayabilir.

But there's a catch.

Ancak tek sorunu var.

Your partitions could end up lopsided, saving no time at all.

Parçalar orantısız olursa hiç zaman kazanamazsınız.

Luckily, this rarely happens.

Neyse ki bu nadiren olur.

That's why QuickSort is one of the most efficient strategies

Bundan dolayı hızlı sıralama günümüzde programcıların kullandığı

used by programmers today.

en etki yöntemlerdendir.

They use it for things like sorting items in an online store by price,

İnternet mağazalarında ürünleri fiyata göre sıralama

or creating a list of all the gas stations close to a given location

veya belirli bir konuma yakın olan benzin istasyonlarının

sorted by distance.

uzaklık sıralamasında kullanırlar.

In your case, you're done quick sorting with time to spare.

Sizin durumunuzda hızlı sıralamayla geriye zamanınız bile kalır.

Just another high-stakes day in the library.

Kütüphanede yüksek riskli günlerden birisi daha.