![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
for(i=0; i<n-1; i++) {
i_min = i;
for(j = i+1; j < n; j++)
if (a[i_min] > a[j]) i_min = j;
if (i_min!= i) { // Переставляем элементы
r = a[i_min]; a[i_min] = a[i]; a[i] = r;
}
}
}
Реже используются: 3) сортировка с помощью прямого (двоичного) включения; 4) шейкерная сортировка (модификация пузырьковой).
К улучшенным методам сортировки относятся следующие.
1. Метод Д. Шелла (1959), усовершенствование метода прямого включения.
2. Сортировка с помощью дерева, метод HeapSort, Д. Уильямсон (1964).
3. Сортировка с помощью разделения, метод QuickSort, Ч. Хоар (1962), улучшенная версия пузырьковой сортировки, являющийся на сегодняшний день самым эффективным методом.
Идея метода разделения QuickSort заключается в следующем. Выбирается значение ключа среднего m -го элемента x = a [ m ]. key. Массив просматривается слева направо до тех пор, пока не будет обнаружен элемент a [ i ]. key > x. Затем массив просматривается справа налево, пока не будет обнаружен элемент a [ j ]. key < x. Элементы a [ i ] и a [ j ] меняются местами. Процесс просмотра и обмена продолжается до тех пор, пока i не станет больше j. В результате массив оказывается разбитым на левую часть a [ L ],0 £ L £ j с ключами меньше (или равными) x и правую a [ R ], i £ R < n с ключами больше (или равными) x.
Алгоритм такого разделения очень прост и эффективен:
i = 0; j = n – 1; x = a[(L + R)/2].key;
while (i <= j) {
while (a[i].key < x) i++;
while (a[j].key > x) j--;
if (i <= j) {
r = a[i]; // Переставляем элементы
a[i] = a[j];
a[j] = r;
i++; j--;
}
}
Чтобы отсортировать массив, остается применять алгоритм разделения к левой и правой частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из одного единственного элемента. Алгоритм получается итерационным, на каждом этапе которого стоят две задачи по разделению. К решению одной из них можно приступить сразу, для другой следует запомнить начальные условия (номер разделения, границы) и отложить ее решение до момента окончания сортировки выбранной половины.
Рекурсивная функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид (begin – первый элемент массива, end – последний элемент массива):
void Quick_Sort(int *a, int begin, int end)
{
int left, right, x;
left = begin;
right = end;
x = a[(left+right)/2];
do {
while(a[left] <x) left++;
while(x < a[right]) right--;
if(left <= right){
x = a[left];
a[left] = a[right];
a[right] = x;
left++;
right--;
}
} while(left<=right);
if(begin < right) Quick_Sort(a, begin, right);
if(left < end) Quick_Sort(a, left, end);
}
Обращение к этой функции Quick_Sort(a, 0, n-1);
Сравнение методов сортировок показывает, что при n > 100 наихудшим является метод пузырька, метод QuickSort в 2-3 раза лучше, чем HeapSort, и в 3-7 раз, чем метод Шелла.
Дата публикования: 2015-02-22; Прочитано: 229 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!