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

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

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

Сортировка перестановок происходит путем генерации возможных перестановок входного массива / списка до обнаружения отсортированной.

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

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

// https://bit.ly/2rcvXK5
#include  <stdio.h>  
#include <stdlib.h>
#include <string.h>
 
typedef int(*cmp_func)(const void*, const void*);
 
void perm_sort(void *a, int n, size_t msize, cmp_func _cmp)
{
	char *p, *q, *tmp = malloc(msize);
#	define A(i) ((char *)a + msize * (i))
#	define swap(a, b) {\
		memcpy(tmp, a, msize);\
		memcpy(a, b, msize);\
		memcpy(b, tmp, msize);	}
	while (1) {
		/* find largest k such that a[k - 1] < a[k] */
		for (p = A(n - 1); (void*)p > a; p = q)
			if (_cmp(q = p - msize, p) > 0)
				break;
 
		if ((void*)p <= a) break;
 
		/* find largest l such that a[l] > a[k - 1] */
		for (p = A(n - 1); p > q; p-= msize)
			if (_cmp(q, p) > 0) break;
 
		swap(p, q); /* swap a[k - 1], a[l] */
		/* flip a[k] through a[end] */
		for (q += msize, p = A(n - 1); q < p; q += msize, p -= msize)
			swap(p, q);
	}
	free(tmp);
}
 
int scmp(const void *a, const void *b) { return strcmp(*(const char *const *)a, *(const char *const *)b); }
 
int main()
{
	int i;
	const char *strs[] = { "spqr", "abc", "giant squid", "stuff", "def" };
	printf("Original Array:\n");
	int n =5;
    for (i = 0; i < n; i++)
    printf("%s   ", strs[i], i == n - 1 ? "\n" : " ");  
	perm_sort(strs, 5, sizeof(*strs), scmp);    
    printf("\nSorted Array:\n");
	for (i = 0; i < 5; i++)
		printf("%s   ", strs[i]);
	return 0;
}

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

 Оригинальный массив:
spqr abc гигантский кальмар   
Сортированный массив:
abc def гигантский кальмар spqr материал  

Блок - схема:

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

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

Предыдущий: Напишите программу на C, которая сортирует числа, используя метод Cycle Sort.
Следующая: C Array Упражнения Home