Алгоритми за сортиране 1част. Лекция

Алгоритми за сортиране
Лекция 4

1. Въведение
Сортирането е процес, при който последователност
от n елемента a1, a2,...., an се подреждат в
определен ред.
В зависимост от местонахождението на данните
сортирането може да бъде:
1.външно – данните са записани върху външен
носител и достъпът до тях е последователен
или цикличен;
2.вътрешно – данните са в оперативната памет
и достъпът до тях е пряк. В зависимост от
операцията, извършвана над елементите
сортиращите алгоритми са:
 частни алгоритми (Сортиране чрез

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

1. Въведение
 общи (универсални) алгоритми

(сортиране чрез сравнение - използват се
операциите <, > и = и т.н.).
Прилагат се за сортиране на елементи от
произволен тип. Те са:
 основни (преки) – сортиране чрез пряко
вмъкване, сортиране с пряк избор,
сортиране с пряка размяна. Те са побавни и имат сложност n2;
 бързи – сортиране с алгоритъма на Шел,
сортиране чрез сливане, бързо сортиране,
пирамидално сортиране.
Имат сложност n log n.

2. Сортиране чрез сравнение
2.1. Дърво на сравненията
Дърво на сравненията за
множеството {X, Y, Z}
Броят на възможните изходи
(листата на дървото) е 3!.
За n елемента е n!.
int Comp_Tree (int X, int Y, int Z) {
if (X < Y)
if (Y < Z) cout<<X<<"\n"<<Y<<"\n"<<Z;
else if (X < Z)
cout<<"\n"<<X<<Z<<"\n"<<Y;
else cout<<Z<<"\n"<<X<<"\n"<<Y;
else
if (Y < Z)
if (X < Z) cout<<Y<<"\n"<<X<<"\n"<<Z;
else cout<<Y<<"\n"<<Z<<"\n"<<X;
else cout<<Z<<"\n"<<Y<<"\n"<<X;
return 1;}