Сортировка массива методом вставок

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..............................................................................................................4
1. РАЗРАБОТКА ПРОЕКТА.................................................................................5
1.1. Описание структуры и формы представления входных и выходных данных......................................................................................................................5
1.2. Разработка алгоритма решения задачи...........................................................5
1.3. Разработка структуры программы................................................................10
2. РАЗРАБОТКА ПРОГРАММЫ.........................................................................11
2.1. Листинг программы........................................................................................11
2.2. Формирование тестовых данных и тестирование программы...................14
3. ОПИСАНИЕ ПРОГРАММЫ............................................................................16
3.1. Описание структуры программы..................................................................16
3.2. Руководство пользователя.............................................................................18
ЗАКЛЮЧЕНИЕ.....................................................................................................19
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ............................................20[pic 1]

ВВЕДЕНИЕ

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

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

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

        На вход алгоритма подается последовательность n чисел: a1,a2,a3...an.  На выходе алгоритм должен вернуть перестановку исходной последовательности, чтобы выполнялось следующее соотношение
. Сортировка вставками имеет сложность n2, количество сравнений вычисляется по формуле . Так, например, для массива с 10 элементами количество перестановок будет равно 45.[pic 2][pic 3]

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

1. РАЗРАБОТКА ПРОЕКТА

1.1. Описание структуры и формы представления входных и выходных данных

        Входными данными для сортировки массива вставками являются:
1) n - переменная, которая вводится пользователем с клавиатуры, содержит информацию о размере массива. Это переменная целочисленного типа  (int), занимает в памяти 2 байта, использующиеся для представления целых чисел от -32768 до 32767;        
2) int *x - указатель на массив, состоящий из n элементов целочисленного типа (int). Программа выделяет память (2×n байт) сразу под группу элементов, т.е. данный массив является динамическим и его размер задается пользователем;
3) var - задаваемая пользователем переменная типа char, служащая для выбора способа заполнения массива (ручной или автоматический). Занимает в памяти 1 байт, использующийся для представления целых чисел и символов от 0 до 255.

        Выходными данными для задачи являются:        
1) int *x - указатель на отсортированный массив, состоящий из n элементов. Выделяемая память под данный тип данных равняется 2×n байтам.

1.2. Разработка алгоритма решения задачи

        Алгоритм сортировки вставками с помощью псевдокода можно записать следующим образом:        
        1. Задать размерность массива n, сам массив Х.        
        2. ЦИКЛ (i=0; i                2.1. temp = X[i];          
                2.2. j=i-1;        
                2.3. ПОКА j ≥ 0 и x[j]>temp        
                        2.3.1. x[j+1]=x[j]        
                        2.3.2. j=j-1        
                2.4. x[j+1]=temp        
                2.5. КОНЕЦ ЦИКЛА        
                2.6. Печать массива