2015-09-06
444
Быстрая сортировка, хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов сортировки. Метод основан на принципе «разделяй-и-властвуй».
Общая схема быстрой сортировки такова: из массива выбирается некоторый опорный элемент a[i], запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] – вправо (рис. 5.5). Теперь массив состоит из двух подмножеств, причем левое подмножество меньше, либо равно правого:
Рис. 5.5. Разделение массива на два подмассива
Для каждого подмассива будем иметь: если в подмассиве более двух элементов, рекурсивно запускается для него та же процедура. В конце получится полностью отсортированная последовательность.
Рассмотрим алгоритм быстрой сортировки подробнее.
1. На входе задаем массив a[0]... a[N] и опорный элемент p, по которому будет производиться разделение.
2. Введем два указателя: i и j (рис. 5.6). В начале алгоритма они указывают, соответственно, на левый и правый концы последовательности.
|
|
|
3. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p.
4. Аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.
5. Если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i, j по тем же правилам.
6. Повторяем шаг 3, пока i <= j.
Рассмотрим работу процедуры быстрой сортировки для массива a[0]...a[6] и опорного элемента p = a[3] (рис. 5.6).
Рис. 5.6. Иллюстрация алгоритма быстрой сортировки
Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой – больше, либо равны p. Разделение завершено.
Листинг 5.4. Задать исходный массив х[N]. Количество элементов массива N и значения элементов массива ввести с клавиатуры. Применяя алгоритм быстрой сортировки, отсортировать исходный массив в порядке возрастания его элементов. Вывести на экран дисплея исходный и отсортированный массивы.
//L5_4.cpp
#include <iostream>
using namespace std;
void qs(int* s_arr, int first, int last); // Прототип функции qs()
int main()
{
setlocale(LC_CTYPE,"russian");
int i, n, *x;
do
{
cout<<"Введите число элементов массива ";
cin>>n;
}while (n<=1);
x=new int[n];
for(i=0; i<n; i++)
{
cout<<"Введите x("<<i+1<<")=";
cin>>x[i];
}
cout<<"Исходный массив\n";
for(i=0; i<n; i++)
cout<<x[i]<<" ";
cout<<endl;
qs(x,0,n-1);
cout<<"Полученный массив\n";
for(i=0;i<n;i++)
cout<<x[i]<<" ";
cout<<endl;
return 0;
}
void qs(int* s_arr, int first, int last)
{
int i = first, j = last, x = s_arr[(first + last) / 2];
do {
while (s_arr[i] < x) i++;
while (s_arr[j] > x) j--;
if(i <= j) {
if (i < j) swap(s_arr[i], s_arr[j]);
|
|
|
i++;
j--;
}
} while (i <= j);
if (i < last)
qs(s_arr, i, last);
if (first < j)
qs(s_arr, first, j);
}
На рис. 5.7 приведен результат выполнения программы листинга 5.4.
Рис. 5.7. Результат работы программы листинга 5.4
