Упражнения C: Сортировка чисел с использованием метода Сортировка коктейлей

Алгоритм поиска и сортировки при программировании на C: упражнение 15 с решением

Напишите программу на C, которая сортирует числа, используя метод Cocktail Sort.

Коктейльный шейкер (также известный как двунаправленная пузырьковая сортировка, коктейльная сортировка, шейкерная сортировка, пульсация, случайная сортировка или челночная сортировка) - это разновидность пузырьковой сортировки, которая является одновременно алгоритмом стабильной сортировки и сравнительной сортировкой. Алгоритм отличается от пузырьковой сортировки тем, что он сортирует в обоих направлениях при каждом проходе по списку. Этот алгоритм сортировки лишь немного сложнее в реализации, чем пузырьковая сортировка, и он решает проблему черепах в пузырьковых видах. Он обеспечивает лишь незначительные улучшения производительности и не улучшает асимптотическую производительность; Подобно пузырьковому типу, он не представляет практического интереса, хотя и находит некоторое применение в образовании.

Визуализация типа шейкера :

Пример решения:

Образец кода C:

// https://bit.ly/2rcvXK5
#include  <stdio.h>  
// can be any swap function. This swap is optimized for numbers.
void swap(int *x, int *y) {
	if(x == y)
		return;
	*x ^= *y;
	*y ^= *x;
	*x ^= *y;
}
void cocktailsort(int *a, size_t n) {
	while(1) {
		// packing two similar loops into one
		char flag;
		int it, i;
		size_t start[2] = {1, n - 1},
			   end[2] = {n, 0},
			   inc[2] = {1, -1};
		for(it = 0; it < 2; ++it) {
			flag = 1;
			for(i = start[it]; i != end[it]; i += inc[it])
				if(a[i - 1] > a[i]) {
					swap(a + i - 1, a + i);
					flag = 0;
				}
			if(flag)
				return;
		}
	}
}
 
int main(void) {
	int a[] = { 5, -1, 101, -4, 0, 1, 8, 6, 2, 3 };
	int i;
	size_t n = sizeof(a)/sizeof(a[0]);
    printf("Original Array:\n");
    for (i = 0; i < n; i++)
    printf("%d%s", a[i], i == n - 1 ? "\n" : " ");  
    printf("\nSorted Array:\n");
	cocktailsort(a, n);
	for ( i = 0; i < n; ++i)
		printf("%d ", a[i]);
	return 0;
}

Пример вывода:

 Оригинальный массив:
5 -1 101 -4 0 1 8 6 2 3
Сортированный массив:
-4 -1 0 1 2 3 5 6 8 101 

Блок - схема:

Редактор кода программирования C:

Улучшите этот пример решения и опубликуйте свой код через Disqus.

Предыдущий: Напишите программу на C, которая сортирует числа, используя метод сортировки Bogo.
Далее: Напишите программу на C, которая сортирует числа, используя метод Cycle Sort.