Сортиране всички степени - фондации - Паскал - Статии Directory - свободно програмируеми

Подреждане на всички видове

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

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

За да се оцени ефективността на алгоритъма, ние ще използваме две стойности: броят на ключови сравнения (K), а броят на превозите на елементи (S). Последната стойност е от голям интерес за нас - изпращане на данни в паметта е по-времеемко от сравнението. Също така, в описанието ще се използват алгоритми такива количества: п - брой на масив елементи А [1..N] - сортирани масив, х - променливи от същия тип като елементи на масиви. Предполагаме, че имаме масив от цели числа (А: масив [l..n] на число х: цяло число).

Според броя на сравненията, необходими алгоритми за сортиране са разделени на два класа: прост разговори за н ^ 2 сравнения, и по-ефективни - от порядъка на п * дневник (н). Ще започна с опростен и интуитивен алгоритми. Методът на първо сортиране, което искам да ви кажа, се нарича "сортиране чрез пряка връзка." Идеята е, че ние приемаме реда на елементите на масив и сложи на своя "законен" място. От втория, ние повтаряме през всички елементи на масива и последователно сравнение с елементи, които имат индекс по-малко от това. Ако нашата позиция по-малко в сравнение с предишните, след това да ги подредите и да продължи да сравните по-нататък, ако повече, а след това го оставете - той е вече на място. И така, докато отиде, докато стигнем до лявата граница на масива. За в този случай процесът на сравняване не остава извън лявата граница на масива е необходимо да се създаде така наречената "бариера" - добавя в началото на клетката масив (например, [0]), което ще доведе сортирани в този подаване елемент. Ето и пълния код на алгоритъма:

Тук, [0] - над преградата, А [1..N] - сортирани масив.

Моят съвет за най-простите алгоритми за сортиране се опитам да напиша на хартия всяка последователност от числа, 4-5. И тогава "тече" го на лист хартия чрез алгоритъм за сортиране. В този случай, моля, напиши стойностите на всички променливи и промени в масива на всяка стъпка. Това не е толкова трудно да се направи, за първите три алгоритми и ще отнеме не повече от половината от тетрадка лист. По този начин много по-лесно да се разбере алгоритъма. Разбира се, от подобрени методи за това представлява значително предизвикателство, но в този случай има изход. Така например, в Delphi можете да изпълните стъпка на програмата по стъпка и да гледат стойностите на всички променливи на програмата - много полезно нещо, за да се разбере как някои от програмите. Не пренебрегвайте този съвет!

Среден брой ключ сравнение, и изпращане на елементите имат следните стойности: К = (п ^ 2 + п-2) / 4, S = (п ^ 2 + 9N-10) / 4 максималните и минималните стойности са: kmín = N-1, Смин = 3 х (п-1), кМАХ = (п ^ 2 + п-4) / 4, Smax = (п ^ 2 + 3n-4) / 2. В алгоритъма, има един съществен недостатък. Да предположим, че имаме масив от числа: 3,7,4,6,8,2. В този случай, последния елемент на масива (2), ще трябва да "влачите" в целия масив.

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

В този случай, не бариера (А [0]) не е необходимо, и считаме масива в интервала [1..N].

Сравнение ключ: К = (п ^ 2-п) / 2. За да изпратите клавиши, за да се изчисли средната стойност на лесно, защото цитирам минимум (ключове вече сортирани) и максимална (клавиши са разменени) стойности: Смин = 3 * (N-1), Smax = п ^ 2/4 + 3 * (NL) , Както можете да видите, прякото алгоритъм избор в повечето случаи ефективно пряка връзка. Единственото изключение е ситуация, в която на масива вече подредени или почти подредени. Въпреки това, в този случай, печалбата не е толкова голям, и като цяло, този метод е за предпочитане пред предишния.

И последният от вида първокласен на сортиране се нарича "сортиране пряка размяна". Основната разлика на този метод от горните две - обмен е характеристика на този алгоритъм. Идеята на алгоритъма последователно получи се сравняват над два съседни елементи и, ако е необходимо, променете места. Тази операция се повтаря, докато редът за цялата решетка.

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

Той използва променливата е като знаме. Ако е = вярно, тогава, в последния пасаж бяха направени пермутация и се нуждаят от повече преминавания, както и ако е = фалшив, тогава пермутация в последния прохода не е бил, и масива вече е сортиран. В този алгоритъм, има и недостатък: При най-малкото число се намира в края на масива, за да го придвижи към върха (в своята "законен" място) изискват N-1 проходи. В същото време, тъй като в началото на най-големия елемент на масива ще се премести в края на един пас. Съгласен съм по-скоро неприятен факт. Изводът е ясен: това е необходимо да се премине на масива от различни ъгли в даден момент, т.е. първи път от началото до края на втория - от края към началото, трета - отново от началото до края и т.н. Такъв подобрен алгоритъм, наречен "разклаща .... сортиране »(ShakerSort). Но програмата за този тип оферта, за да се напише. Ако сте напълно прави с метода на балон нещо, то няма да бъде за вас предизвикателство.

преброя сравнения ключове и пратки е трудно да се балон и се разклаща на видове. Ето защо, обективно сравнение на ефективността на последните две методи с предходната, ние можем в края на статията - аз ще предостави набор от различни часови алгоритми за сортиране.

Сега ние сме дошли близо до обсъждане на подобрени методи за сортиране. Разберете тях много по-трудно. През 1959 г., Д. Shell оферта подобрена сортиране на пряка връзка. Идеята е доста проста. Първо, ние сортиране на елементите раздалечени в региона 4. Например, да елемента А [1] и да я сравни с елемент [5] (A [4 + 1]), когато А [1] е по-голямо от А [5] след това да ги подредите. След това вземете А [2] и да сравнявате A [6] и така нататък. D. След този пропуск с "тримесечие" сортиране пас отново през масива, но сортирате елементи, разположени на разстояние в региона 2. И в последния проход е обичайно единичен сортиране. отдалечава последователност може да се промени, както и тяхното количество. Следователно, за да се обобщят всички разстояния т Включено в масив S [1..t]. Сортиране всеки разстояние е като сортиране пряк включване. Условия за сортиране края ще трябва да инсталирате бариера, а не един.

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

В основния рутинна бързасортировка подпрограма разговор сортиране на елементите от 1 до п. В подпрограма вид ние приемаме за х средата на този кръг и да споделят редица по-горе метод. След това тази подпрограма повикване отново, но половини и т. Г. Между другото, х и w трябва да бъде от същия тип като елементи на масиви.

В този случай средната стойност на S = (п-1 / п) / 6.

Сега е необходимо да се обобщят резултатите и заключенията (вж. Таблицата). За обективна оценка на ефикасността на сортиране алгоритми даде време на същия масив (елементите са разположени произволно) чрез различни методи. От таблицата се вижда, че нещо балон и неговата подобрена версия (PR шейк) е много по-лошо от всички останали. Интересно само подобрени методи. Въпреки метод Shell показва много добър резултат, най-доброто тепърва бързасортировка. Между другото, ако масива вече подредени, всички ефективни методи за показване на резултати, по-лошо, отколкото обикновено.