Продолжение предыдущей статьи...
Рекурсивные алгоритмы и улучшение известных нам из предыдущей статьи.
Быстрая сортировка
Теперь коснемся третьего улучшения метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой сортировки, то следует ожидать относительно существенного улучшения. Оно, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его изобретатель Ч. Хоар назвал метод быстрой сортировкой (QuickSort).
Алгоритм. Выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент , затем будем просматривать массив справа, пока не встретим . Теперь Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена , пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую – с ключами больше (или равными) x.
Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей для разделения понадобится два обмена: 18<>44 и 6<>55: .
Последние значения индексов таковы: i =5, j =3. Ключи меньше или равны ключу x=42, а ключи больше или равны x. Следовательно, существует две части, а именно и .
Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям частей, и так до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента. Эти действия описываются процедурой QuickSort. В ней процедура Sort рекурсивно обращается сама к себе.
void QuickSort(int l, int r, int *a, int n)
{
int i=l, j=r, x, w, k;
x=a[(l+r)/2];
do
{
while (a[i]<x) {i++;};
while (x<a[j]) {j--;};
if (i<=j)
{
w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--;
}
}
while (i<=j);
cout<<"\n";
for (k=0; k<n; k++)
{
cout<<a[k]<<" ";
}
if (l<j) Sort(l,j,a,n); //рекурсивный вызов
if (i<r) Sort(i,r,a,n); //рекурсивный вызов
}
Шейкерная сортировка
Этот метод - результат улучшения известного нам алгоритма сортировки "пузырьком"
Ниже представлен пример его реализации:
void ShakerSort(int n, int *a)
{
int i,j,k,x,l,r,p;
l=1; r=n-1; p=0;
do
{
for (j=r; j>=l; j--)
if (a[j-1]>a[j])
{ x=a[j-1];
a[j-1]=a[j];
a[j]=x;
i=j;
}
p++;
l=i+1;
cout<<"\n"<<p<<" prochod"<<endl;
for (k=0; k<n; k++)
{
cout<<a[k]<<" ";
}
for (j=l; j<=r; j++)
if (a[j-1]>a[j])
{ x=a[j-1];
a[j-1]=a[j];
a[j]=x;
i=j;
}
r=i-1;
p++;
cout<<"\n"<<p<<" prochod"<<endl;
for (k=0; k<n; k++)
{
cout<<a[k]<<" ";
}
} while (l<=r);
}
Конец:)
Комментариев нет:
Отправить комментарий