Другие алгоритмы сортировки массивов
Мы рассмотрели 2 алгоритма сортировки- простой интуитивный и быстрый рекурсивный (quick sort). Простой интуитивный называется сортировкой выбором или selection sort. Но есть и много других алгоритмов сортировки, самые типовые и рассматриваемые из них я тут приведу. Можно делать сразу с шаблонами типов переменных, но для простоты понимания мы рассмотрим массивы с целыми числами. Потом, при желании, можно добавить шаблоны.
Сортировка пузырьком ( bubble sort)
Сортировка пузырьком является первой сортировкой, которую вообще изучают, она является простой и медленной. Рассмотрим на примере сортировки массива по возрастанию. Исходный массив: 4 3 5 2
Проверяем: 4>3 ? нет, тогда меняем местами. 3 4 5 2.
Дальше: 5 > 4 ? да, тогда оставляем.
И так далее. Когда прошли весь массив, начинаем заново. Процесс продолжается до тех пор, пока весь массив будет не отсортирован:
(4) (3) (5) (2) // исходный
(3) (4) (5) (2)
(3) (4) (5) (2)
(3) (4) (2) (5) -> в начало массива
(3) (4) (2) (5)
(3) (2) (4) (5)
(3) (2) (4) (5) -> в начало
(2) (3) (4) (5)
(2) (3) (4) (5)
(2) (3) (4) (5) -> массив отсортирован, поэтому выходим из цикла
Отсортированность массива мы будем проверять благодаря логическим переменным. Например если перестановок больше за весь проход массива не происходит, то значит массив уже отсортирован и пора бы из цикла выходить.
Ниже код алгоритма пузырьковой сортировки:
void bubblesort (int mass[], int size) {
int buf; // буферная переменная для перемены мест
|
|
|
bool per_is_going= false; // суммарно- были ли перестановки вообще
do {
per_is_going= false; // обнуляем- перестановок не было
for (int j=0; j<size-1; j++) {
// если текущий элемент больше следующего, то мы меняем эти 2 элемента местами, т.к. у нас сортировка по возрастанию
if (mass[j] > mass [j+1]) {
buf= mass[j];
mass[j]= mass[j+1];
mass[j+1]= buf;
// учёт перестановки
per_is_going+= true;
}
}
} while (per_is_going); // цикл продолжается пока хоть какие-то перестановки происходят
}
Пример использования:
int m[11]= {3,2,5,7,1,6,6,2,2,1,2};
bubblesort(m,11);
for (int i=0; i<11; i++) cout << m[i] << " ";
Шейкерная сортировка ( cocktail sort)
Или по-другому называется "сортировка перемешиванием". Является усовершенствованием пузырьковой сортировки в том смысле, что массив сортируется с 2 сторон.
|
|
|
void cocktailsort (int a[], int size) {
bool sort_or_not= true;
int right = size;
int left = 1;
do {
sort_or_not = true;
for (int i= left; i <= right; i++) {
if (a[i-1] > a[i]) {
swap (a[i-1], a[i]);
sort_or_not= false;
}
}
right--;
for (int i= right; i >= left; i--) {
if (a[i] < a[i-1]) {
swap (a[i], a[i-1]);
sort_or_not = false;
}
}
left++;
} while (!sort_or_not);
}
Кстати, функция swap, которая меняет местами 2 элемента, уже встроена и кроме iostream подключать ничего не пришлось.
Можно самому написать эту функцию с шаблоном:
template <typename Type>
void swap (Type &a, Type &b) {
Type c= a; a= b; b= c;
}
Её использование упрощает алгоритмы и программы.
Сортировка вставками ( insertion sort)
В данной сортировке мы вставляем каждый новый элемент на то место, чтобы массив был отсортирован. К примеру, есть у нас массив (4) (7) (1) (0) (5) и мы его хотим отсортировать по возрастанию. Создаём новый пустой массив такого же размера и помещаем первый элемент. Далее каждый следующий положим в нужное место:
(4)
(4) (7)
(1) (4) (7)
(0) (1) (4) (7)
(0) (1) (4) (5) (7)
В какое именно место класть, можно понять на примере. У нас есть (0) (1) (4) (7) и надо положить (5). Мы будем проверять (0) > (5) ? нет. И т.д. пока не дойдём до (7) > (5) ? да. Ну тогда ставим перед семёркой. Это был упрощённый пример для понимания принципа.
|
|
|
Ниже код с более совершенным алгоритмом, где левая часть массива будет отсортированной, а из правой части массива мы будем вставлять элементы в левую, таким образом сортируя весь массив:
void insertionsort(int a[], int size) {
int buf; // то что мы будем вставлять
// цикл прохода по исходному массиву
for (int i=1, j; i<size; i++) {
buf= a[i]; // берём первый левый элемент из неотсортированной части массива
// поиск места куда вставить и сдвиг неотсортированных элементов вправо (по циклу проходимся справа налево)
for (j= i-1; j>=0 && a[j]>buf; j--) a[j+1]= a[j];
a[j+1]= buf; // вставка в нужное место
}
}
Сортировка Шелла
Это некая модификация сортировки простыми вставками. Алгоритм достаточно сложный, поэтому комментировать и копаться я в нём не буду, это просто для ознакомления, что такой алгоритм вообще есть, и использования. Ниже весь алгоритм:
// вспомогательная функция
int increment(int inc[], int size) {
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s= -1;
do {
if (++s % 2) inc[s]= 8*p1 - 6*p2 + 1;
else {
inc[s]= 9*p1 - 9*p3 + 1; p2 *= 2; p3 *= 2;
}
p1*=2;
}
while(3*inc[s] < size);
return s>0 ? --s : 0;
}
// сама сортировка
|
|
|
void shellsort(int a[], int size) {
int inc, i, j, seq[40];
int s;
s= increment(seq, size);
while (s>=0) {
inc= seq[s--];
for (i=inc; i<size; i++) {
int temp= a[i];
for (j=i; (j>=inc) && (temp < a[j-inc]); j-=inc) {
a[j]= a[j-inc];
}
a[j]= temp;
}
}
}
Пирамидальная сортировка
Тоже малоизвестный и сложный для понимания алгоритм, поэтому я просто приведу рабочий и немного отредактированный код. При желании его можно разобрать.
// вспомогательная функция
void downHeap(int a[], int k, int n) {
int new_elem;
int child;
new_elem= a[k];
while(k <= n/2) {
child= 2*k;
if (child<n && a[child]<a[child+1]) child++;
if (new_elem >= a[child]) break;
a[k] = a[child];
k = child;
}
a[k] = new_elem;
}
// сама сортировка
void heapSort(int a[], int size) {
int i; int temp;
for(i= size/2 - 1; i>=0; i--) downHeap(a, i, size-1);
for(i= size-1; i>0; i--) {
temp= a[i]; a[i]= a[0]; a[0]= temp;
downHeap(a, 0, i-1);
}
}
Этот алгоритм уже быстрее рассмотренных ранее. Если у "типовых" алгоритмов скорость была O(n*n), то тут уже O(n*log(n))
Дата добавления: 2018-09-22; просмотров: 222; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!