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

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

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

Данный вид сортировки мы просто рассмотрим.

 

Нечетно-четная сортировка слиянием Бэтчера

Алгоритм четно-нечетной сортировки слиянием (odd-evenmergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна.

Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится в состояние «истина», далее каждый нечётный элемент сверяется с последующим и если они стоят в неправильном порядке (предыдущий больше следующего), то они меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».

 

Сортирующие сети

Сортирующая сеть (англ. Sortingnetwork) — метод сортировки, основанный только на сравнениях данных. Схематически изображается в виде параллельных прямых (проводов), соединенных вертикальными линиями (сравнивающими устройствами). Особенность сети сортировки в том, что сравнения выполняются независимо от предыдущих. Кроме того, сравнения могут выполняться одновременно.

Внешняя сортировка

Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память.

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

 

Заключение

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

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

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

 

 

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

1. Роберт Седжвик. Алгоритмы на С++. Вильямс, 2017.

2. Немцова Т.И, Голова С.Ю., Терентьев А.И. Программирование на языке С++: Учебное пособие. Под ред. Л.Г. Гагариной. - М.: ИД ФОРУМ: ИНФРА-М, 2012.

3. Кузин А.В. Программирование на языке Си/А.В.Кузин, Е.В.Чумакова. - М.: Форум, НИЦ ИНФРА-М, 2015. - 144 с.

4. Воронцова Е. А. Программирование на С++ с погружением: практические задания и примеры кода. - М.:НИЦ ИНФРА-М, 2016.

5. Э.Э. Александров, В.В. Афонин. Программирование на языке С в MicrosoftVisualStudio 2010. Учебное пособие. Саранск, изд-во Мордовского университета, 2010

6. Н. Вирт. Алгоритмы и структуры данных. М. Мир, 2006.

7. Окул Скотт Мейерс. Эффективное использование С++. ДМК Пресс, 2017.

8. Седжвик Роберт. Фундаментальные алгоритмы на С++.

9. Части 1-4. Анализ/ Структуры данных/ Сортировка/ Поиск. Диасофт, 2011.

10. Б.С. Хусаинов. Структуры и алгоритмы обработки данных. Примеры на Си. М., Финансы и статистика, 2004.

11. Н.В. Комлева. Структуры и алгоритмы компьютерной обработки данных. М., 2013.

12. Роберт Лафоре. Объектно-ориентированное программирование в С++. Питер, 2015.

13. Березин Б.И. Начальный курс С++. Диалог-МИФИ, 2017.

ПРИЛОЖЕНИЕ 1

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

#include <iostream>

#include <stdio.h>

using namespace std;

intenterV ()

{

int a;

cout<< "Введите целое значение: \n";

cin>> a;

return a;

}

int main ()

{

setlocale(LC_ALL, "Russian");

int input,n,n2,ar1[20],ar2[20],ar3[20],value, tmp;

while (1)

{

int *arr;

int count = 0, max = 0, min = 0;

bool check = false;

cout<< "Введитедлинумассива: \n";

cin>> n;

cout<< "Введите значения массива: \n";

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

cin>>ar1[i];

cout<< "====================================================\n";

cout<< "1.Сортировка пузырьком.\n";

cout<< "2.Сортировка выбором.\n";

cout<< "3.Сортировка вставками.\n";

cout<< "4.Сортировка слиянием.\n";

cout<< "5.Быстрая сортировка.\n";

cout<< "0. Выйти\n";

cin>> input;

cout<< "====================================================\n";

switch (input)

{

case 1:

 

if (n <= 0) {

// Размер масива должен быть положитлеьным

cerr<< "Invalidsize" <<endl;

return 1;

}

 

arr = newint[n]; // выделение памяти под массив

 

// заполнениемассива

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

cout<< "arr[" <<i<< "] = ";

cin>>arr[i];

}

 

inttemp; // временная переменная для обмена элементов местами

 

// Сортировкамассивапузырьком

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

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

if (arr[j] >arr[j + 1]) {

// меняем элементы местами

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

 

// Вывод отсортированного массива на экран

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

cout<<arr[i] << " ";

}

cout<<endl;

 

 

break;

case 2:

 

int size;

cin>> size;

 

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

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

int *a = new int[size];

 

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

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

}

 

for (int i = 0; i <size; i++) { // Найдем минимальный элемент на //промежутке индексов [i; size); // изначально его индекс равен i

intminValueIndex = i; // Переберем оставшиеся элементы промежутка

for (int j = i + 1; j <size; j++) { // Если элемент в позиции j меньше // элемента в позиции minValueIndex, то // необходимо обновить значение индекса

if (a[j] < a[minValueIndex]) { minValueIndex = j; } } // Меняем текущий элемент с минимальным

swap (a[i], a[minValueIndex]); } // Выводим отсортированный массив

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

 

break;

 

case 3:

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]<<" ";

}

 

break;

case 4:

 

 

void Merge(int *A, int first, int last)

{

int middle, start, final, j;

int *mas=new int[100];

middle=(first+last)/2; //вычислениесреднегоэлемента

start=first; //начало левой части

final=middle+1; //начало правой части

for(j=first; j<=last; j++) //выполнение от начала до конца

if ((start<=middle) && ((final>last) || (A[start]<A[final])))

{

mas[j]=A[start];

start++;

}

else

{

mas[j]=A[final];

final++;

}

//возвращение результата в список

for (j=first; j<=last; j++) A[j]=mas[j];

delete[]mas;

};

//рекурсивнаясортировка

void MergeSort(int *A, int first, int last)

{

{

if (first<last)

{

MergeSort(A, first, (first+last)/2); //сортировкалевойчасти

MergeSort(A, (first+last)/2+1, last); //сортировкаправойчасти

Merge(A, first, last); //слияниедвухчастей

}

}

};

 

break;

case 5:

void quickSort(int *numbers, int left, int right)

{

intpivot; // разрешающий элемент

intl_hold = left; //левая граница

intr_hold = right; // праваяграница

pivot = numbers[left];

while (left<right) // пока границы не сомкнутся

{

while ((numbers[right] >= pivot) && (left < right))

right--; // сдвигаем правую границу пока элемент [right] больше [pivot]

if (left!= right) // если границы не сомкнулись

{

numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего

left++; // сдвигаем левую границу вправо

}

while ((numbers[left] <= pivot) && (left < right))

left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]

if (left!= right) // если границы не сомкнулись

{

numbers[right] = numbers[left]; // перемещаемэлемент [left] наместо [right]

right--; // сдвигаем правую границу вправо

}

}

numbers[left] = pivot; // ставим разрешающий элемент на место

pivot = left;

left = l_hold;

right = r_hold;

if (left<pivot) // Рекурсивно вызываем сортировку для левой и правой части массива

quickSort(numbers, left, pivot - 1);

if (right > pivot)

quickSort(numbers, pivot + 1, right);

}

 

break;

case 0:

cout<< "Работа завершена\n====================================================\n";

 

return 0;

break;

default:

cout<<"Ошибка, неправильный ввод\n";

break;

}

cout<< "\n====================================================\n";

intansw;

cout<< "Повторить?\n1. Да\n0. Выйти\n";

cin>>answ;

cout<< "====================================================\n";

if (!answ)

break;

}

cout<< "Работазавершена\n====================================================\n";

 

return 0;

}