Сортировки. Квадратичные сортировки (сортировка выбором, «пузырьковая сортировка»). Сортировка подсчётом. Быстрая сортировка QuickSort.
Алгоритмы сортировки - это методы для упорядочения элементов массива в каком-либо порядке.
Алгоритмы сортировки оцениваются по скорости выполнения и количествую используемой памяти.
Время (скорость выполнения) - основной параметр, он измеряется относительно количества элементов исходного массива. Например: $O(n)$ - время выполнения растёт пропорционально количеству элементов, $O(n^2)$ - пропорционально квадрату количества элементов.
При описании всех алгоритмов: N или $n$ - количество элементов в массиве.
Квадратичные сортировки, сортировка "Пузырьком"
Это самая простая сортировка, её следует применять когда у вас немного элементов (до десятков тысяч). Её сложность $O(n^2)$, т.е. количество операций растёт как квадрат от количества элементов.
Шаги алгоритма:
- Считываем исходный массив в память.
- Пока происходят изменения в массиве: сравниваем каждые два соседних элемента, и если они не стоят не в том порядке, меняем их местами.
- Теперь массив отсортирован, выводим его.
{$APPTYPE CONSOLE}
var
N : Integer; { Количество элементов в массиве }
A : array [1..5000] of Integer; { Сортируемый массив }
i : Integer; { Переменная цикла }
temp : Integer; { Переменная для обмена местами двух элементов в массиве }
Changes : Boolean; { Есть ли изменения? }
begin
{ Ввод исходного массива из файла }
Reset(Input,'bubble.in');
Read(N); { Читаем количество элементов в массиве }
for i:=1 to N do Read(A[i]); { Читаем сам массив }
{ Сортировка }
repeat
Changes := false; { Пока изменений нет :) }
for i:=1 to N-1 do { Пробегаем по массиву сравнивая соседние элементы }
if A[i]>A[i+1] then begin { Если больший элемент слева, а должен быть справа }
temp := A[i]; { Меняем элементы местами при помощи временной переменной temp }
A[i] := A[i+1];
A[i+1] := temp;
Changes := true; { Изменения произошли! }
end;
until not Changes; { Заканчиваем когда нет изменений (значит, все элементы уже по-порядку) }
{ Вывод отсортированного массива в файл }
Rewrite(Output,'bubble.out');
for i:=1 to N-1 do Write(A[i],' ');
Writeln(A[N])
end.
Модификация с максимумами:
В этой сортировке мы пробегаем массив N раз, каждый раз перемещая в конец массива самый большой при сортировке по возрастанию (или самый маленький при сортировке по убыванию) элемент.
Шаги алгоритма:
- Считываем исходный массив в память.
- Переносим в N-ый элемент максимум среди элементов 1..N.
- Переносим в N-1-ый элемент максимум среди 1..N-1.
- и так далее (делаем это N раз).
- Теперь массив отсортирован, выводим его.
{$APPTYPE CONSOLE}
var
N : Integer; { Количество элементов в массиве }
A : array [1..5000] of Integer; { Сортируемый массив }
i,j : Integer; { Переменные цикла }
temp : Integer; { Переменная для обмена местами двух элементов в массиве }
begin
{ Ввод исходного массива из файла }
...
{ Сортировка }
for i:=N downto 1 do { A[i] должно быть больше чем все A[j] слева от него }
for j:=1 to i-1 do { Проверяем все A[j] }
if A[j] > A[i] then begin { Если какое-то A[j] больше чем A[i], то меняем их местами }
temp := A[i]; { Меняем элементы местами при помощи временной переменной temp }
A[i] := A[j];
A[j] := temp;
end;
{ Вывод отсортированного массива в файл }
...
end.
Другой вариант, легче для запоминания:
{ Сортировка }
for i := 1 to N-1 do
for j := i+1 to N do
if A[j] < A[i] then begin
temp:=A[i]; { Меняем элементы A[i] и A[j] местами }
A[i]:=A[j];
A[j]:=temp;
end;
Ну или можно вообще не запоминать как меняются индексы и писать i от 1 до N и j от 1 до N.
Менять местами элементы можно без использования временной переменной, сложениями/вычитаниями (и - исходное значение):
$A_j'=A_i+A_j$;
$A_i'=A_j'-A_i=A_i+A_j-A_i=A_j$;
$A_j''=A_j'-A_i'=A_i+A_j-A_j=A_i$
A[j] := A[i] + A[j]; { A[j] := A[i]_и + A[j]_и }
A[i] := A[j] - A[i]; { A[i] := A[i]_и + A[j]_и - A[i]_и = A[j]_и }
A[j] := A[j] - A[i]; { A[j] := A[i]_и + A[j]_и - A[j]_и = A[i]_и }
Или при помощи операции XOR (используя $x \oplus x =0$):
$A_i'=A_i \oplus A_j$;
$A_j'=A_i' \oplus A_j = A_i \oplus A_j \oplus A_j = A_i$;
$A_i''=A_i' \oplus A_j'= A_i \oplus A_j \oplus A_i = A_j$
A[i] := A[i] xor A[j]; A[j] := A[i] xor A[j]; A[i] := A[i] xor A[j];
Сортировка подсчётом
Когда диапазон чисел которые нужно отсортировать невелик по сравнению с их количеством, проще (и быстрее всего) посчитать количество элементов каждого вида прямо при чтении входного файла и вывести их "по видам".
{$APPTYPE CONSOLE}
var
N : Integer; { Количество элементов в массиве }
Ai : Integer; { Элементы сортируемого массива }
P : array [1..1000] of Integer; { P[i] - количество элементов со значением i }
i : Integer; { Переменная цикла }
begin
{ Ввод исходного массива из файла }
Reset(Input,'sort.in');
Read(N); { Читаем количество элементов в массиве }
for i:=1 to N do begin
Read(Ai); { Читаем элементы массива }
{ Считаем количество элементов каждого вида прямо при чтении файла }
P[Ai] := P[Ai] + 1; { Увеличиваем P[Ai] - количество элементов равных Ai }
end;
{ Вывод отсортированного массива в файл }
Rewrite(Output,'sort.out');
for Ai:=1 to 1000 do { Пробегаем по всем возможным значениям }
for i:=1 to P[Ai] do { Выводим P[Ai] элементов Ai }
Write(Ai,' ');
end.
"Быстрая сортировка" QuickSort
Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем $O(n \log n)$ обменов при упорядочении $n$ элементов).
Описание алгоритма:
- выбрать элемент, называемый опорным.
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
- повторить рекурсивно для «меньших» и «больших».
var A : array [1..1000000] of Integer; { Сортируемый массив }
procedure QuickSort( left,right : Integer );
var i,j : Integer; m,temp: Integer;
begin
i := left;
j := right;
m := A[(left + right) div 2]; { Медиана }
m := A[random(right-left+1) + left]; { Рандомизированный вариант QuickSort }
{ При выборе разделяющего элемента случайным образом практически невозможно попасть на худший случай }
repeat
while A[i] < m do inc(i);
while m < A[j] do dec(j);
if i<=j then begin
{ Меняем A[i] и A[j] местами }
temp := A[i];
A[i] := A[j];
A[j] := temp;
inc(i); dec(j);
end;
until i>j;
if left < j then QuickSort(left,j); { Сортировка левого куска }
if i < right then QuickSort(i,right); { Сортировка правого куска }
end;
var
N : Integer; { Количество элементов в массиве }
i : Integer; { Переменная цикла }
begin
{ Ввод исходного массива из файла }
Reset(Input,'bubble.in');
Read(N); { Читаем количество элементов в массиве }
for i:=1 to N do Read(A[i]); { Читаем сам массив }
{ Сортировка элементов с 1 по N }
QuickSort(1, N);
{ Вывод отсортированного массива в файл }
Rewrite(Output,'bubble.out');
for i:=1 to N-1 do Write(A[i],' ');
Writeln(A[N]);
end.
Реализация на C/C++
#include <stdio.h>
#include <iostream>
using namespace std;
// Сортируемый массив
int A[1000000];
// Случайное целое число в заданном диапазоне
int rand(int low, int high){
return rand() % (high - low + 1) + low;
}
// Поменять местами 2 элемента массива i-ый и j-ый
void swap(int i, int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// Быстрая сортировка от элемента left до элемента right
void qsort(int left, int right){
// Массивы из 1-ого элемента сортировать незачем
if(left >= right) return;
int l = left, r = right; // Левая и правая границы
// Выбираем разделяющий элемент - может быть любым,
// но выбор случайного элемента устойчив к худшим случаям
int m = A[rand(left,right)];
do {
while(A[l] < m) l++; // Двигаем левую границу
while(A[r] > m) r--; // Двигаем правую границу
if(l <= r){ swap(l,r); l++; r--; } // Меняем элементы местами
} while (l <= r);
qsort(left,r); // Сортируем левую половину массива
qsort(l,right); // Сортируем правую половину массива
}
int main(){
freopen("qsort.in","r",stdin);
freopen("qsort.out","w",stdout);
// Ввод исходных данных
int N;
cin >> N;
for(int i=0;i<N;i++) cin >> A[i];
// Сортировка
qsort(0,N-1);
// Вывод отсортированного массива
for(int i=0;i<N;i++) cout << A[i] << " ";
// Код возврата
return 0;
}
Самая короткая рекурсивная реализация QSort на Python
# -*- utf-8 -*-
# Различные реализации QSort (сортировки Хоара)
from random import *
def qsort(A):
""" Самая коротка рекурсивная реализация qsort на Python """
# Если длина массива 0 или 1, то сразу возвращаем его как есть
if len(A) <= 1:
return A
# Выбираем разделяющий элемент
y = choice(A)
# Делим массив на три куска и вызываем qsort для них
return qsort([x for x in A if x < y]) + [x for x in A if x == y] + qsort([x for x in A if x > y])
# Генерируем случайный массив
A = [randint(-10 ** 10, 10 ** 10) for i in range(100000)]
assert qsort(A) == sorted(A)
Сортировка слиянием - MergeSort
Алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
3 этапа алгоритма:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
#include <assert.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
const int N = 100000; // Количество элементов в массиве
int A[N]; // Сортируемый массив
int T[N]; // Временный массив - буфер
// left - левая граница сортируемого участка
// right - правая граница
void MergeSort( int left, int right ){
// Если в массиве один элемент - сортировать нечего => сразу выходим
if(left >= right) return;
// Делим массив на 2 равные половинки
int m = (left + right) / 2; // Среднее арифметическое
MergeSort(left,m); // Сортируем левую половину
MergeSort(m+1,right); // Сортируем правую половину
// Объединяем результаты - операция Merge (слияние)
int l = left, r = m+1;
for(int i = left; i< = right; i++){
if(l > m) // Если левая половинка кончилась, то берём только из правой
T[i] = A[r++];
else if(r > right) // Если правая половинка кончилась, то берём только из правой
T[i] = A[l++];
else if(A[l] < A[r]) // Если обе не кончились, то берём минимальный элемент
T[i] = A[l++];
else
T[i] = A[r++];
}
// Копируем обратно из временно буфера в A
for(int i = left; i<=right; i++)
A[i] = T[i];
// Проверка, что всё верно отсортировано
for(int i = left; i< = right-1; i++)
assert( A[i] <= A[i+1] );
}
int main() {
// Заполняем случайным числами массив A
for(int i=0;i<N;i++) A[i] = rand() % 1000;
// Вызов сортировки всех элементов
MergeSort(0,N-1);
// Вывод отсортированного массива
for(int i=0;i<N;i++) cout << A[i] << " ";
cout << endl;
return 0;
}
Вариант с использованием шаблонов:
// a - сортируемый массив, его левая граница lb, правая граница ub
template<class T>
void mergeSort(T a[], long lb, long ub) {
long split; // индекс, по которому делим массив
if (lb < ub) { // если есть более 1 элемента
split = (lb + ub)/2; // Центр обрабатываемого куска массива
mergeSort(a, lb, split); // сортировать левую половину
mergeSort(a, split+1, last);// сортировать правую половину
merge(a, lb, split, ub); // слить результаты в общий массив
}
}
template<class T>
void merge(T a[], long lb, long split, long ub) {
// Слияние упорядоченных частей массива в буфер temp
// с дальнейшим переносом содержимого temp в a[lb]...a[ub]
// текущая позиция чтения из первой последовательности a[lb]...a[split]
long pos1=lb;
// текущая позиция чтения из второй последовательности a[split+1]...a[ub]
long pos2=split+1;
// текущая позиция записи в temp
long pos3=0;
T *temp = new T[ub-lb+1];
// идет слияние, пока есть хоть один элемент в каждой последовательности
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] < a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}
// одна последовательность закончилась -
// копировать остаток другой в конец буфера
while (pos2 <= ub) // пока вторая последовательность непуста
temp[pos3++] = a[pos2++];
while (pos1 <= split) // пока первая последовательность непуста
temp[pos3++] = a[pos1++];
// скопировать буфер temp в a[lb]...a[ub]
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
delete temp[ub-lb+1];
}
Реализация на Delphi
var
N : integer; { Количество элементов }
A, T: array [1 .. 1000000] of integer; { Сортируемый массив }
Inversions: int64 = 0; { Для подсчёта числа инверсий }
procedure MSort(l, r: integer);
var
e, i, j, k: integer;
begin
if l >= r then
exit;
k := (l + r) div 2; { Средний элемент }
MSort(l, k);
MSort(k + 1, r);
i := l; { Первая половина массива }
j := k + 1; { Вторая половина массива }
{ Слияние }
for e := l to r do begin { Куда записываем результат }
if i > k then begin
T[e] := A[j];
Inc(j);
Inc(Inversions,k-i+1); { Подсчёт инверсий }
end else if j > r then begin
T[e] := A[i];
Inc(i);
end else if A[i] <= A[j] then begin
T[e] := A[i];
Inc(i);
end else begin
T[e] := A[j];
Inc(j);
Inc(Inversions,k-i+1); { Подсчёт инверсий }
end;
end;
{ Обратное копирование из T }
for e := l to r do
A[e] := T[e];
end;
Heap - куча
Бинарное дерево - у каждого родителя максимум 2 потомка
Предок: $Parent = \frac{i}{2}$. Потомки: левый $l = 2i$, правый $r = 2i+1$.
Основное свойство кучи, любая функция, которая допускает линейное упорядочивание.
HeapSort - сортировка при помощи кучи
{$APPTYPE CONSOLE}
uses SysUtils;
var
N : integer; { Размер кучи }
A : array [1..1000000] of int64;
size : Integer;
{ Обмен местами элементов с индексами i и j }
procedure Swap( i,j : integer );
var T : int64;
begin
T := A[i];
A[i] := A[j];
A[j] := T;
end;
procedure Heapify( i:integer );
var r,l : integer;
begin
l := i*2; { Левый потомок }
r := i*2+1; { Правый потомок }
if l <= N then
if A[l] > A[i] then begin
Swap(l,i);
Heapify(l);
end;
if r <= N then
if A[r] > A[i] then begin
Swap(r,i);
Heapify(r);
end;
end;
{ Построение кучи }
procedure BuildHeap;
var i: integer;
begin
for i := N downto 1 do
Heapify(i);
end;
{ Сортировка кучей }
procedure HeapSort;
begin
BuildHeap;
size := N;
while N > 1 do begin
Swap(N,1); { Меняем местами максимальный элемент и элемент в конце кучи }
Dec(N); { Уменьшаем кучу }
Heapify(1); { Восстанавливаем основное свойство кучи }
end;
end;
var i : integer;
begin
Reset(Input,'heapsort.in');
Rewrite(Output,'heapsort.out');
{ Чтение исходных данных }
Read(N);
for i := 1 to N do
Read(A[i]);
{ Вызов сортировки }
HeapSort;
{ Запись отсортированного массива }
for i := 1 to size do
Write(A[i],' ');
end.
#include <assert.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
const int N = 80;
// Массив, который на время станет двоичной кучей, чтобы потом стать отсортированным массивом
int A[N];
// Текущий размер кучи, т.е. сколько первых элементов массива A сейчас являются двоичной кучей
int HeapSize;
// Поменять местами 2 элемента массива i-ый и j-ый
inline void swap(int i, int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// Выполняется ли основное свойство кучи?
bool heap_function(int parent, int child){
return A[parent] > A[child];
}
// Мы хотим сверху получить самый минимум
// parent - корневой элемент
// Мы обновили элемент parent и хотим чтобы куча снова была кучей
void heap(int parent){
// -= Левый потомок =-
int left = 2*parent + 1;
if(left < HeapSize) // Левый потомок есть
if(!heap_function(parent,left)){ // Проверка основного свойства кучи
// Меняем их местами
swap(left,parent);
heap(left); // Проталкиваем значение дальше
}
// -= Правый потомок =-
int right = 2*parent + 2;
if(right < HeapSize) // Правый потомок есть
if(!heap_function(parent,right)){ // Проверка основного
// Меняем их местами
swap(right,parent);
heap(right);
}
}
void HeapSort(){
HeapSize = N;
// Строим кучу
for(int i=N-1;i>=0;i--)
heap(i);
// Выводим очередной элемент
for(int i=0;i<N;i++){
// Ставим элемент с вершины кучи в конец массива
swap(0,HeapSize-1);
// Уменьшаем кучу
HeapSize--;
// Упорядочиваем вершину кучи
heap(0);
}
// Проверяем, что массив отсортирован
for(int i=0;i<N-1;i++)
assert( A[i] <= A[i+1] );
}
int main() {
// Заполняем случайным числами массив A
for(int i=0;i<N;i++) A[i] = rand() % 1000;
// Вызов сортировки
HeapSort();
// Вывод отсортированного массива
for(int i=0;i<N;i++) cout << A[i] << " ";
cout << endl;
return 0;
}
Алгоритмы сортировки в стандартных библиотеках
Использование qsort в C/C++
В C/C++ в STL (Standard Template Library, которую, как правило, можно использовать на олимпиадах) доступна библиотека algorithm в которой в числе прочего есть реализованная процедура сортировки sort.
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define MaxN 5000 using namespace std; int a[MaxN + 3]; int n; int main() { freopen("bubble.in", "rt", stdin); // Открываем входной файл freopen("bubble.out", "wt", stdout); // Открываем выходной файл // Чтение исходных данных scanf("%d", &n); // Чтение количества элементов int i; for(i = 0; i < n; i++) scanf ("%d", &a[i]); // Вызов процедуры сортировки sort(a, a + n); // Вывод отсортированного массива в файл for(i = 0; i < n - 1; i++) printf("%d ", a[i]); printf("%d\n", a[n - 1]); return 0; }
В Python у списков (list) есть встроенный метод sort
# -*- coding: windows-1251 -*-
import sys
sys.stdin = open('bubble.in') # Открываем входной файл на чтение
sys.stdout = open('bubble.out', 'w') # Открываем выхолной файл на запись
# Ввод исходных данных
N = input() # Считываем из первой строки целое число
A = map(int,raw_input().split()) # Считываем строку, делим её на элементы и каждый приводим к типу целое
# Сортировка массива
A.sort()
# Вывод массива
for i in A:
print i,