Цифрово сортиране
Задача за сортиране.
Статистика за сортиране и подреждане.
Сортирането е практически важен и теоретично интересен проблем, свързан с разпределението на някои данни от дадена популация в определен ред.
Сортирането се превърна във важен предмет в изчислителната математика, защото отнема значителна част от времето на компютъра. 25% от общото изчислително време се изразходва за сортиране на данни, така че изграждането на ефективни алгоритми за сортиране е важна (необходима) задача.
За съжаление, няма алгоритъм за сортиране, който да е най-добър във всеки случай. Ефективността на алгоритъма за сортиране зависи от много фактори, например:
- върху броя на сортираните елементи;
- дали всички елементи могат да бъдат поставени в наличната оперативна памет;
- до каква степен елементите вече са сортирани;
- какви са диапазонът и разпределението на стойностите на сортираните елементи;
- начин на въвеждане на информация и данни;
- каква е дължината, сложността и изискванията към паметта на алгоритъма за сортиране;
- дали се очаква елементи да бъдат добавяни или премахвани периодично;
- дали елементите могат да се сравняват паралелно.
Сортирането се използва при превод на програми, когато се съставят таблици със символи, а също така е важен инструмент за ускоряване на работата на почти всеки алгоритъм, в който често трябва да се осъществява достъп до определени елементи.
Задачата за сортиране е подреждането на елементи от данни от определена популация в определен ред.
Обикновено елементите, които се сортират, са някакви записи на данни. Всеки запис има ключово поле и информационно поле. Сортирането не включва целите елементи от данни, а само част от тях, т.нарключ за сортиране.
След товасортирането е операция, която подрежда набор от елементи по ключове, на които е дефинирана връзката на реда.
Частичен ред върху множество S е двуместна релация R такава, че за всяко a, b, c О S
1. рефлексивност - aRa;
2. транзитивност - ако aRb и bRc, то aRc;
3. антисиметрия - ако aRb и bRa, то a=b.
Релациите £ (за цели числа) и релацията U (включване в множество) имат частичен ред.
Линеен или пълен ред върху множество S е частичен ред R върху S, така че за всеки два елемента a, b или aRb, или bRa е изпълнено. Отношението £ върху множеството от цели числа има свойството линеен ред, но отношението на включване в множеството U не.
Традиционните методи за сортиране се разделят на вътрешни и външни. Вътрешните методи са методи, които могат да се прилагат с приемлива производителност само към онези списъци с данни, които се побират изцяло в основната памет на процесора. Външните методи са тези методи, които са приемливи за файлове с данни, които са твърде големи, за да се поберат в основната памет и следователно трябва да бъдат разположени на външни устройства за съхранение по време на процеса на сортиране. Списъкът с думи често се отнася до набор от записи, разположени в основната памет.
По време на външно сортиране част от файла се чете в основната памет, сортира се там и след това се пренаписва на външно устройство. Този процес се повтаря няколко пъти. Вътрешните методи се използват за размяна на данни, обработени между трансферите.
Според броя на сравненията се разграничават линейни и нелинейни сортове. Линейните алгоритми третират сортирания списък като линейна последователност от елементи, като елементите се избират последователно от горната или долната част на списъка един по един. Нелинейните методи предполагат, че списъците, които сортират, имат структура. Те са най-ефективни, когато списъците се третират като двоични дървета.
Простото сортиране използва един и същ метод през целия процес на сортиране. Простите алгоритми не са непременно неусложнени. Ако разработчикът на сортиране използва различни методи за сортиране на различни етапи, тогава такъв алгоритъм се нарича комбиниран.
В алгоритъм за сравнение данните се подреждат по относителния размер на ключовете в списъка. Методът на разпространение изследва целия ключ или символ по символ. Разпределителното сортиране е полезно, когато се знаят много неща за данните, които се сортират, например разпределението на ключовете през някои интервали, дължината на ключовете, броят на записите.
При метода с най-малко памет паметта се изисква само за програмата и подредения списък. Методите без минимална памет също изискват памет за копие на оригиналния списък. Предимството на сортирането с минимална памет е, че позволява големи списъци да бъдат сортирани в основната памет, макар и с цената на времето за сортиране.
Фундаменталните алгоритмивътрешно сортиране включват алгоритми: линейна селекция, линейна селекция с обмен (метод "балон"), пресяване (също "линейно вмъкване с обмен" или "совалково сортиране"), линейно вмъкване.
Нека да разгледаме всички тези методи.
Линеен избор : Най-малкият елемент се избира и извежда къмprint, в оригиналната последователност се заменя с фиктивен елемент.
Метод с мехурчета:
Линейно вмъкване : елемент от изходната последователност се поставя в изходната последователност между нейния по-голям и по-малък елемент.
Най-често срещаната форма навъншно сортиране е сортиране чрез сливане.
Сортиране чрез сливане : Същността на този метод е, че процесът на сортиране се състои от два етапа - етап на сортиране и етап на сливане.
Стъпката на сортиране (или разпръскване) чете толкова данни наведнъж, колкото могат да се поберат в наличната памет, след което подредените редове от данни се вграждат в паметта по някакъв начин. Тези низове се презаписват от паметта в съответствие с алгоритъм за разпространение, създаден специално за желаното сливане. В повечето алгоритми всички данни се разглеждат по време на стъпката на сортиране преди обединяването. В началото на сливането има семейство от низове, разпределени между устройства. Последващото сливане формира един подреден низ.
Нека да разгледаме пример за сортиране по сортиране.
Дадена е поредица от цели числа a1, a2, ..., an, всяко от които се съдържа в интервала [0, m-1].
Ако числото m не е твърде голямо, тогава дадената последователност може да бъде подредена както следва:
1. организирайте m празни опашки, по една за всяко цяло число от 0 до m-1. Ние наричаме всяка такава опашка лъжичка.
2. Нека разгледаме редицата a1, a2, …, an отляво надясно, като поставим елемента ai в опашката с числото ai.
3. Свързваме тези опашки (приписваме съдържанието на (i + 1)-та опашка към края на i-та опашка) и получаваме подредена последователност като резултат.
защото всеки елемент може да бъде поставен в i-тата опашка за постоянно време, тогава n елемента могат да бъдат поставени в опашкатаза O(n) време. Верижното свързване на m опашки отнема O(m) време. Ако m=O(n), тогава този алгоритъм сортира n цели числа за O(n) време. Нека наречем този алгоритъмsort-pull.
Помислете за пример за такова сортиране.
Сортиране чрез побитово групиране. Това сортиране започва с анализиране на най-малката цифра на ключовата дума. След това всички количества с еднакви значими числа се комбинират в групи.
След като всички стойности са разпределени според това правило, съдържанието на групите се подрежда във възходящ ред на стойността на анализираната цифра и процесът се повтаря, докато няма никакви цифри отляво.
Една базова p бройна система изисква p групи (опашки или черпаци).
| Таблица източник | Първо разпределение | Асоциация | Второ разпределение | Асоциация |
| 0.– 1. 31.01.11.21 2. 02 3. 13 4.– 5. 05 6. 26.16 7. 27 8.– 9. 19.09 | 0. 01.02.05.09 1. 11.13.16.19 2. 21.26.27 3. 31 4.– 5.– 6.– 7.– 8.– 9.– |
Следващото обобщение на сортирането по изтегляне е да го разширим до кортежи с неравна дължина, които ще наричаме низове.
Ако най-дългата верига има дължина k, тогава всяка верига може да бъде допълнена със специален знак до дължина k и след това да се приложи алгоритъмът за побитово групиране (или, както се нарича още, алгоритъмът за лексико-графично сортиране).
Следващото обобщение на сортирането чрез изтегляне е разширяването му до кортежи с различна дължина, които ще наричаме низове.
Ако най-дългият низ има дължина k, тогава всеки низ може да бъде подплатен със специални символи до дължина k и след това да се приложи алгоритъмът за побитово групиране. Ако дългоще има малко вериги в сравнение с общия брой елементи на последователността, тогава разгледаният по-рано алгоритъм е неефективен.
Да разгледаме алгоритъм, който сортира n-елементна последователност от низове с различни дължини, чиито компоненти са числа между 0 и m-1; времето за изпълнение на този алгоритъм върху такава последователност е O(m+l*), където li е дължината на i-тата верига и l*=. Този алгоритъм е полезен в ситуация, в която числата m и l* имат еднакъв ред O(n).
Същността на този алгоритъм е, че първо подрежда веригите в низходящ ред на дължините. Нека lmax е дължината на най-дългата верига. След това сортирането по сортиране се прилага lmax пъти.
Но първото такова приложение (по най-десния компонент) сортира само вериги с дължина lmax. Второто приложение сортира (според (lmax - 1)-ия компонент) онези низове, чиято дължина е най-малко lmax - 1 и т.н.
Вход: Поредица от вериги (кортежи) А1, А2, …, Аn, чиито компоненти са представени с цели числа от 1 до m – 1. Нека li е дължината на веригата Ai = (ai1, ai2, … , aili) и lmax е най-голямото от числата li.
Метод:
1. генериране на списъци със знаци, които се появяват в компонента l на един или повече низове. Изграждаме двойки (l, ail) - за всеки компонент на всяка верига. След това формираме подреден списък: NON-empty[l].
2. Определете дължината на всяка верига, формирайте списъка DL[l], който съдържа указатели на всички вериги с дължина l.
3. Сортираме веригите по компоненти, както в предишните алгоритми, като вземаме предвид списъците NON-EMPLOY и DL.
Алгоритъм на описания метод: