Лабораторная работа №9 (4 часа). Улучшенные методы сортировки
Цель работы:
- исследовать и изучить улучшенные методы сортировки на примерах метода Шелла и быстрой сортировки;
- овладеть навыками написания программ с использованием улучшенных методов сортировки на языке программирования С++.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к сортировкам методом Шелла и быстрой;
- ответить на контрольные вопросы и получить оценку по знанию теории;
- получить задание на выполнение конкретного варианта ЛР и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- составить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Все прямые методы сортировки фактически передвигают каждый элемент на всяком элементарном шаге на одну позицию. По этой причине они требуют порядка O(n2) таких шагов. Отсюда следует, что в основу любых улучшений должен быть положен принцип перемещения элементов на каждом шаге на возможно большие расстояния.
Метод Шелла.
Метод Шелла является улучшением метода сортировки с помощью прямого включения и основан на сортировке посредством включением с уменшающимися расстояниями. Сначала отдельно группируются и сортируются методом прямых включений элементы, отстоящие друг от друга на некотором расстоянии h1, затем на расстоянии h2 < h1 и так далее, последнее расстояние должно быть равно единице. Таким образом, если для сортировки будет использовано t расстояний, то ht = 1, hi+1< hi. Желетельно, чтобы расстояния обеспечивали бы взаимодействие различных цепочек как можно чаще.
Рассмотрим процесс сортировки последовательности из 8 целых чисел с начальным шагом h1 = 4, вторым шагом h2 = 2 и последним шагом h3 = 1.
Последовательность чисел: 44, 55, 12, 42, 94, 18, 6, 67.
На рисунке ниже представлена иллюстрация сортировки методом Шелла данной последовательности.
Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.
На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу.
Приводимый ниже в псевдокоде алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с условным переходом. Недостатком приведенного алгоритма является нарушение технологии структурного программирования, при которой нежелательно применять безусловные переходы. Если же внутренний цикл организовать как цикл while , то необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера. При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0..N ] до [-h1..N ], что усложнит написание программы.
Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, … то есть: hm=2hm-1+1, а количество шагов
t = (log 2 n ) - 1.
При такой организации алгоритма его эффективность имеет порядок O ( n1,2 )
Алгоритмы
Алгоритм сортировки Шелла (псевдокод):
Обозначим
h[1..t] - массив размеров шагов
a[1..n] - сортируемый массив
k - шаг сортировки
x - значение вставляемого элемента
const t = 3
h(1) = 7
h(2) = 3
h(3) = 1
for m = 1 to t
k = h(m)
for i = 1 + k to n
x = a(i)
for j = i - k to 1 step -k
if x < a(j) then
a( j+k) = a(j)
else goto L endif
next j
L: a(j+k) = x
next i
next m
return
Другим улучшенным методом сортировки является так называемая быстрая сортировка (QuickSort), которая считается сортировкой разделением и носит также назавание быстрая сортировка Хоара.
Quiсksort - метод быстрой сортировки
Быстрая сортировка является усовершенствованием метода, основанного на обмене. В основу данной сортировки положен метод разделения ключей по отношению к выбранному. Он заключается в следующем. Выбираем наугад какой-либо элемент x исходного массива. Будем проматривать массив слева до тех пор, пока не встретим ai > x, затем будем просматривать массив справа, пока не встретим aj < x. Поменяем местами эти два элемента и продолжим процесс просмотра до тех пор, пока оба просмотра не встретятся. В результате исходный массив окажется разбитым на две части, левая часть будет содержать элементы меньшие или равные x, а правая часть – элементы большие x. Применив эту процедуру разделения к левой и правой частям массива от точки встречи, получим четыре части и так далее, пока в каждой части окажется только один элемент. Остается решить вопрос, каким образом выбирать элемент x для разделения. Если при равновероятном распределении элементов массива в качестве разделения каждый раз выбирать медиану, то общее число сравнений будет n * log 2 n , а общее число обменов – (n * log 2 n)/6. При случайном выборе границы средние затраты увеличатся всего лишь в n * ln 2 раза. В крайне неблагоприятном случае, когда каждый раз для разделения выбирается наибольший обрабатываемый элемент массива, производительность процедуры будет наихудшая. Обычно в процедурах бысторой сортировки в качестве границы выбирают средний элемент, при этом получаются хорошие показатели производительности.
Нижеприведенный рисунок иллюстрирует процесс обменной сортировки
Слева от 6 располагают все ключи, которые меньше 6 , а справа - которые больше или равны 6.
В псевдокододе алгоритм быстрой сортировки следующий:
Sub Sort (L, R)
i = L
j = R
x = a((L + R) div 2)
repeat
while a(i) < x do
i = i + 1
endwhile
while a(j) > x do
j = j - 1
endwhile
if i <= j then
y = a(i)
a(i) = a(j)
a(j) = y
i = i + 1
j = j - 1
endif
until i > j
if L < j then
sort (L, j)
endif
if i < R then
sort (i, R)
endif
return
Sub QuickSort
Sort (1, n)
return
Из всех существующих методов сортировки QuickSort самый эффективный. Его эффективность имеет порядок
О (n log2 n) .
Контрольные вопросы по теории (сортировка с помощью дерева)
1. В чём заключается идея метода QuickSort?
- выбор 1,2,… n – го элемента для сравнения с остальными;
- разделение ключей по отношению к выбранному;
- обмен местами между соседними элементами.
2. В чем заключается суть метода Шелла?
- последовательное сравнение ключей;
- обмен местами между соседними элементами;
- cначала отдельно группируются и сортируются методом прямых включений элементы, отстоящие друг от друга на некотором расстоянии h1, затем на расстоянии h2 < h1 и так далее, последнее расстояние должно быть равно единице.
3. Усовершенствованием какого метода сортировки является быстрая сортировка?
- сортировки Шелла;
- сортировки методом прямого обмена;
- сортировки методом прямого выбора.
4. Какой метод сортировки является наиболее эффективным?
- быстрая сортировка;
- сортировка Шелла;
- пузырьковая сортировка.
Примеры алгоритмов конкретных задач
Рассмотрим теперь реализацию функций сортировки методом Шелла и быстрой сортировки на С++ и примеры сортировки конкретных числовых массивов.
/* *********************************************** */
/* СОРТИРОВКА МЕТОДОМ ШЕЛЛА */
#include <stdio.h>
#include <conio.h>
#define n 9
int A[n] ={5,6,2,4,9,8,3,1,7};
/* ============================================== */
main()
{ void Shell(int A[],int nn);
int j;
printf("\n Сортировка методом Шелла");
printf("\n Исходный массив: \n");
printf("\t");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n");
Shell(A,n);
printf("\n Отсортированный массив :\n");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n");
getch(); return 0;
}
/* ====================================== */
/* ФУНКЦИЯ СОРТИРОВКИ МЕТОДОМ ШЕЛЛА */
void Shell(int A[],int nn)
{ int i,j,k,x,ii;
k =( nn+1)/2;
while ( k >= 1 )
{
for ( i=k; i<nn; i++ )
{ if ( A[i-k] > A[i] )
{ x = A[i]; j = i-k;
M: A[j+k] = A[j];
if ( j>k )
{ if (A[j-k] > x )
{ j = j-k;
goto M;
}
}
A[j] = x;
/* printf(" \nk = %d x=%d: ",k,x);
for (ii=0; ii<nn; ii++)
printf(" %d ",A[ii]);*/
}
}
/* Отладочная печать */
printf(" \nk = %d ",k);
for (ii=0; ii<nn; ii++)
printf(" %d ",A[ii]);
if ( k>2 )
k = ( k +1)/2;
else
k = k /2;
}
}
/* ************************************************** */
/* *************************************************** */
/*БЫСТРАЯ СОРТИРОВКА ХОАРА*/
#include <stdio.h>
#include <conio.h>
#define n 15
int A[n] = {12,22,13,4,15,6,9,11,13,7,15,10,11,8,14,};
/* ========================================== */
main()
{ void QuickSort(int A[],int L,int R);
int j;
printf("\n Быстрая сортировка, рекурсивная функция");
printf("\n Исходный массив: \n\t\t");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n Нажмите любую клавишу для продолжения");
getch();
printf("\n Отладочная печать");
QuickSort ( A ,0, n -1);
printf ("\ n Отсортированный массив :\ n ");
for (j=0; j<n; j++)
printf("%d ",A[j]);
printf("\n");
getch(); return 0;
}
/* ============================================= */
/* ФУНКЦИЯ БЫСТРОЙ СОРТИРОВКИ QuickSort */
void QuickSort(int A[],int L,int R)
{ int i,j,k,x,m;
i = L; j = R;
x =A[(L+R)/2];
do
{
while ( A[i] < x )
i++;
while ( x < A[j] )
j--;
if (i <= j)
{ k = A[i]; A[i] = A[j]; A[j] = k;
i++; j--;
/* Отладочная печать */
printf("\n i=%d j=%d x=%d: ",i-1,j+1,x);
for (m=0; m<n; m++)
printf(" %d",A[m]);
}
}
while (i < j);
if (L < j)
{ printf("\t L=%d j=%d",L,j);
QuickSort(A,L,j);
}
if (i < R)
{ printf("\t i=%d R=%d",i,R);
QuickSort(A,i,R);
}
}
/* **************************************************** */
Задания
С использованием любого из улучшенных методов сортировки решить задачу согласно своему варианту.
1. Составить программу вывода на экран самого большого (самого малого) элемента массива А.
2. Составить программу сортировки массива А по убыванию величин его элементов.
3. В массиве А находятся элементы. Составить программу, которая сформирует массив В, в котором расположить элементы массива А в порядке убывания.
4. Дан упорядоченный массив А - числа, расположенные в порядке возрастания, и число а, которое необходимо вставить в массив А, так, чтобы упорядоченность массива сохранилась.
5. Составить программу для быстрой перестройки данного массива А, в котором элементы расположены в порядке возрастания, так, чтобы после перестройки эти же элементы оказались расположенными в порядке убывания.
6. Дан массив А, содержащий как отрицательные, так и положительные числа. Составить программу исключения из него всех отрицательных чисел, а оставшиеся положительные расположить в порядке их возрастания.
7. Составить программу, которая будет из массива А брать одно число за другим и формировать из них массив В, располагая числа в порядке возрастания.
8. Дан список авторов в форме массива А. Составить программу формирования указателя авторов в алфавитном порядке и вывести его на экран.
9. Имеется n абонентов телефонной станции. Составить программу, в которой формируется список по форме: номер телефона, фамилия (номера идут в порядке возрастания).
10. Имеется n слов различной длины, все они занесены в массив А. Составить программу упорядочения слов по возрастанию их длин.
11. Составить программу для сортировки массива А по возрастанию и убыванию модулей его элементов.
12. В отсортированный массив А. между каждой соседней парой элементов вставить число больше левого и меньше правого элемента в массиве и вывести полученный массив на экран.
Дата: 2019-12-10, просмотров: 301.
