Методы и алгоритмы сортировки

Лабораторная работа № 14

Любой программист сталкивался с необходимостью рассортировать данные, то есть упорядочить их определённым образом. Сортировка применяется во многих, если не во всех, областях программистской деятельности, будь то базы данных или математические программы. Цель сортировки облегчить в дальнейшем поиск требуемых данных. Многие программисты пользуются специально предназначенными для сортировки библиотечными функциями (например, qsort() в Турбо Си), особо не задумываясь над тем, а как же на самом деле работают эти функции. В действительности существует много методов сортировки данных. Причём для разных типов данных иногда целесообразно применять разные методы сортировки.

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение двух элементов, определяющее упорядоченность этой пары;

- перестановку, меняющую местами неупорядоченную пару элементов;

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

Сортировка данных в оперативной памяти называется внутренней, а сортировка данных в файлах называется внешней. Ниже будут рассматриваться методы сортировки данных в оперативной памяти.

Метод пузырька или сортировка простым обменом. Этот метод называют также обменной сортировкой выбором. Нетрудно догадаться, что идея этого метода отражена в его названии. Самые "лёгкие" элементы массива всплывают "наверх", самые "тяжёлые" - тонут. Алгоритмически это можно организовать следующим образом. Мы будем просматривать весь массив "сверху вниз" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем вниз самый "тяжёлый" элемент всего массива. Теперь повторим операцию для оставшихся n-1 элементов, то есть для тех, которые лежат "выше" найденного.

/* Функция сортировки простым обменом (методом пузырька) */

void sort_bubl(int *x, int n)

{

int i,j,buf;

/* Проход массива 'вниз', начиная с нулевого элемента */

for(i=0;i<n;i++)

/*Проход массива 'вниз', начиная с нулевого

и до n-i-го элемента */

for(j=0;j<n-i-1;j++)

/* Сравнение двух соседних элементов и их обмен */

if(*(x+j)>*(x+j+1))

{buf=*(x+j); *(x+j)= *(x+j+1); *(x+j+1)=buf;}

}

Сортировка методом пузырька является самой простой и в то же время самой неэффективной, так как перестановка одного и того же элемента несколько раз (особенно крупных объектов) требует много времени особенно для больших массивов информации.

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

/* Функция сортировки выбором наименьшего элемента */

void sort_min (int *x, int n) {

int i,j,k,buf;

/*Проход массива, начиная с нулевого элемента

до предпоследнего */

for(i=0;i<n-1;i++) {

/* Проход массива, начиная (i+1)-го

до последнего элемента */

for(k=i, j=i+1; j<n; j++)

// Поиск наименьшего k-го элемента

if(*(x+j)< *(x+k)) k=j;

// Перемещение наименьшего элемента вверх

buf=*(x+k); (x+k)=*(x+i); *(x+i)=buf;

}

}

Данные методы сортировки являются неэффективными и редко применяются в «серьезных» программах, но они полезны для иллюстрации принципов сортирования данных и получения практических навыков работы с циклами. В программах, где требуется высокая производительность работы сортировок, применяются другие методы такие как метод Шелла, метод Хора.

Метод Шелла. Метод был предложен автором Donald Lewis Shell в 1959г. Основная идея алгоритма состоит в том, что на начальном этапе реализуется сравнивание и, если требуется, перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализуем метод Шелла следующим образом. Начальный шаг сортировки примем равным n/2, т.е. 1/2 от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на gap элементов. Проход с тем же шагом повторяется, если элементы переставлялись. Следует отметить, что после каждого этапа сортировки отстоящие на gap элементы являются отсортироваными.

Пример. Рассортировать массив чисел:

41, 53, 11, 37, 79, 19, 7, 61.

Процесс сортировки выглядит следующим образом:

								Исходный массив
								(0,4), (1,5)	1-ый цикл
								(2,6), (3,7)
								(0,2),(1,3),(2,4),(3,5),(4,6),(5,7)	2-ой цикл
								(0,2),(1,3),(2,4),(3,5),(4,6),(5,7)
								сравнивались соседние (3-ий цикл).

В строке после массива в круглых скобках указаны индексы сравниваемых элементов и указан номер внешнего цикла.

Функция реализации сортировки методом Шелла имеет вид:

/* Функция сортировки методом Шелла */

void sort_sh(int *x, int n)

{

int i, j; // две переменные цикла

int buffer; // используется при перестановке

int gap; // шаг сортировки

int sorted; // флаг окончания этапа сортировки

for(gap = n/2; gap > 0; gap /= 2) // начало сортировки

Do

{

sorted = 0;

for(i = 0, j = gap; j < n; i++, j++)

if(*(x+i) > *(x+j)) // сравниваем отстоящие на gap элементы

{ // переставляем элементы

buff = *(x+j); *(x+j) = *(x+i); *(x+i) = buff;

sorted = 1; // была перестановка , сортировка не завершена

}

} while (sorted); // окончание этапа сортировки

}

void main()

{

int x[]={2,5,9,1,4,3,8,7,6,0};

sort_sh(x,10);

}

Метод Хоара. Метод Хоара (Charles Antony Richard Hoare, 1962 г.), называемый также методом быстрой сортировки (QuickSort) основывается на следующем: находится такой элемент, который разбивает множество на два подмножества так, что в одном все элементы больше, а в другом - меньше элемента делящего множество на два подмножества. Каждое из подмножеств также разделяется на два, по такому же принципу. Конечным итогом такого разделения станет рассортированное множество. Рассмотрим один из вариантов реализации сортировки Хоара.

В самой процедуре сортировки сначала выберем средний элемент. Потом, используя переменные i и j, пройдемся по массиву, отыскивая в левой части элементы больше среднего, а в правой - меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше j. Тогда мы получим два подмножества, ограниченные с краев индексами l и r, а в середине - j и i. Если эти подмножества существуют (то есть i<r и j>l), то выполняем их сортировку.

Например, необходимо рассортировать массив: 13,3,23,19,7,53,29,17. Переставляемые элементы будем подчёркивать, средний - выделим жирным шрифтом, а элемент попавший на своё место и не участвующий в последующих сравнениях - курсивом. Индекс i будет задавать номер элемента слева от среднего, а jсправа от среднего. Тогда получим:

13 3 23 19 7 53 29 17

13 3 17 19 7 53 29 23

13 3 17 7 19 53 29 23 — делим на два подмножества

13 3 17 7 19 53 29 23

Выделяем подмножество 3 13 17 7 19 23 29 53

13 17 7

Выделяем подмножество 13 7 17

Результат: 3 7 13 17 19 23 29 53

Фрагмент программа реализации сортировки методом Хоара имеет вид:

void main()

{

void Hoare(int *, int , int ); // прототип функции

int x[10] = {7,2,4,0,3,1,9,6,8,5}; // исходный массив

int n=10;

// ...операции...

Hoare(x,0,n-1); // вызываем рекурсивный алгоритм

/* массив рассортирован */

// ...операции...

}

/* процедура сортировки */

void Hoare(int *x, int l, int r) // передаем левую/правую границы

{

int i, j; // две «передвижные» границы

int buffer; // используется при перестановке

int sr = x[(l+r)/2]; // средний элемент

i = 1;

j = r; // устанавливаем начальные значения

Do

{

while(x[i] < sr) i++; // ищем слева элемент больше среднего

while(x[j] > sr) j--; // ищем справа элемент меньше среднего

if(i <= j) // если левая граница не прошла за правую

{ // перестановка элементов

buff = x[i]; x[i] = x[j]; x[j] = buff;

i++; j--; // переходим к следующим элементам

}

} while(i <= j); // пока границы не сошлись

// массив разбит на два подмножества

if(i < r) // если есть что-нибудь справа

Hoare(x,i,r); // сортируем правую часть

if(j>l) // если есть что-нибудь слева

Hoare(x,l,j); // сортируем левую часть

}

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

Пример формирования массива случайным образом:

srand((unsigned)time(NULL));

for(i=0;i<n; i++)

{

a[i] = rand()%10;

}

Задание: Написать программу, которая сортирует массив одним из способов. Способ выбирается из меню:

1) Сортировка Шелла.

2) Сортировка методом "пузырька"

3) Сортировка Хоара

4) Сортировка выбором наименьшего элемента.

.

*Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.

#include <iostream>

using namespace std;

int array[100];

void Sort(int col)

{

int trash=0;

int f=1;

for (int i=1; (i<=col) && (f=1) ; i++)

{

f=-1;

// проходим с лева на право

for (int j=i; j<=col-i; j++)

{

// если число слева больше числа

if (array [j]>array [j+1])

{

// справа, то меняем местами

trash=array[j];

// справа собираются большие числа

array [j]=array [j+1];

array [j+1]=trash;

f=1;

}

}

// проходим с права на лево

for (int j=col-i-1; j>i ; j--)

{

// если число справа меньше числа

if (array [j]<array[j-1])

{

// слева, то меняем местами

trash=array[j];

// слева собираются меньшие числа

array [j]=array [j-1];

array [j-1]=trash;

f=1;

}

}

}

}

// вывод

void Out(int col)

{

for (int i=1; i<=col; i++)

cout << array [i] <<" ";

cout << endl;

}

// главная

int main()

{

int col_el;

// ввод данных

cout << " Enter length of array"<< endl;

cin >> col_el;

cout << " Enter array elements"<<endl;

for (int n=1; n<=col_el ; n++)

{

cout <<n<<" :" << "\t";

cin >> array[n];

}

// сортировка

Sort(col_el);

// вывод результата

cout << "Result is :"<<endl;

Out(col_el);

cin >> col_el;

return 0;

}

void swap(int* x, int i, int j) {

int tmp;

tmp = x[i]; x[i] = x[j]; x[j] = tmp;

}

void ShakerSort(int* x) {

int last = n-1;

int left = 1, right = n-1;

/* основной цикл до тех пор пока границы

отсортированных с разных сторон отрезков

не пересекутся */

do {

/* проход снизу вверх */

for (int j = right; j > 0; j--) {

if (x[j-1] > x[j]) {

swap(x, j-1, j);

last = j;

}

}

/* Корректируем нижнюю границу

до которой уже все элементы получились

отсортироваными */

left = last + 1;

/* проход сверху вниз */

for (int j = 1; j <= right; j++) {

if (x[j-1] > x[j]) {

swap(x, j-1, j);

last = j;

}

}

/* Корректируем верхнюю границу

после которой уже все элементы получились

отсортироваными */

right = last - 1;

} while (left < right);

}

#include"stdafx.h"

#include<conio.h>

#include<stdio.h>

void Out (int col_el);

void ShakerSort(int* x, int n);

void swap(int*, int, int);

int x[100];

int main()

{

int n;

// ввод данных

puts(" Enter length of array");

scanf("%d", &n);

puts("input array :");

for (int i=1; i<=n ; i++)

{

scanf("%d", &x[i]);

}

// сортировка

ShakerSort(x, n);

// вывод результата

puts("rezult is :");

Out(n);

}

void swap(int* x, int i, int j)

{

int tmp;

tmp = x[i];

x[i] = x[j];

x[j] = tmp;

}

void ShakerSort(int* x, int n) {

int last = n-1;

int left = 1, right = n-1;

/* основной цикл до тех пор пока границы

отсортированных с разных сторон отрезков

не пересекутся */

do {

/* проход снизу вверх */

for (int j = right; j > 0; j--) {

if (x[j-1] > x[j]) {

swap(x, j-1, j);

last = j;

}

}

/* Корректируем нижнюю границу

до которой уже все элементы получились

отсортироваными */

left = last + 1;

/* проход сверху вниз */

for (int j = 1; j <= right; j++) {

if (x[j-1] > x[j]) {

swap(x, j-1, j);

last = j;

}

}

/* Корректируем верхнюю границу

после которой уже все элементы получились

отсортироваными */

right = last - 1;

} while (left < right);

}

void Out(int n)

{

for (int i=1; i<=n; i++)

printf("%d ", x[i]);

getch();

}

#include "stdafx.h"

#include <conio.h>

#include <iostream>

int menu(void);

void sort_shel(int *, int );

void ShakerSort(int* , int );

void BubbleSort(int *, int );

void MinSort(int *,int );

void HoorSort(int *x,int n,int l,int r);

int x[100], i;

int main()

{

int n,l, r;

while(1)

{

switch (menu())

{

case 1: sort_shel(x,n); break;

case 2: BubbleSort(x,n); break;

case 3: puts("Vvedite dliny massiva :");

scanf("%d", &n);

for(int i=0;i<n; i++)

{

scanf("%d", &x[i]);

}

printf("Ishodnyi massiv :\n");

for(int i=0;i<n; i++)

{

printf("%d ", x[i]);

}

HoorSort(x,n,0,n-1);

break;

case 4: MinSort(x,n); break;

case 5: ShakerSort(x,n); break;

case 7:return 0;

default:printf("Neverniy vibor\n");

}

}

getch();

}

int menu()

{

int choice;

do

{

printf("\nMenu :\n");

printf("1.Metod Shela\n");

printf("2.Sortirovka puzyr'kom\n");

printf("3.Metod Hoara\n");

printf("4.Sortirovka vyborom naimen'shego elementa\n");

printf("5.Zadanije\n");

printf("7.end\n");

printf("Vash vibor?\n");

scanf("%d", &choice);

system("cls");

}

while (choice > 7);

return choice;

}

void sort_shel(int *x, int n)

{

int i, j; // две переменные цикла

int buffer; // используется при перестановке

int gap; // шаг сортировки

int sorted;

puts("Vvedite dliny massiva :");

scanf("%d", &n);

for(int i=0;i<n; i++)

{

scanf("%d", &x[i]);

}

printf("Ishodnyi massiv :\n");

for(int i=0;i<n; i++)

{

printf("%d ", x[i]);

}

printf("\n");// флаг окончания этапа сортировки

for(gap = n/2; gap > 0; gap /= 2) // начало сортировки

do

{

sorted = 0;

for(i = 0, j = gap; j < n; i++, j++)

if(*(x+i) > *(x+j)) // сравниваем отстоящие на gap элементы

{ // переставляем элементы

buffer = *(x+j);

*(x+j) = *(x+i);

*(x+i) = buffer;

sorted = 1; // была перестановка , сортировка не завершена

}

}

while (sorted); // окончание этапа сортировки

puts("Massiv, otsortirovannyi metodom Shella :");

for(i=0; i<n; i++)

{

printf("%d ", x[i]);

}

}

void HoorSort(int *x,int n,int l,int r)

{

int srednii=x[(l+r)/2];

int i=l;

int j=r, t;

do

{ while(x[i]<srednii)

i++;

while(x[j]>srednii)

j--;

if(i<=j)

{

t=x[i];

x[i]=x[j];

x[j]=t;

i++;

j--;

}

}

while(i<=j);

if(i<r)

HoorSort(x,n,i,r);

if(j>l)

HoorSort(x,n,l,j);

}

void ShakerSort(int* x, int n)

{

int last = n-1, t;

int left = 1, right = n-1;

puts("Vvedite dliny massiva :");

scanf("%d", &n);

for(int i=0;i<n; i++)

{

scanf("%d", &x[i]);

}

printf("Ishodnyi massiv :\n");

for(int i=0;i<n; i++)

{

printf("%d ", x[i]);

}

do {

/* проход снизу вверх */

for (int j = right; j > 0; j--) {

if (*(x+j-1) > *(x+j))

{

t=*(x+j);

*(x+j)=*(x+j-1);

*(x+j-1)=t;

last = j;

}

}

/* Корректируем нижнюю границу

до которой уже все элементы получились

отсортироваными */

left = last + 1;

/* проход сверху вниз */

for (int j = 1; j <= right; j++) {

if (*(x+j-1) > *(x+j)) {

t=*(x+j);

*(x+j)=*(x+j-1);

*(x+j-1)=t;

last = j;

}

}

/* Корректируем верхнюю границу

после которой уже все элементы получились

отсортироваными */

right = last - 1;

} while (left < right);

for(i=0; i<=last; i++)

{

printf("%d ", x[i]);

}

}

void BubbleSort(int *x,int n)

{

int i, j, t;

puts("Vvedite dliny massiva :");

scanf("%d", &n);

for(int i=0;i<n; i++)

{

scanf("%d", &x[i]);

}

printf("Ishodnyi massiv :\n");

for(int i=0;i<n; i++)

{

printf("%d ", x[i]);

}

printf("\n");

for (i=0; i<n; i++)

for (j=n-1; j>i; j--)

if (*(x+j-1)>*(x+j))

{

t=*(x+j);

*(x+j)=*(x+j-1);

*(x+j-1)=t;

}

for(i=0; i<n; i++)

{

printf("%d ", x[i]);

}

}

void MinSort(int *x,int n)

{

int i,j,min, t;

puts("Vvedite dliny massiva :");

scanf("%d", &n);

for(int i=0;i<n; i++)

{

scanf("%d", &x[i]);

}

printf("Ishodnyi massiv :\n");

for(int i=0;i<n; i++)

{

printf("%d ", x[i]);

}

printf("\n");

for(i=0;i<n-1;i++)

{

min=x[i];

for(j=i+1;j<n;j++)

if(x[j]<min)

{

min=x[j];

t=x[j];

x[j]=x[i];

x[i]=t;

}

}

for(i=0; i<n; i++)

{

printf("%d ", x[i]);

}

}