Задание 7. Сортировка массива

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

Пример. Реализовать пузырьковую сортировку случайным образом генерируемого массива. Пузырьковая сортировка: массив просматривается от начала до конца. Сравниваются i -тое и (i +1)-ое числа. Если i -тое число больше (сортировка по возрастанию), то они меняются местами. Массив просматривается до тех пор, пока от начала до конца массива не сделано ни одной перестановки соседних чисел.

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void main ()

{

int a[100],n,b;

bool f;

cout<<"Enter n<100 ";

cin >>n;

cout<<"\nArray:\n";

randomize();

for (int i=0;i<n;i++) //Генерируем массив случайных чисел в

//диапазоне [0..50] и выводим на экран

{

a[i]= random(51);

cout <<a[i]<<" ";

}

cout<<"\nSotr:\n";

do

{

f=false;

for(int i=0;i<n-1;i++)// Просматриваем весь массив

if (a[i]>a[i+1])

{

b=a[i];

a[i]=a[i+1];

a[i+1]=b;

f=true; //Был обмен

}

}

while (f); // Проверяем, был ли хоть один обмен

for (int i=0;i<n;i++) // Выводим на экран отсортированный

//массив

cout<<a[i]<<" ";

}

Отсортировать случайным образом генерируемый массив, используя следующие алгоритмы.

1. Усовершенствованная пузырьковая сортировка. Используется принцип пузырьковой сортировки, но массив просматривается не от начала до конца, а от начала до последнего перемещенного элемента (после которого все элементы уже упорядочены). Вначале этим «последним» элементом выбирается последний элемент массива.

2. Простой выбор. Выбрать наибольший элемент массива и поменять его местами с последним (n -ным) элементом массива. Затем из n -1 первых элементов опять выбрать наибольший и опять поменять его местами с (n -1)-м. И так далее, пока весь массив не будет упорядочен.

3. Простые вставки. Так обычно сортируют карты: из веера карт берут одну, стоящую не по старшинству и помещают между двумя уже упорядоченными картами. Массив просматривают с начала до конца. Рассматривается i-тый элемент массива и вставляется на нужную позицию в ряду первых (i -1) уже упорядоченных элементов. (Первоначально “упорядочен” только первый элемент массива). Если i -тый элемент перемещается в j -тую позицию, то все элементы с j -того по (i -1)-ый элемент должны быть сдвинуты на одну позицию вправо.

4. Метод подсчета. Если для какого-то элемента массива известно, что если он больше, чем i других элементов этого массива, то он должен стоять на (i +1)-ом месте после упорядочивания. Для каждого i-го элемента массива считают, сколько чисел меньше его, и результат заносят в массив индексов с [ i ]. Это делается следующим образом. Сравнивают попарно все элементы массива: i -тый и j -тый. (Одна пара чисел может сравниваться только один раз.) Если i -тый больше, то с[ i ] увеличивают на единицу, иначе c[ j ] увеличивают на единицу. После формирования массива индексов с, формируют результирующий массив.

5. Метод распределяющего подсчета. Используется, если в массиве много одинаковых элементов. Создается массив индексов d [ i ]. Размерность массива – число различных между собой элементов исходного массива. Затем в элемент массива d [ i ] заносят количество элементов массива, равных i, и в результирующий массив записывают по d [ i ] элементов i -того типа. Например, исходный массив 0010101031; d [0]=5, d [1]=4, d[2]=0, d[3]=1. Результирующий массив 0000011113.