Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритмы сортировки в Delphi

Читайте также:
  1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  2. FL now compiled with Delphi 2005.
  3. Алгоритмы внутренней сортировки
  4. Алгоритмы замещения страниц
  5. Алгоритмы и их свойства. Представление алгоритмов
  6. Алгоритмы и их свойства. Представление алгоритмов
  7. Алгоритмы поиска и индексации
  8. Алгоритмы шифрования
  9. Введение в программирование на языке Pascal Работа с величинами. Ввод-вывод Выражения. Линейные алгоритмы

 

Спілкування між споживачами інформації здійснюється за допомогою певної мови. Мова – це сукупність способів для фіксації повідомлень та передавання їх від джерела інформації до споживача. Набір символів з заданими правилами утворення з цих символів конструкцій, зо допомогою яких описується порядок виконання алгоритму, називається алгоритмічною мовою.

Теоретичну основу мов програмування складають алгоритмічні умови. Звичайно при розробці мови програмування високого рівня спочатку створюється алгоритмічна мова з тією ж назвою. Алгоритмічна мова, призначена для опису алгоритмів розв’язання задач на ЕОМ, називається мовою програмування.

Мови програмування умовно класифікуються таким чином: машинні, асемблерів, машинно-орієнтовані та автокоди, процедурно-орієнтовані та проблемно-орієнтовані, об’єктно-орієнтовані, візуальні. З моменту появи ЕОМ мови програмування пройшли великий шлях розвитку, який можливо подати у вигляді ієрархії рівнів.

Рівень мови програмування:

0-й – Програмування у кодах конкретних машин

1-й – Програмування у мнемокодах

2-й – Програмування в автокодах

 

3-й – Програмування проблемно-орієнтованими кодами

 

4-й – Програмування процедурно-орієнтованими мовами

 

5-й – Програмування функціональними і логічними мовами

 

6-й – Програмування мовами без даних

 

7-й – Програмування об’єктивно-орієнтованими мовами

 

8-й – Програмування візуальними мовами

 

Нульовий рівень – програмування з використання машинних мов. Машинна мова – мова програмування, призначена для представлення програм і даних у формі, придатній для безпосереднього сприйняття їх пристроями даною обчислювальною машиною. Являє собою систему команд, даних і інструкцій, що мають форму двійкових кодів, які не вимагають трансляції і безпосередньо інтерпретуються процесором ЕОМ. Команда складається з коду операцій, адрес операндів, ознак модифікації та індексації адреси. Код операції вказує дію, яку має виконати машина, наприклад,

додавання, множення, ділення і т.д. Адреси операндів визначають дані, що

 

беруть участь в операції. Ознака модифікації адреси складається з ознаки адресації, яка вказує дії над операндами. Ознака індексації вказує дії з індексними регістрами. Таке програмування досить складне в практичному здійсненні, важко здійснювати і перевірку таких кодів.

Перший рівень – програмування мовами символічного кодування (мнемокодами). Мова символічного кодування – мова програмування, що орієнтована на конкретну ЕОМ і полягає в символьному кодуванні машинних операцій за допомогою певного набору мнемонічних символів. Мова утворюється внаслідок простої заміни в кодах машинних операцій тієї або тієї ЕОМ двійкових кодів операцій більше звичними для людини буквеними або буквено-цифровими кодами з десятковими цифрами. Двійкові коди адрес і командах змінюються десятковими кодами. Трансляція з такої мови називається мнемонікою і зводиться до простого перекодування. Використання такої простої вхідної мови набагато спрощує програмування і зменшує кількість помилок. Мнемокоди є базою для створення довершеніших систем автоматизації програмування, а також вони мають самостійне значення як системи програмування для малих ЕОМ, для яких не можна створити транслятори з мов високого рівня внаслідок обмежених можливостей машини.

Подальша автоматизація програмування на рівні машинно-орієнтованих систем складається у використанні автокодів (макромів). Вхідною мовою автокодів є мова рівня один до декількох, тобто одній автокодовій інструкції відповідає кілька машинних команд. Основою авто кодової мови є макрокоманди, що вказують функцію або процедуру за допомогою одного запису. Макрокоманди інтерпретуються в машинні команди спеціальними програмами. Структура команд автокоду визначається структурою команд і даними машинної мови, але автокод допускає на відміну від машинного застосування буквених позначень для операцій і адрес. У порівнянні з мнемокодами автокоди мають ряд переваг: наявність досконаліших методів виявлення помилок на етапі трансляції, різноманітних макрокоманд введення-виведення; зменшення трудових витрат на складання програм. Макроми на рівні з символічним кодуванням допускають використання команд, що не мають прямих аналогів у машинній мові, під час трансляції такі команди змінюються кількома машинними командами. Застосування макромови скорочує програму і значно полегшує процес програмування. До мови даного типу відноситься автокод «Інженер», мова Асемблера.

Мови першого й другого рівнів відносяться до машинно-орієнтованих мов. Машинно-орієнтована мова – мова програмування, яка відображає структуру даної ЕОМ або даного класу ЕОМ.

Починаючи з четвертого рівня розташовані машинно-незалежні мови.

Машинно-незалежна мова – мова програмування, структура та засоби якої не пов’язані ні з якою конкретною ЕОМ і дозволяють виконувати складені на ній програми на будь яких ЕОМ, забезпеченими трансляторами з цієї мови.

 

 

Проблемно-орієнтована мова – мова програмування, призначена для розв’язування певного класу задач. Мова по можливості використовує символіку та систему понять відповідної проблемної області. До цього типу мов відносяться Ліпс [Lips], РПГ [RPG від Report Program Generator], Симула. Ці мови використовуються для запису задач у термінології споживача. Алфавіт цих мов – терміни тих галузей науки і техніки, для яких складається програма. Ці мови не вимагають запису алгоритму як пов’язаної логічної послідовності дій. Досить визначити вхідні дані, вказати дії, які повинні проводитися над ними, і які результати потрібно отримати на виході. Всі інші функції покладаються на транслятор, що визначає, яка логічна схема потрібна для розв’язання задачі, і складає програму. Програма, написана проблемно-орієнтованою мовою, - компактна, зрозуміла фахівцеві в даній галузі знань. Для її складання не потрібно попередніх знань техніки програмування.

Процедурно-орієнтована мова – проблемно-орієнтована мова,що полегшує вираження процедури як точного алгоритму. Основні процедури, що зустрічаються в задачах конкретного класу, реалізовуються найпростіше у відповідні процедурно-орієнтованій мові. Кожна з них призначена для запису алгоритмів розв’язання задач певного класу. Виділяють три великих класи задач: наукові, інженерні та економічні. Специфіка кожного класу знайшла своє відображення в різноманітті мов програмування. Для розв’язання задач кожного з вказаних класів створювалися свої мови. Наприклад, мова Алгол призначена для розв’язання наукових задач, Фортран – для інженерних, Кобол – економічних, Снобол – задач обробки символьних даних.

У цих мовах обчислювальний процес записується як докладна послідовність певних процедур, що не залежать від машини. Використання процедурн-орієнтованих мов дозволило: спростити написання програм, скоротити час їх налагодження, виконувати програму, складену для однієї машини, на іншій.

Паралельно зі спеціалізацією мов у розрізі класів задач існують універсальні мови, які можна використати для програмування задач кількох класів. До таких мов належать мови ПЛ/1, Паскаль, С.

Мови п’ятого рівня призначені для програмування задач у галузі штучного інтелекту. Основною особливістю мов цього рівня, що відрізняють їх від усіх інших мов, є декларативний характер написаних на них програм. Декларативні мови дозволяють програмісту визначити правила за рішенням даної задачі, взаємозв`язку між об’єктами, з якими має справу програма. Декларативні мови поділяються на логічні та функціональні. Мова логічного програмування – мова програмування, яка ґрунтується на принципі завдання сукупності правил без явної вказівки послідовності їх застосування. Найвідомішою мовою логічного типу є Пролог. Будівельними блоками програми є множина об’єктів певної структури, а також функції і відношення, що зв’язують ці об’єкти. Програма мовою Пролог не є такою в традиційному розумінні, оскільки не містить керуючих конструкцій типу умовних операторів, операторів циклу або переходу. Вона являє собою модель певного

 

 

Фрагмента предметної області, про який ідеться в задачі, що розв’язується. Тому програмування Прологом вимагає іншого стилю мислення, відмови від поширених програмістських стереотипів. Замість того,щоб задати певну послідовність дій, що приводить до розв’язання задачі, в програмі мовою Пролог треба описати її зміст у термінах об’єктів і відношень між ними. Таким чином, замість алгоритму розв’язання задачі програміст складає його логічну специфікацію.

Мова функціонального програмування – декларативна мова програмування, що ґрунтується на понятті функції. Функції в мові задають залежність,але не визначають порядок обчислень. З функціональних мов найвідомішою є Ліпс.

Мови п’ятого рівня застосовуються для створення експертних систем, інтелектуальних інформаційних систем, інтелектуальних навчаючих систем.

До мов шостого рівня належать мови без даних. Ця форма мови програмування і керування призначена для роботи з однією певною базою даних і здійснює ті дії програми, які мають бут автоматизовані.

Об`єктно-орієнтована мова – мова програмування, яка підтримує об`єктно-орієнтоване програмування. До даної мови програмування належать С++, Smalltalk.

Всі мови ООП базуються на трьох основоположних концепціях – на інкапсуляції, поліморфізмі та успадкуванні. Інкапсуляція – це механізм, який об’єднує дані та код, що маніпулює з цими даними, захищає їх від зовнішнього втручання або неправильного використання. У ООП дані та програмний код, що обробляє їх, можуть бути об`єднані разом, тоді кажуть, що створюється об’єкт. Об`єкт – суть, яка включає не тільки дані, а й процедури (методи) їх обробки. Суттю може бути, наприклад, запис про студента. Об`єкт включає в себе всі дані, які необхідні, щоб описати суть і функції або методи, які маніпулюють цими даними. Всередині об`єкта коди і дані можуть бути закритими для цього об’єкта або відкритими. Закриті коди або дані недоступні для тих частин програми, які існують поза об`єктом. Якщо коди і дані є відкритими, то незважаючи на те, що вони задані всередині об`єкта, вони доступні для інших частин програми.

Можливість описувати необхідні типи даних, використовуючи класи, дозволяє багато разів використати написану і налагоджену програму. Якщо вам потрібен майже такий самий об`єкт, як розроблений, але який має свої власні визначені характеристики, то механізм успадкування дає можливість більш легкого багаторазового використання об’єкта, після невеликого корегування. Успадкування – це прогрес, за допомогою якого один об’єкт може набувати (успадковувати) основних властивостей іншого об’єкта і додавати до них риси, характерні тільки для нього.

Поліморфізм дає можливість поводитися з об’єктами різного типу так, ніби вони є об’єктами одного типу. Поліморфізм використовує базовий клас як загальний тип для обробки множини похідних типів. У загальному значенні концепцією поліморфізму є ідея «один інтерфейс, множина методів». Це означає, зо можна створити загальний інтерфейс для групи близьких за

 

 

змістом дій. Поліморфізм допомагає знижувати складність програми, дозволяючи використання того самого інтерфейсу для завдання єдиного класу дій. Вибір же конкретної дії, в залежності від ситуації, покладається на компілятор. Поліморфізм дає змогу маніпулювати об’єктами різної міри складності шляхом створення загального для них стандартного інтерфейсу для реалізації схожих дій.

Поширення графічних інтерфейсів користувачів привело до появи візуальних середовищ розробки.

Візуальна мова програмування – мова взаємодії користувача з системою програмування, що реалізовується діалоговими засобами графічного інтерфейсу користувача. Поява візуальних мов була наслідком складності програмування графічного інтерфейсу програм,призначених для виконання в операційних середовищах типу Windows. Щоб полегшити програмування елементів графічного інтерфейсу програм і використовуються візуальні мови. Наприклад, малювання діалогового вікна введення даних зводиться до малювання його на екрані або до вибору і корегування прототипу, що пропонується в режимі діалогу. При цьому застосовуються курсор миші, кнопки, меню та інші елементи. Візуальними мовами програмування можна розробляти як оболонки для програм,що вже існують, так і створювати нові. Для цього в мовах візуального програмування розроблений зручний механізм написання і підключення на базовій мові програмування високого рівня, такого як Бейсік, Паскаль, С++. До цієї групи мов належать Visual Basic, PowerBuilder, Borland C++ Builder.

Наведена класифікація є умовною, оскільки практично використовувані мови поєднують властивості різних мов з наведеної класифікації.

 

Алгоритмы сортировки в Delphi

Алгоритм 1. Сортировка вставками.

суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку. Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после — большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal:

Program InsertionSort;

Var A,B: array[1..1000] of integer;

N,i,j: integer;

Begin

{Определение размера массива A (N) и его заполнение}

{сортировка данных}

for i:=1 to N do

begin

j:=i;

while (j>1) and (B[j-1]>A[i]) do

begin

B[j]:=B[j-1];

j:=j-1;

end;

B[j]:=A[i];

end;

{Вывод массива B}


End.

 

В принципе, данную сортировку можно реализовать и без дополнительного массива B, если сортировать массив A сразу при считывании, т. е. осуществлять вставку нового элемента в массив A.

Алгоритм 2. Пузырьковая сортировка в Delphi.

Метод состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N — количество элементов. Вот как это можно реализовать:

Program BubbleSort;
Var A: array[1..1000] of integer;
N,i,j,p: integer;
Begin
{Определение размера массива A (N) и его заполнение}

{сортировка данных}
for i:=1 to n do
for j:=1 to n-i do
if A[j]>A[j+1] then
begin {Обмен элементов}
p:=A[j];
A[j]:=A[j+1];
A[j+1]:=P;
end;
{Вывод отсортированного массива A}

End.

Алгоритм 3. Сортировка Шейкером в Delphi.

Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N — количество элементов. Реализация данного алгоритма выглядит так:

Program ShakerSort;
Var A: array[1..1000] of integer;
N,i,j,p: integer;
Min, Max: integer;
Begin
{Определение размера массива A — N) и его заполнение}

{сортировка данных}
for i:=1 to n div 2 do
begin
if A[i]>A[i+1] then
begin
Min:=i+1;
Max:=i;
end
else
begin
Min:=i;
Max:=i+1;
end;
for j:=i+2 to n-i+1 do
if A[j]>A[Max] then
Max:=j
else
if A[j]<A[Min] then
Min:=j;
{Обмен элементов}
P:=A[i];
A[i]:=A[min];
A[min]:=P;
if max=i then
max:=min;
P:=A[N-i+1];
A[N-i+1]:=A[max];
A[max]:=P;
end;
{Вывод отсортированного массива A}

End.

 

Рассмотрев эти методы, сделаем определенные выводы. Их объединяет не только то, что они сортируют данные, но также и время их работы. В каждом из алгоритмов присутствуют вложенные циклы, время выполнения которых зависит от размера входных данных. Значит, общее время выполнения программ есть O(n2) (константа, умноженная на n2). Следует отметить, что первые два алгоритма используют также O(n2) перестановок, в то время как третий использует их O(n). Отсюда следует, что метод Шейкера является более выгодным для сортировки данных на внешних носителях информации.

Если вы думаете, что бравые «алгоритмщики» остановились на достигнутом, то вы ошибаетесь. Видите ли, временная оценка O(n2) показалась им слишком громоздкой, и они, жадины такие, решили еще потратить свое время, чтобы впоследствии сэкономить наше. Итак, давайте теперь рассмотрим более быстрые алгоритмы.

Алгоритм 4. Сортировка слиянием в Delphi.

 

Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Корректность данного метода практически очевидна, поэтому перейдем к реализации.

Program SlivSort;
Var A,B: array[1..1000] of integer;
N: integer;
Procedure Sliv(p,q: integer); {процедура сливающая массивы}
Var r,i,j,k: integer;
Begin
r:=(p+q) div 2;
i:=p;
j:=r+1;
for k:=p to q do
if (i<=r) and ((j>q) or (a[i]<a[j])) then
begin
b[k]:=a[i];
i:=i+1;
end
else
begin
b[k]:=a[j];
j:=j+1;
end;
for k:=p to q do
a[k]:=b[k];
End;
Procedure Sort(p,q: integer); {p,q — индексы начала и конца сортируемой части массива}
Begin
if p<q then {массив из одного элемента тривиально упорядочен}
begin
Sort(p,(p+q) div 2);
Sort((p+q) div 2 + 1,q);
Sliv(p,q);
end;
End;
Begin
{Определение размера массива A — N) и его заполнение}

{запуск сортирующей процедуры}
Sort(1,N);
{Вывод отсортированного массива A}

End.

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай T(n) — время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2T(n/2)+O(n) (O(n) — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n/2)+O(n)=4T(n/4)+2O(n)= … = 2kT(1)+kO(n)

Осталось оценить k. Мы знаем, что 2k=n, а значит k=log2n. Уравнение примет вид T(n)=nT(1)+ log2nO(n). Так как T(1) — константа, то T(n)=O(n)+log2nO(n)=O(nlog2n). То есть, оценка времени работы сортировки слиянием меньше, чем у первых трех алгоритмов (я прошу прощения у тех, кто не понял мои рассуждения или не согласен с ними, — просто поверьте мне на слово). Перед тем как объяснить, чем этот метод лучше, рассмотрим еще один алгоритм.

Алгоритм 5. Сортировка двоичной кучей в Delphi

Проблема первых трех алгоритмов, описанных в прошлой части статьи, состояла в том, что после того как элемент занимал свое место, информация об уже произведенных сравнениях никак не использовалась. Структура двоичного дерева позволяет сохранить эту информацию. Итак, представим массив в виде дерева (Рис. 1). Корень дерева — элемент с индексом 1; элемент с индексом i является «родителем» для элементов с индексами 2*i и 2*i+1, а те, в свою очередь, являются его «детьми». Каждый элемент кроме первого имеет «родителя» и может иметь до двух «детей» — речь ведь идет именно о ДВОИЧНОМ дереве. Очевидно, что корнем дерева является наименьший элемент, а наибольший не имеет детей. Тут возникают два вопроса: как нам такую кучу наплодить? И зачем нам это вообще нужно? Пренебрегая порядком, отвечу сразу на второй вопрос: мы хотим извлечь из кучи минимальный элемент, а потом как-то преобразовать и восстановить кучу. Таким образом, по очереди извлечь все элементы и получить отсортированный массив. И вот как мы собираемся это сделать: пусть поддеревья с корнями 2*i и 2*i+1 уже имеют свойство кучи, мы же хотим, чтобы такое свойство имело и поддерево с корнем i. Для этого, если корень больше наименьшего своего «ребенка», мы меняем корень дерева (элемент с индексом i) с этим «ребенком», после повторяем алгоритм для поддерева, куда перешел бывший корень. Выполняя этот алгоритм «снизу вверх» (сначала для маленьких поддеревьев, потом для больших), мы добьемся того, что свойство кучи будет выполняться для всего дерева. Извлечение элемента происходит очень простым способом: мы ставим последний элемент на первое место и запускаем алгоритм исправления кучи от корня дерева… Я тут много наговорил, но на самом деле, реализация совсем несложная:

Program HeapSort;
Var A,B: array[1..1000] of integer;
N,i,P: integer;
Procedure Heapi(ind: integer); {процедура, формирующая и исправляющяя кучу}
Var k: integer;
Begin
k:=ind*2;
If k<=N then
begin
if (k+1<=N) and (A[k]>A[k+1]) then
k:=k+1;
if A[ind]>A[k] then
begin
P:=A[ind];
A[ind]:=A[k];
A[k]:=P;
Heapi(k);
end;
end;
End;
Begin
{Определение размера массива A — N) и его заполнение}

{формирование кучи}
for i:=N div 2 downto 1 do
Heapi(i);
{формирование массива B}
for i:=1 to N do
begin
B[i]:=A[1];
A[1]:=A[N];
N:=N-1;
Heapi(1);
end;
{Вывод отсортированного массива B}

End.

 

А теперь главное, т. е. оценка сложности. Время работы процедуры исправляющей кучу зависит от высоты дерева. Высота всего дерева равна log2n, значит, время работы процедуры есть O(log2n). Программа состоит из двух частей: формирование кучи и создание отсортированного массива B. Время исполнения каждой из частей не больше O(n log2n) (в каждой части исправляющая процедура вызывается не более n раз). Значит, время работы то же, что и в сортировке слиянием.

Теперь лирическое отступление насчет времени работы. Может, читатель думает, что быстрые алгоритмы сложны в исполнении и проще написать что-то вроде сортировки вставками. Что ж, рассмотрим простой пример: допустим, вы написали сортировку вставками, тщательно, с помощью ассемблера, и время работы получилось 2n2, а какой-нибудь раздолбай написал сортировку слиянием со временем работы 50nlog2n. И тут появилась необходимость отсортировать 1000000 элементов (что в наше время не редкость). Вы использовали крутой компьютер, который делает 108 операций сравнения и перестановки в секунду, а у него компьютер похуже — всего 106 операций в секунду. И вы будете ждать 2*(106)2/108 = 20 000 секунд (приблизительно 5.56 часов), а ваш конкурент — 50*(106)*log2(106)/106 = 1000 секунд (приблизительно 17 минут). Надеюсь, вы проведете это время (5 часов) с пользой для себя и поймете, что хороший алгоритм — быстрый алгоритм:-). Хотя, если вы будете сортировать маленький массив или много маленьких массивов, то 2n2 для вас будет лучше, чем 50nlog2n. Эту закономерность использует один из способов оптимизации сортировки слиянием: сортировать маленькие части массива вставками.

 

Теперь переходим к самому интересному, а именно к одной из самых быстрых и эффективных из известных сортировок, которая так и называется — «быстрая сортировка».

Алгоритм 6. Быстрая сортировка.

Как и в сортировке слиянием, массив разбивается на две части, с условием, что все элементы первой части меньше любого элемента второй. Потом каждая часть сортируется отдельно. Разбиение на части достигается упорядочиванием относительно некоторого элемента массива, т. е. в первой части все числа меньше либо равны этому элементу, а во второй, соответственно, больше либо равны. Два индекса проходят по массиву с разных сторон и ищут элементы, которые попали не в свою группу. Найдя такие элементы, их меняют местами. Тот элемент, на котором индексы пересекутся, и определяет разбиение на группы. Классическая реализация алгоритма выглядит так:

Program QuickSort;
Var A: array[1..1000] of integer;
N,T: integer;
Procedure Sort(p,q: integer); {p,q — индексы начала и конца сортируемой части массива}
Var i,j,r: integer;
Begin
if p<q then {массив из одного элемента тривиально упорядочен}
begin
r:=A[p];
i:=p-1;
j:=q+1;
while i<j do
begin
repeat
i:=i+1;
until A[i]>=r;
repeat
j:=j-1;
until A[j]<=r;
if i<j then
begin
T:=A[i];
A[i]:=A[j];
A[j]:=T;
end;
end;
Sort(p,j);
Sort(j+1,q);
end;
End;
Begin
{Определение размера массива A — N) и его заполнение}

{запуск сортирующей процедуры}
Sort(1,N);
{Вывод отсортированного массива A}

End.

Что же делает данный алгоритм таким быстрым? Ну во-первых, если массив каждый раз будет делится на приблизительно равные части, то для него будет верно то же соотношение, что и для сортировки слиянием, т. е. время работы будет O(nlog2n). Это уже само по себе хорошо. Кроме того, константа при nlog2n очень мала, ввиду простоты внутреннего цикла программы. В комплексе это обеспечивает огромную скорость работы. Но как всегда есть одно «но». Вы, наверное, уже задумались: а что если массив не будет делится на равные части? Классическим примером является попытка «быстро» отсортировать уже отсортированный массив. При этом данные каждый раз будут делиться в пропорции 1 к n-1, и так n раз. Общее время работы при этом будет O(n2), тогда как вставкам, для того чтобы «понять», что массив уже отсортирован, требуется всего-навсего O(n). А на кой нам сортировка, которая одно сортирует хорошо, а другое плохо? А собственно, что она сортирует хорошо? Оказывается, что лучше всего она сортирует случайные массивы (порядок элементов в массиве случаен). И поэтому нам предлагают ввести в алгоритм долю случайности. А точнее, вставить randomize и вместо r:=A[p]; написать r:=A[random(q-p)+p]; т. е. теперь мы разбиваем данные не относительно конкретного, а относительно случайного элемента. Благодаря этому алгоритм получает приставку к имени «вероятностный». Особо недоверчивым предлагаю на своем опыте убедится, что данная модификация быстрой сортировки сортирует любые массивы столь же быстро.

 

А теперь еще один интересный факт: время O(nlog2n) является минимальным для сортировок, которые используют только попарное сравнение элементов и не использует структуру самих элементов. Тем, кому интересно, откуда это взялось, рекомендую поискать в литературе, доказательство я здесь приводить не намерен, не Дональд Кнут, в конце концов:-). Но вы обратили внимание, что для рассмотренных алгоритмов в принципе не важно, что сортировать — такими методами можно сортировать хоть числа, хоть строки, хоть какие-то абстрактные объекты. Следующие сортировки могут сортировать только определенные типы данных, но за счет этого они имеют рекордную временную оценку O(n).

Алгоритм 7. Сортировка подсчетом.

Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место. Если все равно непонятно, смотрите реализацию:
Program CountingSort;
Var A,B: array[1..1000] of byte;
C: array[byte] of integer;
N,i: integer;
Begin
{Определение размера массива A (N) и его заполнение}

{сортировка данных}
for i:=0 to 255 do
C[i]:=0;
for i:=1 to N do
C[A[i]]:=C[A[i]]+1;
for i:=1 to 255 do
C[i]:=C[i-1]+C[i];
for i:=N downto 1 do
begin
B[C[A[i]]]:=A[i];
C[A[i]]:=C[A[i]]-1; {здесь мы избегаем возможности записи двух одинаковых чисел в одну ячейку}
end;
{Вывод массива B}

End.

Этот простой метод не использует вложенных циклов и, учитывая небольшой диапазон значений, время его работы есть O(n).
Рассмотрев такое количество сортировок, можно задуматься: а будет ли результат их работы одинаковым? Странный вопрос, ведь все сортировки правильно сортируют данные, так почему же результат работы может быть разным? Хорошо, объясню: меньшие элементы всегда расположены перед большими, но порядок одинаковых элементов может быть нарушен. Если мы сортируем данные, которые состоят из одного ключа, то мы, конечно, не заметим разницы. Но если к ключу прилагается дополнительная информация, то одна сортировка может вернуть нам 1977 "Иванов" и 1977 "Сидоров", а другая — 1977 "Сидоров" и 1977 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.

Алгоритм 8. Цифровая сортировка.

Этой сортировкой можно сортировать целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы. Реализация такова:

Program RadixSort;
Var A,B: array[1..1000] of word;
N,i: integer;
t: longint;
Procedure Sort; {сортировка подсчетом}
Var C: array[0..9] of integer;
j: integer;
Begin
For j:=0 to 9 do
C[j]:=0;
For j:=1 to N do
C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1;
For j:=1 to 9 do
C[j]:=C[j-1]+C[j];
For j:=N downto 1 do
begin
B[C[(A[j] mod (t*10)) div t]]:=A[j];
C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]-1;
end;
End;
Begin
{Определение размера массива A (N) и его заполнение}

{сортировка данных}
t:=1;
for i:=1 to 5 do
begin
Sort;
A:=B;
t:= t*10;
end;
{Вывод массива A}

End.

Так как сортировка подсчетом вызывается константное число раз, то время работы всей сортировки есть O(n). Заметим, что таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям.




Дата добавления: 2014-12-19; просмотров: 53 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Поняття алгоритмічної мови, її структура та типові компоненти.| Барвинок малый

lektsii.net - Лекции.Нет - 2014-2024 год. (0.019 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав