Сортиране мерен масив

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

Нека последователност от елементи - А1. А2. ..., А п. Сортирането е пермутация на тези елементи в нова поръчка Ak1. AK2. ..., Akn. Това разположение отговаря на стойностите на функцията F, така че съотношението доста F (Ak1) Като всеки изчислителен процес от сортиране има свои критерии за сравнителна оценка на качеството на програмата и съответния алгоритъм. Тези критерии са: използването на паметта и по време на работа. счита този вид, в който данните се сортират по същия масив, където суровите данни за добра критерий памет.
брой ключови сравнения (C), броят на трансфер на данни (М): две показателите, използвани за оценка на времето за сортиране. Добър сортиране по време счита, в които броят на сравнения C = N * Ln (N). Чрез прости, че не е много добра, те са нещо, в което броят на сравненията е пропорционална на квадрата на измерение N на оригиналния масив C? N2. Трябва да се отбележи, че на фигури С и М зависи основно от първоначалния ред на сортиран масив. Най-тежки (Mach) се счита за случая, когато масива се подредени в обратен ред. По-долу ще разгледаме трите най-добре познат метод на сортиране едномерен масив. Сравнителен времето на характеристика на тези методи са дадени в следната таблица:

Сортиране прост обмен. метод балон.

Пример 32. метод на сортиране балон (подредени) в възходящ ред на масив от 8 числа (44, 55, 12, 42, 94, 18, 06, 67).