«Ненормальная» сортировка — реализация алгоритма «блинной» сортировка

Бродя по просторам Википедии, читал статью о сортировках. Увидел невиданную для себя ранее — «блинную» сортировку. Гугление реализации на просторах рунета не помогло. Подумал, почему бы не реализовать самому? И вот моя статья здесь.

Немного о сабже

Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания. (см. wikipedia)

Идея реализации

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

Заметим, что такой подход делает алгоритм устойчивым, то есть при подаче на вход массива, не нуждающегося в сортировке, кол-во обменов будет == 0.

Собственно, реализация

Реализацию привожу на языке Си

Итак, для начала необходимо написать процедуру, исполняющую переворот элементов массива от индекса m до индекса n.
void flip(int *data, int m, int n)
{
int swap, i;

for(i = m; i < --n; i++) {
swap = data[i];
data[i] = data[n];
data[n] = swap;
}

}


Теперь пристуаем непосредственно к функции сортировки. Находим максимальный элемент и переворачиваем массив.

//Функция сортировки
int sort(int *data, size_t length)
{
int i, j, a, maxNumPos, moves = 0;

//Если длина массива меньше 2 (1 или 0) - сортировка не требуется.
if(length < 2)
return 0;

for(i = length; i > 1; i--) { // i - длина неотсортированной части
//Находим позицию максимального элемента
maxNumPos = 0;
for(a = 0; a < i; a++) {
if(data[a] > data[maxNumPos])
maxNumPos = a;
}

//Если максимальный элемент и так на своём месте - переходим на следующий шаг
if(maxNumPos == (i - 1))
continue;

//Получаем найденную макс. позицию для начала переворота
if(maxNumPos >= 0){
flip(data, maxNumPos, i); //Переворачиваем
moves++;

}

//Тогда всё выше list[i-1] упорядочено и больше не трогаем этот кусок
}

return moves;
}

Примеры.

5 4 3 2 1 9 8 6 7 — входной массив
5 4 3 2 1 7 6 8 9
5 4 3 2 1 6 7 8 9
1 2 3 4 5 6 7 8 9 — выходной массив, moves = 3

9 8 7 6 5 4 3 2 1 — входной массив
1 2 3 4 5 6 7 8 9 — выходной массив, moves = 1

1 2 3 4 5 6 7 8 9 — входной массив
1 2 3 4 5 6 7 8 9 — выходной массив, moves = 0

Резюме

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

Данная статья представлена лишь в ознакомительных целях, использовать или нет данный алгоритм — дело каждого.

Моя цель была лишь показать какие бывают алгоритмы сортировки, возможно я напишу и о других сортировках позднее.