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

Аудармашы: Ainura Jaulbayeva Редактор: Bakytgul Salykhova

You work at the college library.

Колледж кітапханасында жұмыс істеп отырсыз

You're in the middle of a quiet afternoon

Жайма шуақ бір күні

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

әр түрлі тақырыптағы 1,280 кітап келеді.

Кітаптар тізіліп тұр, бірақ шашыраңқы,

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

but they're all out of order,

олар ретімен тұрған жоқ,

and the automatic sorting system is broken.

автоматты сұрыптау жүйесі жұмыс істемейді.

To make matters worse, classes start tomorrow,

Ертең сабақ басталатыны да жағдайды қиындатып тұр,

which means that first thing in the morning,

бұл таңертең ең алдымен студенттер

кітап іздеуге топырлап келеді деген сөз.

students will show up in droves looking for these books.

How can you get them all sorted in time?

Бәрін уақытында орнына қойып үлгересіз бе?

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

Сұрыптауды кез келген қатардан бастау - ең тиімді әдістердің бірі.

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

Егер кітаптар өз орнында тұрса, онда сол жерде қалдырыңыз.

Otherwise, swap them.

Басқа жағдайда орнын ауыстыру қажет.

Then, look at the second and third books,

Келесі екінші және үшінші кітапқа қараңыз,

repeat the process,

сол әрекетті қайталаңыз,

and continue until you reach the end of the line.

соңына жеткенше жалғастыра беріңіз.

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

Бір кезде сіз соңында тұратын кітапты табасыз,

and keep swapping it with every subsequent book,

яғни әр кітаптың орнын ауыстыруды жалғастыра беріңіз,

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

соңғы нүктеге жеткенше ретімен жылжып отырыңыз.

Then, start from the beginning and repeat the process

Содан кейін басынан бастап, соңғы кітапты

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

тиісті орнына қою үшін әрекетті қайталаңыз,

and keep going until all books are sorted.

бәрі сұрыпталмайынша үдерісті жалғастыра беріңіз.

This approach is called Bubble Sort.

Бұл тәсілдің атауы - Bubble Sort.

It's simple but slow.

Бұл оңай, бірақ көп уақыт алады.

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

Бірінші кезеңде 1,279 кітапты салыстырасыз,

then 1,278, and so on,

содан кейін 1,278, т.с.с.,

adding up to 818,560 comparisons.

соңында 818,560 салыстыруға тең болады.

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

Егер әр әрекет бір секунд уақыт алса, жұмыс тоғыз күнге созылады.

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

Екінші стратегия: тек алғашқы екі кітапты сұрыптаудан басталады.

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

Сосын үшінші кітапты алып, келесі екінші кітаптың орнына қойыңыз.

If it belongs before the second book, swap them,

Егер оның екінші кітапқа қатысы болса, кітаптың орнын ауыстырыңыз,

then compare it with the book in the first spot,

кейін, оны бірінші тұрған кітаппен салыстырыңыз,

and swap again if needed.

қажет болса, орнын ауыстырыңыз.

Now you've sorted the first three books.

Сіз алғашқы үш кітапты сұрыптадыңыз.

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

Егер екінші кітаптан бұрын тұрса, кітаптың орнын ауыстырыңыз,

comparing and swapping the new book with the one before it

жаңа кітапты алдыңғысымен салыстырып, ауыстыру керек,

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

кітаптар дұрыс орналаспайынша сұрыптауды жалғастырыңыз.

Бұл әдіс Insertion Sort деп аталады.

This is called Insertion Sort.

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

Bubble Sort әдісінен айырмашылығы әр жұп кітапты салыстырудың қажеті жоқ.

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

Орта есеппен алғанда әр кітапты оған дейін шыққан кітаптардың

to half of the books that came before it.

жартысымен салыстыру керек.

In that case, the total number of comparisons

Жалпы салыстыру саны

would be 409,280,

409,280

taking almost five days.

бұл жұмысқа бес күн керек.

You're still doing way too many comparisons.

Сіз әлі де көп салыстыру жасайсыз.

Here's a better idea.

Бұл - табылған ақыл.

First, pick a random book.

Алдымен, кездейсоқ кітапты алыңыз.

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

Бұны бір бөлім деп атап, оны әрбір екінші кітаппен салыстырыңыз.

Then, divide the line

Содан кейін қатарды екіге бөліп,

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

сол жақ бөлімнің алдында тұрған кітаптардың бәрін алып

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

оң жаққа қойыңыз.

You've just saved loads of time

Сіз біраз уақытты үнемдедіңіз

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

сол жақтағы кітаптардың ешқайсысын

to any of the ones on the right ever again.

оң жақтағы кітаптармен салыстырудың қажеті жоқ.

Now, looking only at the books on the left,

Енді тек сол жақтағы кітаптарға қараңыз,

you can again pick a random partition book

сіз тағы да кез келген кітапты ала аласыз

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

осыдан кейін кітаптарды қайта бөліңіз.

You can keep creating sub-partitions like this

Сіз осындай бөлімдерді құрастыра аласыз

until you have a bunch of small sub-lines,

яғни, сізде шағын қатар болғанша,

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

сұрыптаудың басқа стратегиясын пайдаланып, жылдам сұрыптайтын едіңіз.

Each round of partitioning requires about 1,280 comparisons.

Сұрыптаудың әр кезегі шамамен 1,280 салыстыруды қажет етеді.

If your partitions are pretty balanced,

Бөлімдер жеткілікті деңгейде теңестірілсе,

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

кітаптарды он қатардан 128-ге бөлу керек, бұл шамамен жеті раунд болады,

or 8,960 seconds.

немесе 8,960 секунд.

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

Бұл қатарды сұрыптауға әрқайсысына шамамен 22 секунд кетеді деген сөз.

All in all, this method known as QuickSort

Жалпы алғанда бұл әдіс QuickSort атымен танымал,

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

шамамен кітаптарды үш жарым сағатта сұрыптай аласыз.

But there's a catch.

Бірақ бір нәрсе бар.

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

Бөлінген кітаптар бір жақты болуы мүмкін, бұл уақытты мүлдем үнемдемейді.

Luckily, this rarely happens.

Мұндай жағдай сирек кездеседі.

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

Сондықтан QuickSort сұрыптаудың ең жақсы әдісі болғандықтан,

used by programmers today.

программистер қазіргі таңда қолданып жүр.

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

Интернет-дүкендегі

тауарлардың бағасын

сұрыптау үшін

пайдаланады.

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

Осы жерле жақын жанармай бекеттерінің тізімін құрау үшін де пайдалы

sorted by distance.

Сіздің мысалыңызда уақыт үнемдеп, сұрыптауды жылдам аяқтадыңыз

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

Just another high-stakes day in the library.

Кітапханадағы тағы бір қарбалас күн аяқталды.