Реализация алгоритмов сортировки

МИНОБРНАУКИ РОССИИ

 

Федеральное государственное бюджетное образовательное  учреждение высшего профессионального  образования «Саратовский государственный  технический университет имени  Гагарина Ю.А.»

 

 

 

 

 

Контрольная работа

По дисциплине «Технология программирования»

На тему «Реализация алгоритмов сортировки»

 

 

 

Выполнила:

Студентка группы ИФСТ 023

Тайкова М.И.

 

 

Проверил:

Препадователь кафедры МФПИТ

 Соколов Д.И.

 

 

 

 

 

Саратов 2013

 

Цель  работы:

Получить необходимые знания об основных концепциях и алгоритмах в  программировании, а также практические навыки их реализации на языке С. Курс предназначен для студентов технических  специальностей ВУЗов.

 

Задание

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

 

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

• пузырьковая сортировка
• сортировка вставкой
• сортировка выбором

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

• по возрастанию
• по убыванию
• случайными целыми числами в диапазоне от 0 до 99

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

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

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

 

Отчет по лабораторной работе должен включать:

• титульный лист
• задание на лабораторную работу с номером варианта
• листинг программы
• блок-схемы алгоритмов
• таблицы сравнений алгоритмов на различное число элементов
• выводы о результатах работы

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

Полученные результаты должны быть представлены в виде таблицы, например:

 

Таблица сравнения алгоритмов сортировки на различное число элементов.

 

Алгоритм сортировки	Способ заполнения массива	Время работы алгоритма, мс	Количество операций
			сравнения	присвоения
Сортировка пузырьком	По возрастанию
	По убыванию
	Случайным образом
Сортировка вставкой	По возрастанию
	По убыванию
	Случайным образом
Сортировка выбором	По возрастанию
	По убыванию
	Случайным образом

 

 

Аналогично составляются таблицы  на 100, 1000, 5000 элементов.

Для каждого из рассмотренных алгоритмов сортировок составляется блок-схема.

 

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

 

Листинг программы.

 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

void fillDesc(int size, int * array);

void fillAsc(int size, int * array);

void fillRand(int size, int * array);

 

void sortBubble(int size, int * array);

void sortInsertion(int size, int * array);

void sortSelection(int size, int * array);

 

void displayArray(int size, int * array);

 

int main()

{

    int size = 0, item = 0;

    int * array;

 

    printf("Input size array: ");                 /*Просьба ввести размер массива*/

    scanf("%i", &size);                            /*Вводим размер массива*/

 

array = malloc(size * sizeof(int));          /* Функция malloc - возвращает указатель на первый байт области памяти размером size, которая была выделена из динамически распределяемой области памяти*/

 

    while(!item)

    {

        printf("\nFill array:\n");                    /*Заполним массив отдним из способов*/

        printf("1 - Descending order\n");             /*По убыванию*/

        printf("2 - In ascending\n");                 /*По возрастанию*/

        printf("3 - Random\n");                       /*Случайными числами*/

        printf("Enter the item number... ");         /*Введите номер элемента*/

        scanf("%i", &item);                           /*Вводим как мы хотим заполнить массив*/

 

switch(item)                                  /* Взависимости какой способ мы выбрали switch выполняет  переход на ту или иную метку*/

        {

            case 1: fillDesc(size, array); break;        /*А операторы case определяют эти самые метки,   в данном случае по убыванию*/

            case 2: fillAsc(size, array); break;          /*По возрастанию*/

            case 3: fillRand(size, array); break;          /*Случайными числами*/

            default : printf("\n Invalid item\n"); item = 0; break;   /*Проверка соответствия введенному значению*/

        }

    }

 

displayArray(size, array);                          /*Выводим на экран размер и массив с выбраным заполнением*/

 

    item = 0;

    while(!item)

    {

        printf("\n\nSorting array:\n");                   /* Сортирвка массива*/

        printf("1 - Buble sort\n");                       /* Пузырьковая. */

        printf("2 - Insertion sort\n");                          /*Сортировка вставкой..*/

        printf("3 - Selection sort\n");                              /*Сортировка выбором.

*/

        printf("Enter the item number...");                       /*Введите номер элемента*/

        scanf("%i", &item);

 

switch(item)                                                 /* Взависимости какой способ мы выбрали switch выполняет

                                                                          переход на ту или иную метку*/

        {

            case 1: sortBubble(size, array); break;                /*пузырьковая сортировка*/

            case 2: sortInsertion(size, array); break;             /*сортировка вставкой*/

            case 3: sortSelection(size, array); break;              /*сортировка выбором*/

            default : printf("\n Invalid item\n"); item = 0; break;      /*Проверка соответствия веденному значению*/

        }

    }

 

    displayArray(size, array);

 

    free(array);

 

    return 0;

}

 

void fillDesc(int size, int * array)               /*Метод заполнения по убыванию*/

{

    int i;

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

        array[i] = size - i - 1;

}

 

void fillAsc(int size, int * array)              /*Метод заполнения по возрастанию*/

{

    int i;

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

        array[i] = i;

}

 

void fillRand(int size, int * array)             /*Метод заполнения случайными числами*/

{

    srand(time(NULL));

 

    int i;

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

        array[i] = rand()%100;

}

 

void sortBubble(int size, int * array)             /*Метод сортировки пузырьком*/

{

    int i, j, tmp;

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

    {

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

        {

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

            {

                tmp = array[j];

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

                array[j + 1] = tmp;

            }

        }

    }

}

 

void sortInsertion(int size, int * array)              /*Метод сортировки вставкой*/

{

    int i, j, tmp;

    for (i = 1; i < size; i++)

    {

        tmp = array[i];

 

        j = i - 1;

        while(j >= 0 && array[j] > tmp)

        {

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

            j--;

        }

 

        array[j + 1] = tmp;

    }

}

 

void sortSelection(int size, int * array)                 /*Метод сортировки выбором*/

{

     int i, j, min, tmp;

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

     {

        min = i;

 

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

        {

            if(array[j] < array[min])

                min = j;

        }

        if(min != i)

        {

            tmp = array[i];

            array[i] = array[min];

            array[min] = tmp;

        }

    }

}

 

void displayArray(int size, int * array)

{

    int i;

    printf("\nArray: ");

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

        printf("%i ", array[i]); }

Таблица сравнений алгоритмов на различное  число элементов.

 

На 10 элементов.

 

Алгоритм сортировки	Способ заполнения массива	Время работы алгоритма, мс	Количество операций
			сравнения	присвоения
Сортировка пузырьком	По возрастанию	28.090
	По убыванию	27.621
	Случайным образом	6.187
Сортировка вставкой	По возрастанию	17.298
	По убыванию	10.388
	Случайным образом	7.742
Сортировка выбором	По возрастанию	10.365
	По убыванию	6.333
	Случайным образом	6.251

 

 

Вывод.