Тема №6. Классические алгоритмы сортировки (2 часа)
Cортировка массивов. Сортировка с помощью прямого включения. Сортировка с помощью прямого выбора. Сортировка с помощью прямого обмена. Улучшенные методы сортировки. Сортировка с помощью включений с уменьшающимися расстояниями. Сортировка с помощью дерева. Сортировка с помощью разделения. Нахождение медианы. Сортировка последовательностей. Прямое слияние. Естественное слияние.
Сортировка — процесс перестановки элементов данного множества в определенном порядке.
Цель сортировки — облегчение последующего поиска элементов в упорядоченном массиве.
Сортировка обменом
//===========================================================
void Swap(float &a; float &b)
{
float c;
c = a; a = b; b = c; // Обмен a и b друг с другом через с
}
//===========================================================
void BubbleSort_v1() // Сортировка обменом (пузырьковая) вариант №1
{
int i, j;
char flag = 1; // Нет обмена f = 0, был обмен f = 1
i = N-1;
While( (i > = 0) && f)
{
f = 0; // Считаем, что обмена не было
for(j = 0; j < i; j++) // Цикл по j от 0 пока j меньше i
{
f = 1; // Обмен был
Swap(a[j], a[j+1]); // Поменять местами a[j] и a[j+1]
i--; // Декремент i на единицу
}
}
}
//============================================================
void BubbleSort_v2() // Сортировка обменом (пузырьковая) вариант №2
{
int i, j;
char flag = 1; // Нет обмена f = 0, был обмен f = 1
i = N-1;
While( (i > = 0) && f)
{
f = 0; // Считаем, что обмена не было
for(j = 0; j < i; j++) // Цикл по j от 0 пока j меньше i
{
f = 1; // Обмен был
Swap(a[j], a[j+1]); // Поменять местами a[j] и a[j+1]
i--; // Декремент i на единицу
}
}
}
//============================================================
Сортировка выбором
При этом методе сортировки в неупорядоченной последовательности выбирается минимальный элемент, который исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную. Процесс повторяется до тех пор, пока все элементы не будут выбраны. Очевидно, что все выбранные элементы образуют упорядоченную последовательность.
Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:
а) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр.
б) Минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.
В этом случае программа сортировки выбором нуждается во вспомогательной функции поиска индекса минимального элемента из списка переменной длины — от элемента с некоторым индексом start до последнего элемента массива.
int function m_i_n (int start, integer a);
{
//Ищет минимальный элемент правее start (включая start)
//и возвращает его номер
int m, i;
m = start;
for (i = start+1; i <= N; i++)
if (a[i]<a[m]) m = i;
return m;
}
Необходима также процедура, обеспечивающая обмен местами двух элементов — найденного при i-м просмотре минимального элемента и элемента с индексом i.
void function Swap (int *a, int *b)
{
int c;
c = &a; *a = &b; *b = c;
}
Процедура сортировки выбором имеет вид:
void function sort_choice (int *t[]);
{
int i;
for ( i = 0; i < N; i++) Swap (t[m_i_n(i,a)], t[i]);
return;
}
=================================================
Приведем еще одну реализацию алгоритма простого выбора.
#define N 8;
int a[N];
int x, i, j, k;
void main()
{
for (i = 0; i < N; i++) scanf(''%d '', a[i]);
for (i = 0; i < N; i++)
{
k = i; x = a[i];
for (j = i+1; j < N; j++)
if (a[j]<x) { k = j; x = a[j];}
a[k] = a[i]; a[i] = x
}
for ( i = 0; i < N; i++) printf(''%d '', a[i]);
}
Быстрая сортировка (рекурсивный алгоритм)
#define N 16 // Число элементов в массиве
int a[N], i;
// ------------------------------ //
int SORT (int l, int r)
{
int i, j, x, w;
i = l; j = r; x = a[(l+r) / 2];
do
{
while (a[i]<x) i = i+1;
while (x<a[j]) j = j-1;
if (i <= j)
{
w = a[i]; a[i] = a[j]; a[j] = w; i = i+1; j = j-1;
}
}
while (i <= j)
if (l<j) SORT (l,j);
if (i<r) SORT (i,r);
}
//-------------------------------------
int main()
{
for (i = 1; i < N; i++) scanf (''%d'', &a[i]);
SORT (1,N);
for (i = 1; i < N; i++) printf (''%d'', a[i]);
}
//-------------------------------------
Рисунок — Алгоритм быстрой сортировки (рекурсивный вариант)