Демонстрационная программа сортировки «быстрым» методом

 

Министерство образования Российской Федерации

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И  РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

Кафедра радиоэлектроники и защиты информации (РЗИ)

 

 

 

 

 

Курсовая работа на тему

«Демонстрационная программа сортировки «быстрым» методом»

 

 

 

Выполнил:

Студент группы 1А2

______Тихонов В.А.

«__»__________2013

Проверил:

Аспирант кафедры  РЗИ 

______Чечулин С.О.

«__»__________2013

 

 

Томск 2013 

Реферат

Курсовая работа 20 страниц, 3 рисунка, 4 источника, 2 приложения.

Демонстрационная программа сортировки «быстрым» методом.

1. Объектом разработки является демонстрационная программа сортировки «быстрым» методом.
2. Целью работы является разработка программы, сортирующей массив целых чисел. Также сортировка пошагово представлена на экране, для наглядной демонстрации сортировки «быстрым» методом.
3. В результате был разработан программный продукт, который может быть использован в учебных целях для демонстрации сортировки «быстрым» методом.

4. Достигнутые технико-эксплуатационные характеристики: устойчивость продукта к некорректным действиям.

5. Данный программный продукт может быть модифицирован и видоизменен для решения каких-либо более специфических задач данного направления.
6. Данная работа выполнена в текстовом редакторе Microsoft Word 2010. Программа написана в компиляторе Dev-C++.

 

 

                                                       Оглавление

 

1.Цель работы 5

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

3.Описания программы и используемых алгоритмов 7

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

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

7.Заключение 10

8.Список используемой литературы. 11

Приложение А 12

Приложение Б 20

 

 

 

1.Цель работы

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

Составить алгоритм решения задачи. Отобразить на экране в пошаговом  и автоматическом режиме сортировку данных «быстрым методом». Вывести  значения числа сравнений и числа  перестановок.

 

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

«Основная идея, на которой базируется этот метод состоит в том, чтобы  взять одну из записей, скажем R₁ и передвинуть ее на то место, которое она должна занять после сортировки» скажем в позицию s. В поиске этой окончательной позиции придется несколько перекомпоновать и остальные записи таким образом,  чтобы слева от позиции s не оказалось ни одной записи с большим ключом, а справа — с меньшим. В результате последовательность окажется разбитой таким образом, что исходная задача сортировки всего массива записей будет сведена к задачам независимой сортировки пары подмассивов R₁...R_S-1 и  R_S+1…R_n меньшей длины. Далее, тот же метод применяется и к полученным подмассивам до тех пор, пока не будет завершена сортировка всей последовательности.

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

Итак, выбираем опорный элемент  R₁ и указатели i  и j  причем вначале i=2 и j=N. Увеличивая значения i и  j на 1, сравниваем элементы R_i и R_j с опорным элементом R₁, до тех пор пока не найдем элемент больше и меньше опорного соответственно. Если  i < j, поменяем местами R_i с R_i, затем повторим аналогичную процедуру со следующей записью, "сжигая свечку с обоих концов" пока не станет i > j. Завершается процесс разделения массива обменом записей R₁ с R_i. Посмотрим, например, что произойдет с нашей последовательностью из шестнадцати чисел.»

Пример одной итерации представлен  на рис 3.1

Рис.3.1 Пример одной итерации быстрой  сортировки.

Для удобства анализа указатели  i  и j ключи К₁ и К₂ выделены полужирным шрифтом.

 

3.Описания программы и используемых  алгоритмов

В программе используется несколько алгоритмов.

Алгоритм вывода на экран массива:

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

Алгоритм защиты от неправильного  ввода, при работе с пользователем:

Используя ASCII коды клавиш, проверяем введенную последовательность. При наличии символов, отличных от цифр, пробела и конца строки, выводим сообщение об ошибке.

Алгоритм быстрой сортировки:

Передаются номера на первого и последнего элемента. Создаются переменные j,i.

Наращиваются  созданные переменные при условии  выполнения неравенств: 
для j: A[j]>x &&j>0

для I: A[i]>x &&i<n+1

Проверяется местоположение переменных, происходит обмен элементов, если i < j.

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

 

 

 

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

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

Пример работы программы.

Рис 5.1 Ввод начальных данных

Рис 5.2 Пример работы программы

 

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

 

1)Запустите quicksort.exe

2)Выберите количество  сортируемых элементов

3)Выберете ввод  данных: случайные числа или с  клавиатуры.

4)введите данные (при  выборе «с клавиатуры»)

 

Примечание:

Следует учитывать:

1. Количество сортируемых элементов  располагается в диапазоне от 2 до 40 включительно.

2. Максимальный элемент располагается  в диапазоне от 0 до 99.

3. Программа предназначена для  работы с целыми числами.

 

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

 

7.Заключение

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

1. Лучший случай: N lg N сравнений

2. Средний случай: O(n log n) перестановок

3. Худший случай: O(n²) перестановок

Высоко эффективен при сортировки большего числа элементов, при малом  числе элементов эффективность  уменьшается. Можно существенно  увеличить эффективность сортировки, если подмассивы малого размера сортировать  другим способом (например, методом  простых вставок).

 

8.Список используемой литературы.

 

1. «Программирование на языке Си», К. Поляков, 1995 – 2009.
2. «Язык программирования С», Б. Керниган, Д. Ритчи.
3. «Искусство программирования», том 3, Д. Кнут.
4. Касаткин А.И. «Профессиональное программирование на языке Си»

 

 

 

Приложение А

Текст программы

//Курсовая работа

#include <locale.h>                                                             //для языка

#include <time.h>                                                               //для srand

#include <stdio.h>                                                              // для ввод вывод

#include <stdlib.h>                                                             // для переобразования типов и  для рандома

#include <windows.h>                                                      // для слипа

#include <graphics.h>                                                          

int A[40],n,sravn=0,perest=0,o=0;                                               // o-переменная для перевода строки  в графическом режиме

//Функция защиты

int defence (int gran_min,int gran_max,int &cifra)

{ int key=32,schet=0;                                      // переменные нажатой клавиши и кол-ва символов

  cifra=0;

  fflush(stdin);

  key=getchar();

  while (key==32) key=getchar();

  while (key==48) key=getchar();

  while (key!='\n'&& key!=32)

      {if ((key>47 && key<58))

           {cifra=cifra*10+(key-48);schet ++;               // «собираем» число из цифр

               }      

       else

           {printf("Ошибка! Не совпадает с возможным \n");

            Sleep (1000);

            system("cls");

            return 0;

            }

       key=getchar();           //считываем последующий за последней цифрой символ

      }

  if (key==32)

  {while (key==32) key=getchar(); //избавляемся от лишних пробелов

   if (key!='\n')

   {printf("Ошибка! Не совпадает с возможным \n");

    Sleep (1000);

    system("cls");

    return 0;

    }

  }

    if(cifra<gran_min||cifra>gran_max||schet >3)    //проверяем на значение

      {printf("Ошибка! Не совпадает с возможным \n");

       Sleep (1000);

       system("cls");

       return 0;

       }

 else return 1;

}

//Фунция вывода массива на экран

void print_a(int l , int p, int s)

{int g,; char t[3];

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

    {itoa(A[g],t,10);

     if (g==l || g==p )setcolor(2);

     else setcolor (7);

     if (g==s) setcolor (4);

     outtextxy(g*30,o*20,t);

    }

    o++;getch();

}

//Алгоритм быстрой сортировки

void quicksort(int lef, int prav)

{setcolor (15);

 outtextxy(0,o*20,"Мы выбираем опорный элемент (красный), который поделит массив чисел на два подмассива:");

 o++;

 outtextxy(0,o*20,"меньше и больше элемента стоящего на месте опорного.А так же выбираем элементы на коротрые указывают указатели (зеленые)");

 o++;

  //объявление указателей и опорного элемента

 int i=lef+1;

 int j=prav;

 int x=A[lef];

 int x_i=lef;

 

 print_a(i , j,x_i);

  //сортировка подмасива

  while(i<=j)

  { setcolor (15); 

    outtextxy(0,o*20,"Поочередно находим элементы больше опорного и меньше опорного");

    o++;

    print_a(i , j,x_i);

    //нахождения элементов для обмена

    while (A[i]<x && i<prav+1) { ++i; print_a(i , j,x_i);sravn++;}  

    while (A[j]>x &&j>0) {--j; print_a(i , j,x_i);sravn++;}

  

       

    if(i <= j)

            {   setcolor (15);                   

                outtextxy(0,o*20,"Поменяем местами найденные элементы");

                o++;

               

                int temp=A[i];

                A[i]=A[j];

                A[j]=temp;

                print_a(i , j,x_i);

                ++i;--j; perest++;        

            }  

  }

 

 setcolor (15);                   

 outtextxy(0,o*20,"Поменяем местами опорный и последний найденный элемент т.к. указатели поменялись");

 o++;

//обмен опороного элемента с  последним найденным

 int temp=A[lef];

 A[lef]=A[j];

 A[j]=temp;

 perest++;

 print_a(i , j,j);

 

 setfillstyle ( 1, 0 );

 bar ( 0, 0, 1366,768 );

 o=0;

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

 if(lef < j-1) quicksort( lef, j-1);

 if(j+1 < prav) quicksort( j+1, prav);    

 }

 

 

 

 

main()

{//блок обяъявления

setlocale(LC_CTYPE,"Russian");

int i,sp,max;

char ch='\n';

srand(time(NULL));

 

//ввод кол-ва символов

printf("Введи кол-во символов  в массиве\n");

while (defence(2,40,n)!=1 )

   { printf("Введи кол-во символов в массиве\n");

                                                                //очищает поток, чтобы опять считывать c клавы

   }

 

//выбор заполнения

printf("Введите способ заполнения  массива\n 1-Случайные числа \n 2-С  клавиатуры\n");

while (defence(1,2,sp)!=1 ) printf("Введите способ  заполнения массива\n 1-Случайные  числа \n 2-С клавиатуры\n");

system("cls");

if (sp==1)

   { printf("Введи максимальный элемент массивa \n");

     while(defence(0,99,max)!=1)printf("Введи максимальный элемент массивa\n");

     for (i=0;i<n;i++) A[i]=rand()%(max+1);

   }

else

   {

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

       { printf("Введи %d элемент массивa \n",i+1);

         while(defence(0,99,А[i])!=1)printf("Введи %d элемент массивa \n",i+1);

       }

    }   

printf("Иссходная последовательность:\n");

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

   {printf("%3d\t",A[i]);}

printf("\n\n");

initwindow(1366,768,"Демонстрация быстрой  сортировки");

settextstyle(8, 0, 1);

quicksort(0,n-1);

closegraph();

printf("\n\n");

printf("Отсортированная последовательность:\n");

for (i=0;i<n;i++) printf("%d \t",A[i]);

printf("\n\n");

printf("Кол-во сравнений %d\nКолв-во  перестановок %d\n",sravn,perest);

system("pause");

}

 

Приложение Б

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

main:

!=1

Sp=1

 

 

 

 

 

 

 

                                              нет                                       да

 

 

 

 

нет да

 

Запроc на ввод максимального элемента