Алгоритмы сортировки. Gnome Sort на Си

Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).

Алгоритм гномьей сортировки разработан, по словам официального автора(Дика Груна), гномами, которые сортировали садовые горшки. Правда это или нет, но алгоритм очень прост, особенно для начинающих. По сути, в алгоритме сравниваются рядом стоящие горшки, если они стоят в нужном порядке, тогда мы переходим на следующий элемент массива, если нет, ты мы их переставляем и переходим на предыдущий. Нету предыдущего элемента — идём вперед, нету следующего — значит мы закончили. Изначально мы находимся на втором элементе массива.

Приступим к реализации на Си. Я думаю, что со вводом и выводом массива ни у кого проблем не будет:

#include <stdio.h>
#include <stdlib.h>

size_t n = 0; // размер сортируемого массива
long *arr = NULL; // сортируемый массив

void Read()
{
	size_t i;
	printf("Array size: ");
	scanf("%u", &n);
	
	arr = (long*)calloc(n, sizeof(long));

	printf("Array: ");
	for (i = 0; i < n; i++) {
		scanf("%d", &(arr[i]));
	}
}

void Do()
{
         // сортировка
}

void Write()
{
	size_t i;

	printf("Result: ");
	for (i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void main()
{
	Read();
	Do();
	Write();
}

Итак, сама сортировка. В начале инициализируем счётчик i типа size_t еденицой. Пишем цикл while с условием i < n:

void Do()
{
         // сортировка
         size_t i = 1;

         while (i < n) {
	 }
}

Теперь цикл. Если мы в начале, то идём вперед(if (i == 0) i = 1;). Если мы в конце, то ничего не пишем, т.к. сработает условие цикла. Если данный элемент равен или превышает предыдущий, тогда вперёд. В другом случае меняем элементы местами и идём назад.

Итого готовая программа для сортировки:

#include <stdio.h>
#include <stdlib.h>

size_t n = 0;
long *arr = NULL;

void Read()
{
	size_t i;
	printf("Array size: ");
	scanf("%u", &n);
	
	arr = (long*)calloc(n, sizeof(long));

	printf("Array: ");
	for (i = 0; i < n; i++) {
		scanf("%d", &(arr[i]));
	}
}

void Do()
{
	// сортировка
	size_t i = 1; // счётчик

	while (i < n/*если мы не в конце*/) {
		if (i == 0) {
			i = 1;
		}
		if (arr[i-1] <= arr[i]) {
			++i; // идём вперед
		} else {
			// меняем местами
			long tmp = arr[i];
			arr[i] = arr[i-1];
			arr[i-1] = tmp;
			// идём назад
			--i;
		}
	}
}

void Write()
{
	size_t i;

	printf("Result: ");
	for (i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void main()
{
	Read();
	Do();
	Write();
}