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

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Основно съдържание

Псевдокод на сортиране чрез пряка селекция

Има много различни начини да сортираме картите. Ето един прост начин, наречен сортиране чрез пряка селекция, подобен на начина, по който сортира картите по-горе:
  1. Намираме най-малката карта. Разменяме я с първата карта.
  2. Намираме следващата най-малка карта. Разменяме я с втората карта.
  3. Намираме третата най-малка карта. Разменяме я с третата карта.
  4. Повтаряме намирането на следващата най-малка карта и я разменяме с правилната позиция, докато масивът е сортиран.
Този алгоритъм се нарича сортиране с пряка селекция, защото последователно избира следващия най-малък елемент и го поставя на правилната позиция.
По-долу може самостоятелно да видиш алгоритъма. За начало използвай "Step", за да видиш всяка стъпка от алгоритъма, а след това опитай "Play" след като го разбереш, за да видиш всички стъпки по пътя.
След като го разгледа, какво мислиш за този алгоритъм? Кои части отнемат най-дълго време? Как смяташ, какво ще бъде изпълнението му за големи масиви? Задавай си тези въпроси, докато учиш и имплементираш този алгоритъм.

Намиране на индекса на минималния елемент на подмасива

Една от стъпките на сортирането чрез пряка селекция е намирането на следващата най-малка карта, която да бъде поставена на правилната позиция. Например, ако в началото масивът има стойностите [13, 19, 18, 4, 10], първо трябва да намерим индекса на най-малката стойност в масива. Тъй като 4 е най-малката стойност, индексът на най-малката стойност е 3.
Сортирането чрез пряка селекция ще размени стойността на индекс 3 със стойността на индекс 0, което ще даде [4, 19, 18, 13, 10]. Сега трябва да намерим индекса на втората най-малка стойност, която да поставим на индекс 1.
Кодът, който намира индекса на втората най-малка стойност в масив, може да бъде сложен. Сигурни сме, че можеш да го напишеш, но има и по-добър начин. Забележи, че, тъй като най-малката стойност вече е поставена на индекс 0, това, което трябва да намерим, е най-малката стойност в тази част на масива, която започва от индекс 1. Наричаме тази секция на масива подмасив, а в този случай искаме индекса на най-малката стойност в подмасива, който започва от индекс 1. За нашия пример, ако целият масив е [4, 19, 18, 13, 10], то най-малката стойност в подмасива, който започва от индекс 1, е 10, а в първоначалния масив има индекс 4. Затова индекс 4 е мястото на втория най-малък елемент от пълния масив.
Опитай тази стратегия в следващото предизвикателство и ще знаеш всичко необходимо, за да имплементираш целия алгоритъм за сортиране с пряка селекция.
Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.