На алгоритми за подредбата на едномерни - Технически Форум

На алгоритми за подредбата на едномерни

Често в образователни задачи, които се търгуват на нашия форум хваща нареди масив, т.е. елементи източник масив подредени във възходящ или низходящ ред. Има много методи (алгоритми) за решаване на този проблем: преди 20-30 години, те изобретили усилено, опитвайки се да открие "оптимална", бърз и т.н. Днес, като се има предвид скоростта на съвременните компютри, такива дейности IMHO няма никакъв смисъл, и това изглежда разумно да се обучават студенти, които притежават най-малко един метод, най-добре е да се "балон", както е най-очевидната и проста, но не е - да преподават продължи да измъчва ukazulyami деца като "употреба метод вмъкване. " Е, нека се справят с основните.

Забелязвам, че този прост и елегантен начин за много начинаещи е трудно да се разбере и дори въпроси като "Защо двойна линия -! Мерен масив нещо" и т.н. Някои от тях, обаче, предпочитат да безсмислено от някъде perekatal програма фрагмент, като по този начин, са склонни да обърка двете променливи на усилване, което, разбира се, "не е добре". В същото време, ако погледнете, всеки може лесно да напиша това е подредбата на просто "от главата ми."
Да направим един пример за анализа. Език - Паскал (което, между другото, няма значение).
Да предположим, че е необходимо възходящ ред със следния масив:
03 апр 5 2 1
Броят на елементите (5) означават п.
Кодът:

Мисля, че по смисъла на тялото на цикъла е ясно: ако предишния елемент вече не следват, те са разменени. В този случай, имайте предвид, че външният контур променлива I като елемент от масив не се използва, това е - просто един брояч. Но наистина да бъде ясна, ние следваме последователността на програмата:

Така че, не забравяйте, първоначалното местоположение:

Първият преминаването на вътрешния контур (I = 1, к варира от един до 4 = 5-1):
3 4 5 1 2 (обменят позиции на елементите 1 и 2)
03 апр 5 2 1 (втори и трети са верни)
3 4 2 5 1 (обменят позиции 3 и 4 елементи)
3 4 2 1 5 (обменят позиции 4 и 5 позиции)

Лесно е да се разбере, че там, където има максимален елемент, след края на първия вътрешен цикъл, той ще бъде последният, който е там, където му е мястото. Повече, тази позиция няма да се докосна, защото на следващия вътрешният цикъл продължава от 1 до 5-2 = 3:
Април 3 2 1 5 (първо и второ щанд е вярна)
3 2 4 1 5 (обменят позиции 2 и 3 елементи)
3 2 1 4 5 (обменят позиции 3 и 4 елементи)

Това е вторият по големина елемент (4) на мястото си. На следващия цикъл от J - 1 до 5-3 = 2:
2 3 1 4 5 (обменят номера 1 и 2) елементи
2 1 3 4 5 (обменят позиции 2 и 3 елементи)

И накрая, последното преминаване на к - 1 до 1:
1 2 3 4 5 (обменят номера 1 и 2) елементи

Всичко! Както можете да видите, масивът е сортиран, проблемът е решен.
Защо е все още нарича "метод балон"? И си представете нашия масив под формата на тясна вертикална съд с течност, в която по-ниските индекси - това е "дъното" и старейшините - "отгоре". Тогава движението на елемента заедно масива от плаващ като въздушни мехурчета в съда. Обикновено визуална аналогия.
Разбира се, ако имате нужда да се организира елементите, които не са във възходящ ред и в низходящ ред, е необходимо само да се промени знака на неравенството в хода на изпълнението.

Това е значително по-ниско от "балон" в простота и яснота и, в допълнение, изисква използването на изкуствен прием - добавяне на допълнителен помощен елемент (възможно и без него, но след това програмата става тежка). В крайна сметка: нека първият от наш елементи, които вече са "подредени", т.е. На първо място е най-малкият елемент. След това се започва от втората нататък начин, както в "балон" верига по двойки Първообразът "преследвани" правилните, елементите - първа, втора, после трета и така нататък, докато п-ти. Но как да се изпълни условието, че на първо място е най-малкият елемент? Но за този "фронт" и се е вкопчил в масив веднъж "нула" в един ред елемент, със сигурност по-малко от другите. код:

сортиране избор на начин на

Всичко това е съвсем проста - намерете най-малкия елемент, промяна на места с първата, после се намери най-малката от друга страна, промяната на места с втория си и т.н. до предпоследната, която, ако е необходимо, за да промените места с последния. код:

Ето - внимание! МЕТОД Шели решава проблема Накрая той носи само предварителен "груб" сортиране, и накрая по делото, заведено от вмъкване или балон. Същност: първоначално разменени възходящи елементи, разположени в п / 2 позиция (т.е., ако п = 6, след това 1 до 4, 2 до 5 и 3 до 6), тогава "разстояние", разделена на две (закръглено, разбира се), а процедурата се повтаря, и така продължава толкова дълго, колкото "терена" става равна на 1. код:

Quicksort на метод (Hoare алгоритъм)

Смятан за един от най-бързите и най-ефективни. В същото време, много nenaglyaden и трудно за разбиране. Shell е нещо подобно на алгоритъма, но, за разлика от последните, носи, за да сортирате чрез. На следващо място, аз ще заеме основно материали от Уикипедия. както по отношение на спецификацията и в списъка с програми.
Стъпките са следните:

1. Изберете елемент в масива, който ще се нарича член на подкрепа. От гледна точка на коректността на избора на алгоритъм на опорния елемент на е безразличен.
2. Операция масив раздяла: реорганизиране на масива, така че всички елементи, чиято стойност е по-малка или равна на референтната държава, се превърнаха в ляво от него и всички елементи, надхвърлящи референтната стойност - прав. Нормално алгоритъм на работа:
   1. Две индекс - л и г. равна на минималната и максималната индекс на обща масив, съответно.
   2. Тя изчислява индекса на еталонния елемент м.
   3. Индексът л увеличава последователно нагоре, докато L-ти елемент ще бъдат не по-големи или равни на препратката.
   4. индекс R понижава до последователно, докато R-тия елемент е равна на или е по-малко от референтната.
   5. Ако R = л - Намерено средата масив - операция разделяне е завършена, двата индекса сочат към опорния елемент.
   6. Ако л
3. Рекурсивно поръчате под-масиви, лежи на ляво и дясно на опорния елемент.
4. База рекурсия са комплекти, състоящи се от един или два елемента. Произход връща в първоначалния си вид, на втория, ако е необходимо, за сортиране намалява до разменят местата на двата елемента. Всички тези сегменти вече са подредени в процеса на разделяне.

Тъй като всяка итерация (всяко следващо ниво на рекурсия) дължина на обработвания интервал масив намалява най-малко с един, клон терминал рекурсия се достига и обработването е необходимо да се гарантира пълно.

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

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

Попаднах тук тази сутрин за друг метод. Просто и глупаво. Тъй като аз не знам как се нарича, и то има ли някакъв начин на всички, нека го наречем "метод XXXX".
В крайна сметка: въведете булева променлива б кутия и да започне многократно преминаване на масива от началото до края, като замените съседни "дезорганизация" елементи, и така правя, докато такава "неподредени" двойки не остават, т.е. дадено преди следващото преминаване на стойността на идентификатора ще останат същите (ако тя отговаря на най-малко един "случаен" двойка, отметката е включена). код:

__________
Следват екранни снимки поръчка от същия масив от всички разгледани методи. За пореден път привлече вниманието към "непълнотите" на метода на Shell.

__________________
С Mozilla Firefox - направо на комунизма!