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

Томский Государственный Университет Систем Управления и Радиоэлектроники (ТУСУР)

Кафедра радиоэлектроники и защиты информации 
 
 
 
 
 

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

Пояснительная записка к курсовой работе. 
 
 
 

Выполнил  студент гр.149-2:

_____________Петухов  И.Б.

      “___” ___________ 2010 год

Руководитель:

____________Смирнов  Е.В.

“___” ___________2010 год 
 
 
 
 
 

Томск 2010

РЕФЕРАТ

       Курсовая  работа  17с, 2 прил,1 табл,7 ист

       Цель  работы – разработка программы сортировки массива методом <<выбора>>.

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

       Курсовая  работа выполнялась в компиляторы : Eclipse C++.

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

Содержание.

Введение 4

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

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

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

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

Заключение 11

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

Приложение А Файл sortirovka.cpp 13

Приложение Б Блок-схема 17 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

 

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

1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.
3. И так далее до предпоследнего элемента.

      Ниже  представлена программа сортировки массива целых чисел по возрастанию.

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

 

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

 

      Сортировка  выбором — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов  имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая  что сравнения делаются за постоянное время.

      Сортировка - процесс  перестановки объектов данного  массива в определенном порядке. Целью сортировки являются упорядочение массивов для облегчения последующего поиска элементов в данном массиве.

• метод  парных перестановок  сортировки массива основан  на  принципе сравнения и обмена  пары  соседних  элементов. Процесс перестановок пар повторяется просмотром массива с начала до тех пор , пока  не будут отсортированы все  элементы , т.е.  во время  очередного просмотра не произойдет ни одной перестановки.
• модифицированный метод  простого выбора сортировки
• основывается на алгоритме поиска минимального элемента. В массиве  А(1..n) отыскивается минимальный  элемент, который ставится  на  первое  место . Для  того, чтобы  не потерять элемент , стоящий  на  первом  месте , этот  элемент   устанавливается  на  место минимального . Затем  в  усеченной последовательности, исключая  первый элемент, отыскивается минимальный элемент и ставится на второе место и так  далее n-1 раз  пока  не  встанет  на свое место предпоследний n-1 элемент массива А, сдвинув максимальный элемент в самый конец.

 

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

 

Исходные данные:

     Размер  массива не превышает 40 и задается с клавиатуры. Заполнение массива  с помощью датчика случайных  чисел или с клавиатуры по выбору пользователя. Элементы массива целые  неотрицательные числа. Максимальное значение элементов массива задается с клавиатуры и не превышает 99.

     Цель  работы:

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

 

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

Рассмотрим задачу упорядочивания массива в следующей  постановке:

     Дан числовой массив , требуется переставить элементы массива так, чтобы они удовлетворяли после перестановки неравенствам:

      

     Воспользуемся следующим алгоритмом сортировки для  решения поставленной выше задачи: найдем среди  элементов массива минимальный элемент и его номер, и затем поменяем его местами с первым элементом. Далее, среди оставшихся элементов (без первого элемента массива) определим минимальных элемент и его номер, и переставим этот элемент со вторым элементом массива. Процесс будем повторять до тех пор, пока не останется один элемент. Именно он и будет наибольшим элементом в массиве. Таким образом. В алгоритме простого выбора весь массив делится на готовую часть и исходную. На каждом шаге алгоритма граница смещается на один элемент вправо. В исходной части выбирается минимальный и добавляется к готовой части. Проиллюстрируем описанный алгоритм на примере.

     Пример.

     Пусть и задан массив из пяти целых чисел: 1, 2, 0, 5, 4. Отсортируем массив в порядке возрастания.

     1-й  шаг. Среди заданных чисел находим  минимальный элемент 0, стоящий  на 3-м месте, и переставляем  его с 1-м элементом. Получим:

     0, 2, 1, 5, 4.

     2-й  шаг. Среди чисел 2, 1, 5, 4 находим  минимальное значение (это будет  1), стоящее в массиве на 3-м месте,  и меняем его местами со  вторым элементом. Будем иметь:

     0, 1, 2, 5, 4.

     3-й  шаг. Поскольку минимальным среди  чисел 2, 5, 4 является 2 и это число  стоит на 3-м месте, то после  сортировки на этом шаге положение  элементов в массиве не изменится:

     0, 1, 2, 5, 4.

     4-й  шаг. Среди чисел 5, 4 определяем  минимальное значение 4 и переставляем  его со значением 5. Получаем  в итоге:

     0, 1, 2, 4, 5.

     Итак, элементы массива отсортированы  в порядке возрастания за шагов.

     Оформим разобранный способ сортировки простым выбором в виде фкнкции на языке С++. В качестве параметров функции выступает число требуемых перестановок, длина массива и сам массив.

void  selection(int &Perm, int Size, int *a)

{int i,j,k,      //  parameters of cycle

        nom,       // number of minimal element

        min;       // minimal element 

Perm=0;

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

{

       nom=i;

       min=a[i];

       for (j=i+1;j<Size;j++)  //find the minimum element

                               //     and its number at each step

             if (a[j]<min)

             {

                   min=a[j];

                   nom=j;

             }

       if (a[i]>min)   // if the current element is greater than the

                         // minimum then they will be permutated

       {

             Perm=Perm+1;

             a[nom]=a[i];

             a[i]=min;

       } 

       cout<<"step="<<i+1<<"  array:=    ";  //step mode

       for (k=0;k<Size;k++)

             cout<<a[k]<<" ";

       cout<<endl;

 }

}

     Анализ  сортировки простым выбором показывает, что число сравнений элементов  массива не зависит от начального положения элементов в массиве  и равно 

       .

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

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

В файле sortirovka.cpp находится исходный код.

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

     Затем пользователь должен выбрать способ заполнения массива (нажать 1, если задавать массив с помощью датчика случайных  чисел; нажать 2, если с клавиатуры).

     При нажатии «1» функция createMas(Size,AMax,a) создает массив а, имеющий размер Size, и элементы которого не превышают значение Amax.

     При нажатии «2» пользователь должен задать значения элементов массива  с клавиатуры, причем они должны входить в диапазон 1..Amax.

     Выдаются  значения исходного массива.

     С помощью функции selection(Perm,Size,a)  массив а сортируется по возрастанию. На экране пошагово отображается все перестановки в массиве.

     Выдается  отсортированный массив, а так  же значения числа сравнений и  числа перестановок (Perm). 

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

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

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

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

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