Технологии Программирования. 6 лекция

Тема 5 СОРТИРОВКИ

Опр. Сортировка - упорядочение элементов множества в возрастающем или убывающем порядке.

С упорядоченными элементами проще работать, то есть легче найти необходимые элементы, исключить элемент, вставить элемент и т.д.

Алгоритмы сортировки можно разбить на следующие группы

Обычно сортируемые элементы множества называют записями и обозначают

A1 , A2 ,..., AN

1. Сортировки обменом

Опр. Сортировка обменом – метод, в котором элементы списка последовательно сравниваются между собой и меняются местами, если предшествующий элеме6нт больше последующего.

1.1. Стандартный обмен – метод «пузырька» - простой код и алгоритм

Рассмотри алгоритм сортировки массива по возрастанию в массиве из N= 4 – элементов

1)«Пробегаем» по массиву снизу вверх ( просматриваем элементы 3, 2,1,0), при этом каждый элемент массива сравниваем Ak , ( k = N −1,...,1 ) сравниваем с тем, что над ним Ak−1 , и если последний больше ( Ak −1 > Ak ), то меняем их местами

2)Операция 1) повторяется до тем пор, пока «наименьший» элемент не «всплывет» на самый верх.

3)Применяем данную процедуру 1) и 2) к подмассиву, то есть к элементам (3, 2,1)

4)Сортировка продолжается до тех пор пока все подмассивы не будут исчерпаны.

Компьютерная реализация size – размер массива (<N)

…

main()

{int A[100],size,k,n,temp,i;

//

cin>>size; for(k=0;k<size;k++) cin>>A[k];

for(k=0;k<size-1;k++) for(n=k+1;n<size;--n)

// обмен если A[k]>A[n]

If (A[k]>A[n]) {temp= A[k]; A[k]=A[n]; A[n]=temp;}

// печать отсортированного массива

….

}

1.2. Быстрая сортировка (Quicksort) – сортировка Хоара (1962)

Это эффективное развитие метода простого обмена. Метод основан на принципе «разделяй и властвуй».

Общая схема

1)из массива выбирается некоторый опорный элемент p.

2)Массив разделяется на два подмассива. Слева от p элементы меньшие либо равные p, справа – большие либо равные p.

3)Массив состоит из двух подможеств , причес левое подмножество меньше (либо равно) правому

4)Для обоих подмножеств, если в них число элементов более двух, выполняем ту же

процедуру. Например

Компьютерная реализация

…

int A[100];

void quicksort(long High, long Low)

{

long i,j;

short int p,temp;

i=Low; j=High; // копии нижней и верхней границы подмассива

p=A[(Low+High)/2]; // выбор опорного элемента

do{

while(A[i]<p) i++; // если истина, то указатель i передвигается на 1 элемент вправо while(A[j]>p) i++; // если истина, то указатель j передвигается на 1 элемент влево

if(i<=j) // указатели не пересеклись по позициям в массиве, меняем элементы i, j местами

{temp=A[i]; A[i]=A[j]; A[j]=temp; i++; j--;}

}while(i<=j)

// цикл продолжается до тех пор пока показатели не пересекутся по позициям в массиве

if(j>Low) quicksort(j,Low);

// запускаем сортировку для подмассива слева

if(i<High) quicksort(High,i);

// запускаем сортировку для подмассива справа

}

main()

{ int size,k;

//

cin>>size; for(k=0;k<size;k++) cin>>A[k];

quicksort(size-1,0); //size-1 - верхняя граница; 0 – нижняя граница

// печать отсортированного массива

….

}

Функция сложности метода ХоараO(N log2 N)

Задание. Переписать алгоритм быстрой сортировки для сортировки чисел по убыванию.

1.3. Сортировка методом Шелла.

Метод заключается в сравнении элементов массива, разделенных одинаковым расстоянием таким образом, чтобы элементы были упорядочены по расстоянию. Затем это расстояние делится пополам, и процесс повторяется, и т.д.

Компьютерная реализация сортировки массива по возрастанию

int A[100];

void Shell_sort(int A[], int N)

{

int temp, Middle, i , Change;

Middle =N/2; // находится номер центрального элемента массива do

{

do

{

Change=0; /* -признак, показывающий внесение изменений в массив.

if(A[i]>A[i+Middle]) {// меняем элементы массива местами

….. // написать самостоятельно

Change=1; // в массив внесены изменения

}

} while(Change); }while(Middle!=Middle/2);

}

мoid main()

{int A[100], i , size;

… // написать самостоятельно ввод размера массива и элементов массива

…// распечатать исходный массив

Shell_sort( A, size);

…// распечатать отсортированный массив

}

Комментарии

Переменной Middle присваивается значение центрального элемента подмассива, в начале =N/2, где N – количество элементов в массиве.

Далее определяем переменную Changе, отвечающую за изменения в массиве.

Если Changе=0, то на текущем шаге элементы массива не переставлялись, в противном случае Changе=1.

Пусть массив уже отсортирован do

{

do

{

Change=0;

Теперь с помощью цикла for(i=0;i<N-Middle;i++)

просматриваем все элементы массива от нулевого до N-Middle и проверяем, действительно ли массив отсортирован.

Если на некотором шаге, окажется, что

A[i]>A[i+Middle],

то меняем элементы местами и изменяем переменную Change=1,

это указывает на то, в массиве произошли изменения, поэтому сортировку необходимо запустить еще раз.

} while(Change); - проверяем и запускаем.

Алгоритм будет работать до тех пор, пока в массиве происходят перестановки и пока расстояние между элементами не станет равным 1.

}while(Middle!=Middle/2);

Сложность метода Шелла - O(0,3N(log2 N)2 )

Задание. Переписать алгоритм Шелла для сортировки чисел по убыванию

2. Сортировки выбором

(с выбором наименьшего или наибольшего элемента)

По сравнению с методом пузырька в выборочной сортировке сокращено число перестановок.

Как и при простом обмене, данный алгоритм просматривает подмассивы и находит наименьший элемент. Затем делает перестановку: наименьший элемент в начало подмассива, а на его место «первый» и т.д.

Программный код

void main()

{int A[100], i , size, start min, min_pos, temp.

… // написать самостоятельно ввод размера массива и элементов массива

start=0; // начальная левая граница подмассива

/* цикл повторений по перестановке элементов , пока все подмассивы не будут пройдены */

while(start!=size-1)

{

min=A[start]; // допустим, самый «первый» элемент подмассива наименьший min_pos=start; //запоминаем индекс наименьшего элемента

// поиск наименьшего элемента в массиве for(i=start;i<size;i++) if(A[i]<min) {min=A[i];min_pos=i;}

// переставляем элементы, если наименьший элемент не «первый» if(min_pos!=star){ temp=A[start];A[start]=A[min_pos]; A[min_pos]=temp;}

start++; // уменьшаем подмассив, смещая левую границу вправо

}

… // распечатать отсортированный массив

}

Сложность выборочной сортировки - O(N 2 )

Задание. Переписать алгоритм выбора для сортировки чисел по возрастанию с выбором наибольшего элемента

Задание. Переписать алгоритм выбора для сортировки чисел по убыванию с выбором наибольшего элемента

Задание. Переписать алгоритм выбора для сортировки чисел по убыванию с выбором наименьшего элемента

Вариант для теста

Вариант для теста с выбором наибольшего элемента

Заполнить таблицу до конца

3. Сортировка вставкой

В этом методе из неупорядоченной последовательности элементов выбирается поочередно каждый элемент, сравнивается с предыдущим, уже упорядоченным, и помещается на соответствующее место

Например, на приведенном ниже рисунке показана процедура сортировки вставкой. На каждом этапе кружком обведен анализируемый элемент, в рамку заключены упорядоченные части последовательности.

На каждом этапе кружком обведен анализируемый элемент, в рамку заключены упорядоченные части последовательности.

На первом этапе сравниваются два начальных элемента.

После сравнения 2-й элемент вставляется, сдвигая первый вправо на одну позицию.

На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее. Так как он больше предыдущих, он остается на месте. Вставки нет.

Процедура повторяется аналогично до тех пор, пока весь массив не будет упорядочен.

Задание. Написать программный код для сортировки вставкой

Сложность сортировки вставкой - O(N 2 )

Сравнение функций сложности

Чем правее на оси расположена функция сложности, тем менее эффективен алгоритм.

Задание* для самостоятельной работы