Сортировка методом Хоора (её ещё называют быстрой сортировкой) — это наиболее эффективный алгоритм внутренней сортировки. Его производительность зависит от выбора точки разбиения. При быстрой сортировке используется стратегия:
1. Массив разбивается на меньшие подмассивы.
2. Подмассивы сортируются.
3. Отсортированные подмассивы объединяются.
Быструю сортировку можно реализовать несколькими способами, но цель каждого подхода заключается в выборе элемента данных и помещении его в правильную позицию (этот элемент называется точкой разбиения), таким образом, чтобы все элементы слева от точки разбиения оказались меньше (или предшествовали) точки разбиения, а все элементы справа от точки разбиения оказались больше (или следовали за ней). Выбор точки разбиения и метод, используемый для разбиения массива, оказывают большое влияние на общую производительность реализации.
Рассмотрим один из вариантов реализации сортировки Хоора.
Пример 7.5
В самой процедуре сортировки сначала выберем средний элемент. Потом, используя переменные i и j, пройдемся по массиву, отыскивая в левой части элементы больше среднего, а в правой – меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше j. Тогда мы получим два подмножества, ограниченные с краев индексами l и r, а в середине – j и i. Если эти подмножества существуют (то есть i<r и j>l), то выполним их сортировку.
void Quicksort(int a[], int n, int left, int right)
{
int i=left, j=right; /*Инициализируем переменные левой и
правой границами подмассива*/
int test=a[(left+right)/2]; /*Выбираем в качестве
элемента разбиения средний элемент массива*/
do {
while (a[i] < test)
i++;
/*нашли элемент, больший элемента разбиения */
while (a[j] > test)
j--;
/*нашли элемент, меньший элемента разбиения */
if (i<=j) {
Swap(&a[i], &a[j);
i++; j--;
}
}
while(i <= j); /*рекурсивно вызываем алгоритм для
правого и левого подмассива*/
if (i<right)
QuickSort(a, n, i, right);
if (j>left)
QuickSort(a, n, left, j);
}
Анализ быстрой сортировки.
Быструю сортировку следует рассмотреть одной из первых при выборе метода внутренней сортировки. Этот алгоритм содержит сложную фазу разбиения и простую фазу слияния. В худшем случае выполненная работа эквивалентна работе при сортировке выбором. Производительность быстрой сортировки существенно зависит от выбора точки разбиения.
6. Шейкер сортировка
В этом методе учитывается тот факт, что от последней перестановки до конца массива будут находиться уже упорядоченные данные. Тогда просмотр
имеет смысл делать не до конца массива, а до последней перестановки на предыдущем просмотре. Если же просмотр делать попеременно в двух направлениях и фиксировать нижнюю и верхнюю границы неупорядоченной части, то получим шейкер-сортировку. Ниже приведен пример программы, использующей шейкер-сортировку элементов массива размерностью k.
void shaker(int *ms, int k)
{ register int i,a,b,c,d;
c=1;
b=k-1; //номер элемента на котором остановка
d=k-1; //номер стартового элемента для сортировки справа налево
do
{ for(i=d;i>=c;--i)
{ if (ms[i-1]>ms[i])
{ a=ms[i-1];
ms[i-1]=ms[i];
ms[i]=a;
b=i; // крайний слева упорядоченный элемент
}
}
c=b+1; //номер стартового элемента для сортировки слева направо
for(i=c;i<=d;++i)
{ if (ms[i-1]>ms[i])
{ a=ms[i-1];
ms[i-1]=ms[i];
ms[i]=a;
b=i; // крайний слева упорядоченный элемент
}
}
d=b-1;
} while(c<=d);
}
Алгоритмы поиска.
7.1. Последовательный поиск.
Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.
Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то
n Max{А} = max{ Si, i=1,n }; Avg{А} = Pi Si. i=1Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера.
Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.
Пример 7.1
Пусть во входном потоке задано 5 целых чисел К1,К2,... К5 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:
#include <stdio.h>
void main(void)
{
int k[5],v,i,count=0;
puts(“Vvedite elementi:”);
for (i=0;i<5;i++)
scanf(“%d”,&k[i]);
puts(“vvedite element dlja poiska”);
scanf(“%d”,&v);
i=0;
while(i<5)
{ if (k[i]==v)
{
printf(“element-%d position-%d\n”,v,(i+1));
count++;
}
i++;
}
if(count==0) printf(“element-%d ne naiden “,v);
}
7.2. Поиск элемента по индексу.
Пример 7.8
#include <stdio.h>
void main(void)
{
int k[5],v,i,count=0;
puts("Vvedite elementi:");
for (i=0;i<5;i++)
scanf("%d",&k[i]);
puts("vvedite element dlja poiska");
scanf("%d",&v);
i=0;
while(i<5)
{
if (k[i]==v)
{
printf("element-%d position-%d\n",v,(i+1));
count++;
}
i++;
}
if(count==0) printf("element-%d ne naiden ",v);
puts("Vvedite index elementa");
scanf("%d",&v);
if(v>=0&&v<5)
printf("element s indexom %d raven = %d\n",v,k[v]);
else printf("Elementa s takim indexom net\n");
}
Анализ линейного поиска.
Линейный поиск - это самый простой тип поиска, потому что при его выполнении просто просматривается множество элементов данных и эти элементы сравниваются с искомыми данными, пока не обнаружится совпадение. Линейный поиск прост в реализации, но не всегда эффективен.
7.3. Бинарный поиск.
Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.
Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.
Пример 7.4
#include <stdio.h>
void main()
{
int k[6],v,i,j,m;
for (i=0;i<6;i++)
scanf("%d",&k[i]);
scanf("%d",&v);
i=0; j=6; m=3;
while (k[m]!=v)
{
if (k[m] < v) i+=m;
else j=m-i;
m=(i+j)/2;
}
printf("%d %d",v,m);
}
Задания
На 4:
1. Отсортировать динамический массив в порядке убывания методом вставок
На 5-6:
1. Выполнить сортировку четных элементов методом пузырька.
2. Выполнить сортировку отрицательных элементов методом вставок.
3. Выполнить сортировку положительных элементов методом выбора.
4. Выполнить сортировку нечетных элементов методом Шелла.
На 7-8:
1. В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить).
2. В заданной последовательности все элементы, не равные нулю, расположить сохраняя их порядок следования, в начале последовательности, а нулевые элементы - в конце последовательности. Дополнительного массива не заводить.
3. Отсортировать массив по возрастанию, используя процедуру Swap, которая меняет местами 2 элемента.
4. Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем.
5. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный так же, как исходные массивы.
6. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный в обратную сторону.
7. Составьте алгоритм, упорядочивающий заданную последовательность чисел так, чтобы каждый элемент, стоящий на четном месте, был больше каждого из соседних.
8. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных значений, которые в первом массиве встречаются по два и более раза.
9. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных чисел, которые ни разу в первом массиве не встречаются и имеют величину больше минимального и меньше максимального из чисел первого массива.
10. Дана вещественная матрица размером 7x4. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент (один из них) оказался в левом верхнем углу.
11. В заданном целочисленном массиве найти элементы, сумма которых равна данному числу, в предположении, что такие числа существуют.
12. Дан массив А, состоящий из n элементов. Осуществить перестановку элементов массива на M элементов вправо.
13. В двумерном массиве поменяйте местами первую строчку, и строчку в которой находится первый нулевой элемент.
14. В двумерном массиве переставьте строки следующим образом: первую с последней, вторую с предпоследней и так далее. Если строк нечетное число, то средняя остается неизмененной.
15. Дан двумерный массив А. Расставить его столбцы в следующем порядке:
а) последний, предпоследний,..., второй, первый;
б) первый, последний, второй, предпоследний, третий,...
16. Дан двумерный массив. Начиная с первой строки, сдвинуть все строки на две вниз, а последние перенести на место первых двух строк.
17. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по убыванию элементов последней строки. Вычислить сумму элементов расположенных на диагоналях полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы.
18. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по возрастанию элементов первой строки. Вычислить среднее арифметическое элементов расположенных по периметру полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы.
19. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по возрастанию элементов 3-го столбца.
20. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по убыванию элементов 2-й строки.
На 9-10:
1. Выполнить сортировку строк матрицы (динамической) в порядке убывания/возрастания суммы элементов методом Хоора.