Элементарные методы сортировки

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

Федеральное государственное бюджетное образовательное учреждение

Высшего образования

«Российский экономический университет имени Г.В. Плеханова»

ФДО

Кафедра Управления информационными системами и программирования

КУРСОВАЯ РАБОТА

 

По дисциплине «Информатика и программирование»

На тему «Анализ алгоритмов сортировки массивов данных»

 

 

Выполнила:

студентка группы ПИ-101у

Милованов Ю.А.

Научный руководитель:

к.э.н., доцент Комлева Н.В.

 

 

Москва – 2017

 

 

ОГЛАВЛЕНИЕ

Введение. 3

Глава 1. Массивы.. 4

Глава 2. Элементарные методы сортировки. 5

2.1. Сортировка выбором. 5

2.4. Сортировка Шелла. 14

2.7. Пирамидальная сортировка. 19

2.8. Поразрядная сортировка. 21

Глава 3. Специальные методы сортировки. 25

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

Список литературы.. 28

 

Введение

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

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

В данной работе будет представлена моя точка зрения на поставленную тематику.

Цель: изучить алгоритмы сортировки массивов.

Задачи:

- Рассмотреть методы сортировки массивов, выявить наиболее актуальные из них;

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

Объект исследования: Алгоритмы сортировки массивов в программировании.

Предмет исследования: Массивы в программировании.

Методы исследования – изучение профессиональной литературы и информационного портала.

 

Массив

Перед тем как начать анализировать методы сортировки, стоит познакомится с понятием массив, что такое массив и с чем его едят.

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

Размерность массива – это количество индексов, необходимых для адресации в рамках массива.

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

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

Многомерный массив – это массив, имеющий несколько строк и несколько столбцов образующих матрицу. Двумерные массивы представляют в виде матрицы.

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

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

 

 

Элементарные методы сортировки

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

Метод элементарной сортировки удобен для сортировки небольших файлов или файлов со специальной структурой.

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

Сортировка выбором

Selectionsort (сортировка выбором) – Это один из самых простых методов сортировки и работает он следующим образом, а именно: сначала находится наименьший элемент массива и меняется местами с первым элементом массива, потом находится второй и меняется местами со стоящим вторым в исходном массиве и так продолжается до тех пор, пока все элементы массива не встанут на свои места. На рисунке 1 представлен вариант сортировки выбором.

Рисунок 1

 

Посмотрим как это выглядит в коде:

#include<iostream>

using namespace std;

inti, j;

void SelectionSort(int A[], int n) //сортировкавыбором

{

int count, key;

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

{

count=A[i]; key=i;

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

if (A[j]<A[key]) key=j;

if (key!=i)

{

A[i]=A[key];

A[key]=count;

}

}

cout<<"Результирующий массив: ";

for (i=0; i<n; i++) cout<<A[i]<<" "; //выводмассива

}

//Главнаяфункция

int main()

{

setlocale(LC_ALL, "Rus");

int n, A[1000];

cout<<"Количество элементов > "; cin>>n;

for (i=0; i<n; i++) //вводмассива

{ cout<<i+1<<" элемент> "; cin>>A[i]; }

SelectionSort(A, n);

}
Результат сортировки представлен на рисунке 2.

Рисунок 2

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

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

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

 

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

Insertionsort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Весомым плюсом является возможность сортировать массив по мере его получения. То есть имея часть массива, можно начинать его сортировать. В параллельном программирование такая особенность играет не маловажную роль.

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

Рисунок3

 

Далее представлен код реализации сортировки вставками:

// Example program

#include <iostream>

using namespace std;

intmain()

{

// Считываем размер массива,

// который необходимо отсортировать

intsize;

cout<<input;

cin>>size;

// Динамически выделяем память под

// хранениемассиваразмера size

int *a = new int[size];

// Считываеммассив

for (inti = 0; i< size; i++) { cin>> a[i];

}

for (inti = 0; i< size; i++) { int temp = a[i];// запомнимi-ыйэлементint j =i-1;//будемидтиначинаяс i-1 элемента while(j >= 0 && a[j] > temp)

// пока не достигли начала массива

// или не нашли элемент больше i-1-го

// который храниться в переменной temp

{

a[j + 1] = a[j];

//проталкиваем элемент вверх

j--;

}

a[j + 1] = temp;

// возвращаем i-1 элемент

}

// Выводимотсортированныймассив

for (inti = 0; i< size; i++) { cout<< a[i] << ' '; } return 0; }

#include <iostream>

using namespace std;

inti, j, key=0, temp=0;

void InsertSort(int *mas, int n) //сортировкавставками

{

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

{

key=i+1;

temp=mas[key];

for (j=i+1; j>0; j--)

{

if (temp<mas[j-1])

{

mas[j]=mas[j-1];

key=j-1;

}

}

mas[key]=temp;

}

cout<<endl<<"Результирующий массив: ";

for (i=0; i<n; i++) //вывод массива

cout<<mas[i]<<" ";

}

//Главнаяфункция

int main ()

{

int n;

cout<<"Количество элементов в массиве > "; cin>>n;

int *mas=new int[n];

for (i=0; i<n; i++) //вводмассива

{ cout<<i+1<<" элемент> "; cin>>mas[i]; }

InsertSort(mas, n); //вызовфункции

delete[] mas;

system("pause>>void");

}

Результат сортировки на рисунке 4.

Рисунок4

 

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