22

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Демонстрационная программа сортировки методом Шелла

Реферат

Курсовая работа с., рис., прил., источника, таблицы.

СОРТИРОВКА, ШЕЛЛ, ДЕМОНСТРАЦИОННАЯ ПРОГРАММА

Цель работы - разработка программного, продукта, позволяющего иллюстрировать метод сортировки Шелла. Чтобы пользователь по результатам программы смог понять, как работает сортировка Шелла.

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

Данная курсовая работа выполнялась в компиляторе BorlanC++ Version 3.1 by Borland International, Inc.

Пояснительная записка выполнялась в текстовом редакторе Microsoft® Office Word 2007.

Введение

Существует множество алгоритмов сортировки данных. У простых алгоритмов сортировки, таких как сортировка вставками или сортировка пузырьком слишком велико количество производимых действий - О(n²). Сложные сортировки, такие как быстрая сортировка или сортировка слияниями этот недостаток компенсируют, имея гораздо меньшее количество производимых действий, но при этом довольно сложны в реализации.

Сортировка Шелла (англ. Shell sort) -- алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга.[1]

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

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

Задачи: реализовать ввод данных, проверяя их на корректность, адаптировать алгоритм для 2 способов вычисления длин промежутков, отсортировать массив, проиллюстрировать на экране алгоритм работы сортировки.

1. Описание метода решения задачи

Пусть дан массив a[] из 16 элементов, изображенный на рисунке 2.1.

Рисунок 2.1

1. Вначале сортируем методом пузырька каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]), рисунок 2.2

Рисунок 2.2

2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]), рисунок 2.3

Рисунок 2.3

В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.

3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]), рисунок 2.4

Рисунок 2.4

4. В конце сортируем пузырьком все 16 элементов, рисунок 2.5

Рисунок 2.5

Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам.

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

Единственной характеристикой сортировки Шелла является приращение или длинна промежутка, между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой пузырьком, но именно последовательность приращений определяет рост эффективности.

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

, 2ⁱ-1

где i такая последовательность шагов приводит к алгоритму класса O(N^{3 / 2})

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

2. Описание программы

Описание файла shellgoi.cpp

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

MAXN 41 - Максимальный размер массива плюс1

MAXM 100 - Максимальное значение элемента массива

MAXNAME 255 - Максимальная длинна файла.

MAXPOW 10 - максимальное количество необходимых приращений

MASSTR1 1 - размещение курсора в строке 1

MASSTR2 1 - размещение курсора в строке 1

MASCOL1 1 - размещение курсора в столбце 1

MASCOL2 3 - размещение курсора в столбце 3

MASPOSGL 28 - размещение курсора темы на строке 28

MASPOSTM 13 - размещение курсора темы на столбце 13

Глобальные переменные:

int n - количество элементов в массиве

long mas[MAXN] - сортируемый массив

int it - номер способа вычисления приращений

int shag - длина шага сортировки

int kolsrv - количество выполненных проверок

int kolper - количество выполненных перестановок

m - номер массива на расстояний шага

k - номер сортируемого массива

Ход выполнения программы:

Очищаем экран.

Выводим на экран описание алгоритма сортировки Шелла.

Вызываем процедуру vvod(), в которой вводим данные: n, mas[], it. И осуществляем проверку данных на корректность. Если данные не корректны, то просим ввести их повторно. Для проверки данных на корректность используется функция int chislo(char*), которая проверяет передаваемую строку. Если в ней лежат все цифры и/или знаки `-' и `+' то возвращаем число, которое лежит в этой строке. Если строка не проходит это условие, то возвращаем некорректное значение -1.

Вызываем процедуру shag(int) определяем шаг сортировки

Выводим сортируемый массив на экран при помощи процедуры outmas()

Начинаем сортировку.

Запускаем процедуру sshell() и сортируем массив

По ходу работы сортировки выводим на экран этапы сортировки для обеспечения наглядности. Для этого используются процедуры outmas()

После сортировки запускаем процедуру out(), которая выводит на экран результаты работы программы - отсортированный массив, количество проверок и количество перестановок.

Текст программы предоставлен в приложении А.

Блок-схема программы предоставлена в приложений Б.

3. Описание методики тестирования программы

Программа была протестирована на различных массивах и с 2мя видами приращений.

Были проверены возможные случаи аварийного завершения программы, проверка корректности ввода данных, для чего в исходные данные вводилась ошибка: буква, числа, сильно превышающее границы ввода.

Результаты работы программы предоставлены в таблице 4.1 (под результатами понимается отсортированный массив, количество сравнений и перестановок)

Таблица 4.1 Обобщенные примеры работы программы.

Входные данные (n, mas[], it)	Результат
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1	1 2 3 4 5 6 7 8 9 10 11 12 13 14 Kolichesto sravnenij: 40 kolichestvo perestanovok: 0
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2	1 2 3 4 5 6 7 8 9 10 11 12 13 14 Kolichesto sravnenij: 31 kolichestvo perestanovok: 0

Дан массив mas[] с размером n=14.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Сортируем по формуле .

Длина промежутка равен 9 так как n=14. Количество сравнений в первом проходе 5.

Длина промежутка равен 4, количество сравнений во втором проходе 10.

Длина промежутка равен 2, количество сравнений в третьем проходе равен 12.

И последняя длина промежутка равен 1. Сортируем пузырьком все 14 элементов. Количество сравнений будет 13.

Общее количество сравнений равен 40, что подтверждает правильность сортировки Шелла.

4. Руководство пользователя по работе с программой

4.1 Установка программы

Копировать папку проекта в любую директорию с возможностью записи файлов (Пример: Рабочий стол). Папка должна содержать 1 файл : shellgoi.exe и 1 папку: include в котором содержатся константы и функция chislo(char*)

4.2 Запуск программы

Запустить исполняющий файл shellgoi.exe, главное окно на рисунке 5.1

Рисунок 5.1

4.3. Предоставляется выбор ввода данных: с клавиатуры, случайно и с файла, рисунок 5.2

Рисунок 5.2

4.4 Выбор с клавиатуры

Рисунок 5.3

Следовать указаниям, появляющимся на экране.

4.5 Выбор ввода случайно

Рисунок 5.4

Выбираем количество элементов массива и максимальное значение

4.6 Ввод данных из файла

Рисунок 5.5

Необходимо ввести имя файла. Имя файла должно содержать не более 255 символов (включая путь), должно содержать только латинские буквы, не должно содержать пробелов.

Файл должен содержать информацию в следующем виде.

Таблица 5.5 - Пример оформления входного файла.

Input.txt
N A1 A2 … Аn IT

Где N - количество элементов в массиве (1<=N<=40), A_i - элемент массива (0<=А_i<=100), IT - номер способа вычисления приращений (1<=IT<=2)

При IT =1

где i такая последовательность шагов приводит к алгоритму класса O(N^{3 / 2})

При IT=2

2ⁱ-1 где i такая последовательность шагов приводит к алгоритму класса O(N^{3 / 2})

Примечание

Программа тестировалась и корректно работает в ОС Windows XP SP3.

Заключение

алгоритм программа шелл сортировка

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

Данный продукт можно использовать в учебном процессе для наглядной иллюстрации алгоритма сортировки методом Шелла

Список использованных источников

1. Д. Кнут. Искусство программирования. Том 3. Сортировка и поиск, 2-е изд. Гл.5.2.1

2. Уинер "Язык Турбо-СИ" (1991г)

3. Дубинин Д.В. Информатика: Методические указания по выполнению курсовой работы - 2011. 34 с.

Приложение (обязательное)

Файл shellgoi.cpp

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include"CONSTANT.cpp" //constanty

#include"CHISLO.cpp" //funkcia chislo

long mas[MAXN];

int n=MAXN, it,s,m,shag=0,k,kolsrv=0,kolper=0;

void vvod(),outmas(int,int),out(),outgroup(int),sshell();

int shagi(int x),chislo(char*);

void main()

{ clrscr();

gotoxy(MASPOSGL,MASPOSTM);

cprintf("SORTIROVKA METODOM SHELLA");getch();

clrscr();

printf("Sortirovka Shella - algoritm sortirovki, yavlyaiuwieisya usovershenstvovannym\nvariantom sortirovki vstavkami.Ideya metoda Shella sostoit v sravnenii elementov stoyashih ne tolko ryadom, no i na opredellennom rastoyanii drug ot druga\nA seychas\n");

int i;

vvod(); //funkcia vvoda

shag=shagi(shag); //opredelyaet wag sortirovki

clrscr();

outmas(MASSTR1,MASCOL1); getch(); //vyvod massiva na ekran

sshell(); //sortirovka metodom shella s demonstraciei

out(); //vyvod rezultata

}

void sshell() //funkcia sortirovki Shella

{int tmp,k=0;

while (shag>0)

{

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

{gotoxy(MASSTR2,MASCOL2);

textcolor(WHITE);

cprintf("dlina promejutka %d\n",shag);

k=i-shag;

m=k+shag;

getch();

while (k>=0)

{outmas(MASSTR1,MASCOL1); //vyvod massiva

kolsrv++;

if (mas[k]>mas[k+shag])

{

tmp=mas[k]; mas[k]=mas[k+shag]; mas[k+shag]=tmp;

kolper++; k=k-shag;

}

else k=-1;

}

} shag=shag/2;

}

}

int truecolor(int h,int first,int numb) //funkcia vybora cveta chisla

{

if((numb-first)%h==0)

{return 1;}

else return 0;

}

void out() //vyvod rezultata

{

textcolor(WHITE);

cprintf("\n\n\nMassiv osortirovan!\r\n");

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

printf("%ld ",mas[q]);

printf("\n");getch();

printf("\nKolichesto sravnenij: %d\n",kolsrv);

printf("kolichestvo perestanovok: %d\n",kolper);

printf("\nPress any key for exit.");

getch();

}

int prob(char *s, char c) //funkcia opredelenia probela

{

int i,res=-1,delenie;

delenie=strlen(s);

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

if(s[i]==c)

{

res=i;

break;

}

return res;

}

void del (char *s, int g) //udalenie stroki

{

int i,dl;

dl=strlen(s);

for(i=0;i<dl-g;i++)

{

s[i]=s[i+g+1];

}

}

void rec(char *s_sour,char *s_dest,int g) //zapis v massiv

{int i;

// char s_dest[MAX][MAX];

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

{

s_dest[i]=s_sour[i];

}

s_dest[i]=0;

}

void outmas(int s,int c) //vyvod massiva

{int e,q;

textcolor(WHITE);

gotoxy(s,c);

cprintf("Sortiruemyi massiv\r\n");

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

{

if(truecolor(shag,e,m)) //opredelenie cveta dlya dannogo i-togo massiva

{textcolor(LIGHTRED);

cprintf("%d ",mas[e]);

textcolor(WHITE);

}

else

cprintf("%d ",mas[e]);

}

cprintf("\n\n\r");

}

int shagi(int shag)//orpedelenie shaga sortirovki

{

int str1[MAXPOW]={1,2,5,9,17,33,64};

int str2[MAXPOW]={0,1,3,7,15,31,63};

int q,i,prir[MAXPOW];

{

for(q=0;str1[q]<n;q++)

if(it==1)

{if(str1[q]<=n);

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

prir[i]=str1[i];

}

else

{if(str2[q]<=n);

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

prir[i]=str2[i];}

{ s=q-1;

shag=prir[s];

}

}

return shag;

}

void vvod() //funcia vvoda

{

char num[MAXNAME],max[MAXM];

char name[MAXNAME];

printf("Viberite sposob vvoda dannih:\n1. S klaviaturi;\n2. Sluchajno;\n3. Iz fajla;\n");

int sposob=0;

while(!(1<=sposob&&sposob<=3))

{

scanf("%s",&num);

sposob=chislo(num);

if(sposob==1)

{printf("vvedite kolichestvo elementov massiva 1<=n<=40: ");

while(!(0<n&&n<MAXN))

{scanf("%s",&num);

n=chislo(num);

if(!(0<n&&n<MAXN))

printf("n - nekorrektno. Vvedite n povtorno: ");

}

printf("vvedite elementi massiva 0<=mas[i]<=99:\n");

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

{mas[q]=-1;

while(!(0<mas[q]&&mas[q]<MAXM))

{printf("mas[%d]= ",q);

scanf("%s",&num);

mas[q]=chislo(num);

if(!(0<mas[q]&&mas[q]<MAXM))

printf("%dij element nekorrekten. Vvedite povtorno\n",q);

}

}

printf("\nViberite sposob vichisleniya dlinni promezhutka:\n1. 2^i+1\n2. 2^i-1\n");

it=0;

while(!(1<=it&&it<=2))

{scanf("%s",&num);

it=chislo(num);

if(!(1<=it&&it<=2))

printf("Vi vveli nekorretnoe znachenie. Vvedite nomer sposoba povtorno.");

}

}

if(sposob==2)

{

int max,min=0,flag;

printf("vvedite kolichestvo elementov massiva 1<=n<=40: ");

while(!(0<n&&n<MAXN))

{scanf("%s",&num);

n=chislo(num);

if(!(0<n&&n<MAXN))

printf("n - nekorrektno. Vvedite n povtorno: ");

}

{do

{flag=0;

printf("vvedite max znachenie chisel(max<=99) ");

scanf("%d",&max);//randomize();

{if(max>99)

flag=1;

printf("vy vveli nekorektnoe chislo. vvedite povtorno \n");

}

}while(flag!=0);

}

srand(time(NULL));

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

{

mas[q]=(rand()%(max-min)+min);

printf("%ld ",mas[q]);

}

printf("\nViberite sposob vichisleniya dlinni promezhutka:\n1. 2^i+1\n2. 2^i-1\n");

while(!(1<=it&&it<=2))

{scanf("%s",&num);

it=chislo(num);

if(!(1<=it&&it<=2))

printf("\nVi vveli nekorretnoe znachenie. Vvedite nomer sposoba povtorno.");

}

}

if(sposob==3)

{char *str,s=' ',c[MAXM][MAXM];

int m,l,k,j,i,flag=1;

FILE *file;

while(flag!=0)

{flag=0; k=0;

printf("vvedite imya faila ili put k failu ");

scanf("%s",&name);

file=fopen(name,"r");

fgets(str,MAXN,file);

n=atoi(str);

{if(!(0<n&&n<MAXN)) flag=1;}

fgets(str,MAXM,file);

do

{

m=prob(str,s);

if(m!=-1)

{

rec(str,c[k],m);

del(str,m);

k++;

}

else

{

rec(str,c[k],strlen(str)+1);

k++;

}

}

while(m!=-1);

rec(str,c[k],m);

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

{

mas[i]=chislo(c[i]);

{if(!(0<mas[i]&&mas[i]<MAXM)) flag=1;}

}

it=chislo(c[i]);

{if(!(1<=it&&it<=2)) flag=1; }

{if(flag==1)

printf("Vvedeno nevernoe imja fajla ili dannie v fajle ne korrektni. Vvedite imja fajla povtorno.\n");}

fclose(file);

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

{for(int j=i;j<n;j++)

c[i][j]=0;

}

}

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

printf("%ld ",mas[i]);

printf("\n");

}

if(!(1<=sposob&&sposob<=3))

printf("Vvedeno nekorrektnoe znachenie. Vvedite nomer sposoba povtorno.\n");

}

}

Блок схема программы

На рисунке 6.1 изображена блок схема программы

Рисунок 6.1

Размещено на Allbest.ru