Обменные сортировки

Сортировка пузырьком – простой в реализации и малоэффективный алгоритм сортировки.

Метод пузырька получил свое название за то, что "более весомые" элементы поднимаются в процессе сортировки к концу массива.

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

Например, пусть количество элементов N равно 5:

9, 1, 4, 7, 5

Вначале сравниваются два первых элемента: 9 и 1. Они меняются местами. Далее сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями.

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

Всего потребуется N*(N - 1) сравнений.

В частности, на данной последовательности произведено 20 сравнений и 5 перестановок.  

#include <iostream>

using namespace std;

Void BubbleSort(int *a, int n)

{ int c, i, j, k;

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

{ for (j = 0; j < N - 1; j++)

{ k = j + 1; c = A[k];

if (A[j] > A[k]) { A[k] = A[j]; A[j] = c; }

}

}

}

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

}

BubbleSort(A, N);

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

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

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

}

Можно void BubbleSort(int A[], int N)

Другой вид:

void BubbleSort(int B[], int n)  //сортировка пузырьком { int t;

for (int i = n - 1;  i > 0;  --i) for (int j = 0;  j < i;  ++j) if (B[j] > B[j + 1]) { t = B[j]; B[j] = B[j + 1]; B[j + 1]=t; }

}

Пример внешней сортировки. Пусть исходные данные нужно прочитать из файла "A.txt", где целые числа записаны через пробел. Результат записывается в массив A и выводится на экран.

#include <iostream>

using namespace std;

int A[100]; int N;

Void BubbleSort(int *a, int n)

{ int c, i, j, k;

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

{ for (j = 0; j < N - 1; j++)

{ k = j + 1; c = A[k];

if (A[j] > A[k]) { A[k] = A[j]; A[j] = c; }

}

}

}

Void main()

{ FILE *ft = fopen("A.txt", "r");

int i = 0;

while (!feof(ft))

{ fscanf(ft, "%d", &A[i]);

i++;

}

N = i - 1;

BubbleSort(A, N);

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

printf("%d ", A[i]);

}

Характеристики сортировки методом "пузырька": в худшем случае (когда элементы наиболее удалены от своих конечных позиций) выполняется n(n - 1) / 2 сравнений, т.е. примерно  n² / 2, и n(n - 1) / 2 перестановок

Сложность алгоритма – О(n²).

Сортировку пузырьком можно улучшить.

Шейкерная сортировка (перемешиванием)

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

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

Просмотр будет выполняться не до конца массива, а до последней перестановки на предыдущем просмотре. Тогда сильно удаленные от своего места элементы будут быстрее перемещаться на нужное место.

#include <iostream>

using namespace std;