Подреждане по големина (сортиране)

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

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

 За целта тя се разбива на отделни информационни единици с еднаква структура. Всяка информационна единица от своя страна се състои от една или няколко съставни части. Информационните единици се наричат понякога документи, записи, обекти, елементи и др., а съставните им части - признаци или ключове.

В редица практически случаи информацията, представена чрез едномерни масиви (редици от елементи) или таблици (двумерни масиви), се подрежда (сортира) по определен съдържателен признак. Например да разгледаме списък на студенти от една група, съдържаща за всеки студент следните данни: факултетен номер; име и фамилия;оценка от дипломата за средно образование. Този списък можем да представим като една структурна величина от тип таблица, като всеки ред е запис с полета за: факултетния номер; име и фамилия; оценка:

 

Таблицата е съставена по случаен начин – например в реда, в който са дали документите. От тази таблица може да се съставят три други таблици:

T1 - в която редовете са подредени по факултетните номера. На първо място ще е Кирица Стоянова, а на последно - Стоян Стоилов.

T2 - в която редовете са подредени по азбучен ред на имената. На първо място ще е Димитър Николов, а на последно - Стоян Стоилов.

ТЗ - в която редовете са подредени по успех, като на първо място ще е Кирил Банков, а на последно - Иван Иванов.

С подредени масиви и таблици се извършват по-лесно някои действия, които се срещат в практиката. Най-често прилаганите действия са търсене на елемент, вмъкване, премахване или замяна на елемент в подреден масив.

Подреждането на документите може да се извършва по един или няколко признака, но в изложените тук алгоритми се предполага, че подреждането се извършва само по един признак.

Ще разгледаме няколко алгоритъма за подреждане, като за простота предполагаме, че подредбата се извършва над елементите на едномерен масив. Подреждането на елементи на таблици се извършва по аналогичен начин.

Нека А=(a1, a2, a3, …, an) са елементи на даден масив.

Да се сортира масивът А, означава да се разместят елементите му по такъв начин, че за елементите на новополучения масив А=(ai1, ai2, …, ain) да са в сила условията:

ai1≤ai2≤ … ≤ain – сортиране във възходящ (нарастващ) ред

ai1≥ai2≥ …≥ain – сортиране в низходящ (намаляващ) ред

За да е възможно да се извършва сортиране на елементите на масив, е необходимо базовият тип на масива да допуска сравняване на елементите му.

За операцията сортиране се познават няколко основни метода и множество техни модификации. Сеща ще разгледаме идеята на метода на “мехурчето” за сортиране на едномерен масив.

 

1. Сортиране на едномерен масив по метода на “мехурчето”

Елементите на масива се преглеждат отляво надясно. Всеки два съседни елемента, които не са в нарастващ ред, разменят местата си. Този процес продължава до пълното сортиране на масива.

Пример: Нека А=(7, 0, 19, 25, 5). Последователността от разместванията е следната:

 Първо преглеждене: 0, 7, 19, 5, 25

При първото преглеждане на масива най-големият елемент на масива “изплува като мехурче” в края на масива и вече е подреден на мястото си.

Второ преглеждене: 0, 7, 5, 19, 25

При второто преглеждане на масива най-големият измежду останалите елементи заема предпоследно място.

Трето преглеждене: 0, 5, 7, 19, 25

 

Блок –схема на алгоритъма за сортиране по метода на мехурчето

 

  

2. Сортиране на едномерен масив по метода на пряката селекция

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

3. Друг алгоритъм за сортиране на едномерен масив.

 Състои се в следното: сравняват се последователно два съседни елемента. Ако първият е по-малък от втория, се преминава към следващия. Ако вторият е по-малък, се започват сравнения с предишните елементи, докато на елемента не се намери подходящото място. В това връщане назад може да се стигне до първия елемент.

Схема на алгоритъма:

 

 

 

На следващата таблица са дадени измененията на масива А; първата колона съответства на началното състояние на А.

 

 

4. Сортиране чрез „вмъкване"

Нека А е едномерен масив с n, n≥2 елемента, в който първите k елемента 1≤k<n са вече подредени. Чрез сравняване на елемента аk+1 с част или с всичките подредени елементи a1, a2, …, ak елементът аk+1 може да се „вмъкне" между тях така, че вече първите k+1 елемента на A да са също подредени. Точното описание на алгоритъма е следното:

 Алгоритъм I

I1. [Начален брой подредени елементи.] k:=1

I2. [Сравняване.] Ако аk≤аk+1, изпълнете I4

I3. [“Вмъкване”.] Вмъкнете елемента аk+1 между първите k подредени елементи а1, a2, …, аk, така че новополучената последователност от k+1 елемента да остане подредена

I4. [Проверка за край.] Ако k = n-1, изпълнете I6

I5. [Подготовка за следващо сравнение.] k:=k+1, изпълнете I2

I6. [Край.] Прекратете пресмятанията.

Изпълнението на т. I3 е дадено на следващата блок-схема (аl≤аk+1 трябва да се разбира като сравнение на аl с елемента, който се „вмъква", а не като сравнение на аl, с елемента от (k+1) място).

 

Пример за изпълнение на алгоритъм I е даден в таблицата

 

Разгледаните досега алгоритми за подреждане имат една обща слабост. Докато даден елемент заеме своето постоянно място, той последователно си разменя местата със съседни елементи, като по този начин се движи в определена посока. Основателно се поставя въпросът, не е ли възможно елементите да заемат своите постоянни места след по-малък брой премествания.  Съществува т. н. метод на Д. Шел, който отговаря положително на този въпрос.

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

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

С още по-ефективни методи за сортиране и други алгоритми можете да се запознаете в книгите:

1. Бърнев П., П. Азълов, Алгоритми, Народна просвета, София, 1978

2. Седжуик Р., Алгоритми на С, Софтпрес, София, 2002 г.

3. Наков П., П. Добриков, Програмиране =++Алгоритми, Top Team Co

4. Харис С., Дж. Рос, Основи на алгоритмите, Алекс Софт, 2006 г.

5. Амерал Л., Алгоритми и структури от данни в С++, Софтех, София, 2001 г.

и др.

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