Алгоритъм

Сравняване на алгоритми

Обикновено има повече от един начин за решаване на даден проблем. Може да има много различни рецепти за приготвяне на определено ястие, което изглежда различно, но в крайна сметка има един и същ вкус, когато всичко е казано и направено. Същото важи и за алгоритмите. Въпреки това някои от тези начини ще бъдат по-добри от други. Ако една рецепта се нуждае от много сложни съставки, с които не разполагате, тя не е толкова добра, колкото простата рецепта. Когато разглеждаме алгоритмите като начин за решаване на проблеми, често искаме да знаем колко време би отнело на компютъра да реши проблема, използвайки определен алгоритъм. Когато пишем алгоритми, искаме нашият алгоритъм да отнема най-малко време, за да можем да решим проблема си възможно най-бързо.

При готвенето някои рецепти са по-трудни за изпълнение от други, защото отнемат повече време или трябва да се следят повече неща. Същото важи и за алгоритмите, а алгоритмите са по-добри, когато са по-лесни за изпълнение от компютъра. Нещото, което измерва трудността на даден алгоритъм, се нарича сложност. Когато питаме колко сложен е даден алгоритъм, често искаме да знаем колко време ще отнеме на компютъра да реши задачата, която искаме да реши.

Сортиране

Това е пример за алгоритъм за сортиране на карти с цветове в купчинки от един и същи цвят:

1. Вземете всички карти.
2. Вземете карта от ръката си и погледнете цвета на картата.
3. Ако вече има купчина карти от този цвят, сложете тази карта на тази купчина.
4. Ако няма купчинка с карти от този цвят, направете нова купчинка само с този цвят карти.
5. Ако в ръката ви все още има карта, върнете се към втората стъпка.
6. Ако в ръката ви все още няма карта, картите се подреждат. Приключили сте.

Сортиране по числа

Това са примери за алгоритми за сортиране на купчина карти с много различни числа, така че числата да са подредени.

Играчите започват с купчина карти, които не са били сортирани.

Първи алгоритъм

Този алгоритъм преминава през купчината карти, една по една. Тази карта се сравнява със следващата карта в купчината. Моля, обърнете внимание, че тази позиция се променя само в стъпка 6. Този алгоритъм се нарича сорт на балончетата. Той е бавен.

1. Ако купчината от карти е празна или съдържа само една карта, тя е сортирана и сте готови.
2. Вземете купчината карти. Погледнете първата карта (най-горната) от купчината.
3. Картата, която гледате, е карта А. Позицията, на която се намира карта А в момента, е в купчина P.
4. Ако в купчината няма повече карти след карта А, преминете към стъпка 8.
5. Следващата карта в купчината е карта В.
6. Ако карта В има по-малко число от карта А, разменете позициите на карти А и В. Запомнете, че направихте това. Когато разменяте картите, не променяйте позицията P.
7. Ако има друга карта в купчината след позиция P, погледнете я; върнете се към стъпка 3.
8. Ако не сте разменили позицията на нито една от картите при последното пускане, сте готови; купчината карти е подредена.
9. В противен случай се върнете към стъпка 2.

Пример "стъпка по стъпка

Нека вземем купчина карти с числата "5 1 4 2 8" и я подредим от най-малкото до най-голямото число, като използваме този алгоритъм. На всяка стъпка алгоритъмът сравнява елементите, изписани с удебелен шрифт. Върхът на купчината карти е от лявата страна.

Първо преминаване:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 2 8 ) Тук алгоритъмът сравнява първите два елемента и ги разменя.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Тези елементи вече са подредени, така че алгоритъмът не ги разменя.
Второ преминаване:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Сега купчината карти вече е сортирана, но нашият алгоритъм не знае това. Алгоритъмът се нуждае от едно цяло преминаване без никаква размяна, за да разбере, че е сортиран.
Трето преминаване:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Накрая масивът е сортиран и алгоритъмът може да спре.

История

Това е лесен за разбиране алгоритъм за сортиране. Компютърните учени го наричат Bubble sort, защото по-малките елементи се издигат нагоре, като променят позицията си при всяко изпълнение. За съжаление алгоритъмът не е много добър, защото за сортирането му е необходимо много време (много преминавания през купчината карти).

Втори алгоритъм

Този алгоритъм използва друга идея. Понякога решаването на даден проблем е трудно, но проблемът може да бъде променен така, че да се състои от по-прости проблеми, които са по-лесни за решаване. Това се нарича рекурсия. Той е по-труден за разбиране от първия пример, но ще даде по-добър алгоритъм.

Основна идея

1. Ако в купчината няма карти или има само една карта, тя е сортирана и вие сте готови.
2. Разделете купчината карти на две половини с приблизително еднакъв размер. Ако броят на картите е нечетен, в едната от двете купчинки ще има една карта повече от другата.
3. Сортирайте всяка от двете купчини, като използвате този алгоритъм (За всяка купчина започнете от елемент 1 на този списък.)
4. Обединете двата сортирани стека, както е описано по-долу.
5. Резултатът е подредена купчина карти. Готови сте.

Обединяване на два стека

Това работи с две купчини карти. Едната от тях се нарича А, а другата - В. Има и трета купчина, която е празна в началото, наречена В. В края тя ще съдържа резултата.

1. Ако купчинка А или купчинка В е празна, поставете всички карти от купчинката, която не е празна, върху купчинка С; готово, купчинка С е резултатът от сливането. (Забележка: вземете цялата купчина и я поставете върху купчина C; ако го направите карта по карта, ще промените реда и няма да работите както трябва.)
2. Погледнете най-горните карти от купчинка А и купчинка Б. Поставете тази с по-малък номер върху купчинка В. Ако в купчинка В не е имало карти, сега в нея ще има една карта.
3. Ако в купчинка А или купчинка В има останали карти, върнете се към стъпка 1, за да ги сортирате.

История

Джон фон Нойман разработва този алгоритъм през 1945 г. Той не го нарича Сортиране по числа, а Mergesort. Това е много добър алгоритъм за сортиране в сравнение с други.

Трети алгоритъм

Първият алгоритъм отнема много повече време за сортиране на картите, отколкото вторият, но може да бъде подобрен (усъвършенстван). При разглеждане на метода за сортиране на балончета може да се забележи, че картите с големи числа се придвижват от върха на купчината доста бързо, но картите с малки числа в долната част на купчината се издигат (придвижват се към върха) дълго време. Идеята за подобряване на първия алгоритъм е следната:

Вместо да се сравняват две карти, които са една до друга, в началото се избира "специална" карта. След това всички останали карти се сравняват с тази карта.

1. Започваме с един стек A. Ще има още два стека B и C, които ще бъдат създадени по-късно.
2. Ако в купчина А няма карти или има само една карта, сортирането е приключило.
3. Избира се карта от купчина А, по възможност на случаен принцип. Това се нарича пивот.
4. Всички останали карти от купчина А се сравняват с тази ос. Картите с по-малък брой отиват в купчина Б, а тези със същия или по-голям брой отиват в купчина В.
5. Ако има карти в купчини B или C, тези купчини трябва да бъдат сортирани със същия алгоритъм (Започнете от позиция 1 на този списък за купчини B и C.)
6. Изпълнено. В подредената купчина карти първо се намира подредената купчина В, след това оста и след това подредената купчина С.

История

Този алгоритъм е разработен от К. А. Р. Хоар през 1960 г. Той е един от най-широко използваните алгоритми за сортиране днес. Той се нарича Quicksort.

Анимация, която показва как работи сортирането на мехурчета


Сортиране на 7 числа чрез втория алгоритъм за сортиране по числа (Mergesort)


Третият алгоритъм за сортиране на карти. Елементът с червената лента се избира за ос. В началото това е елементът, който се намира най-вдясно. Този алгоритъм се нарича Quicksort.

Сглобяване на алгоритми

Ако играчите разполагат с карти с цветове и числа, те могат да ги сортират по цвят и число, ако изпълнят алгоритъма "сортиране по цветове", след това изпълнят алгоритъма "сортиране по числа" за всяка цветна купчинка и след това съберат купчинките.

Алгоритмите за сортиране по числа са по-трудни за изпълнение от алгоритъма за сортиране по цветове, тъй като може да се наложи стъпките да се повтарят многократно. Може да се каже, че сортирането по числа е по-сложно.

Свързани страници

• Алгоритъмът на Евклид е открит преди повече от 2000 години. С него може да се намери най-големият общ делител на две числа.