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

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

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

#include <iostream>

using namespace std;

Void SelectSort(int a[], int n)

{ int k, min;

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

{ k = i; min = A[i];

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

if(A[j] < min) { k = j; min = A[j]; }

A[k] = A[i]; A[i] = min;

}

}

Void main()

{ setlocale(LC_ALL, "Rus");

int i, N; int A[100];

cout<<"Количество= "; cin>>N;

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

{ cout<<" А= "; cin>>A[i]; }

SelectSort(A, n);

cout<<"Результат: ";

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

cout<<A[i]<<" ";

}

При сортировке выбором требуется Q = (n - m) * (n - m) действий и не требуется дополнительной памяти.

Число сравнений равно n(n - 1) / 2 (в среднем порядка n²), где n - количество записей в таблице.

Максимальное количество перестановок при такой сортировке равно (n - 1).

Оценка сложности алгоритма - O(n²)

Сортировка квадратичной выборкой

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

Сортируемый массив, состоящий из n элементов, разделяется на группы по n элементов в каждой (если n не является точным квадратом, то таблица разделяется на n' групп, где n' - ближайший точный квадрат, больший n).

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

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

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

Количество действий, требуемое для сортировки квадратичной выборкой, несколько меньше, чем в предыдущих методах и равно n². Общее число сравнений равно приблизительно 2n*sqrt(n), необходимый резерв памяти - поле длиной (n+sqrt(n)) элементов.

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

Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения. То есть, имея часть массива, можно начинать его сортировать.

Сортируемый массив надо разделить на две части — отсортированная часть и неотсортированная.

В начале сортировки первый элемент массива считается отсортированным, все остальные — не отсортированные.

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

Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент. 

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

{ int t, i, j;

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

{ t = A[i];

for (j = i-1; j >= 0 && A[j] >t; j--)

A[j + 1] = A[j];

A[j + 1] = t;

}

}

Внешний цикл выполняется n - 1 раз, внутренний – не больше, чем n - 1.