lab4_sort/sort.c

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

#include "macro.h"

typedef void (*sorter_t)(int *arr, size_t sz);

typedef struct {
	const char *name;
	sorter_t func;
} sort_info_t;

/*
 * Написать сортировку вставками (не подглядывая в инторнеты!)
 * arr -- целочисленный массив
 * sz -- размер массива
 */
void
insert_sort(int *arr, size_t sz)
{
	int i, j, t;

	for (i = 1; i < sz; i++) {
		t = arr[i];
		j = i - 1;
        
		while (j >= 0) {
			if (arr[j] > t) {
				arr[j + 1] = arr[j];
				j--;
			} else {
				break;
			}
		}
		arr[j + 1] = t;
	}
}

void
bubble_sort(int *arr, size_t sz)
{
	int i, j;
	int tmp;

	for (i = 0; i < sz; i++) {
		for (j = i + 1; j < sz; j++) {
			if (arr[i] > arr[j]) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

/*
   Функция для слияния двух отсортированных
   массивов в один.

     a -- указывает на первый элемент первого массива
     b -- указывает на первый элемент второго массива
     end -- указывает на первый элемент за границами второго массива
   Результат записывается во временный массив tmp.
   Первый элемент в tmp[0], второй в tmp[1] и т.д.

  Пример
      массивы a = [1, 4, 5]
              b = [2, 3, 6]

    a                     b               end
    |                     |                |
   \/                    \/               \/
   |  1   |  4   |   5   |  2  |  3  |  6 |

   после вызова _merge в tmp должен получиться массив
   |  1   |  2   |   3   |  4  |  5  |   6 |

 */
static void
_merge(int *tmp, int *a, int *b, int *end)
{
	int k = 0;     // индекс для массива tmp
	int *p1 = a;   // указатель на начало первого кускf
	int *p2 = b;   // указатель на начало второго куска
	// Пока оба куска не закончились
	while (p1 < b && p2 < end) {
		if (*p1 <= *p2) {
			tmp[k] = *p1;
			p1++;
		} else {
			tmp[k] = *p2;
			p2++;
		}
		k++;
	}

	// Если остались элементы в первом куске
	while (p1 < b) {
		tmp[k] = *p1;
		p1++;
		k++;
	}

	// Если остались элементы во втором куске
	while (p2 < end) {
		tmp[k] = *p2;
		p2++;
		k++;
	}
}

static void
_merge_sort_int(int *tmp, int *arr, size_t n)
{
	int half = n / 2;	//индекс, который делит массивы пополам

	if (half > 1)
		_merge_sort_int(tmp, arr, half);
	if (n - half > 1)
		_merge_sort_int(tmp + half, arr + half, n - half);

	// "слить" два отсортированных массива в один
	_merge(tmp, arr, arr + half, arr + n);
	// Скопировать данные из временного хранилища в
	// оригинальный массив
	memcpy(arr, tmp, n * sizeof(*tmp));
}

void
merge_sort(int *arr, size_t sz)
{
	int *tmp;

	if (sz < 2)
		return;
	tmp = malloc(sizeof(*arr) * sz);
	assert(tmp);
	_merge_sort_int(tmp, arr, sz);
	free(tmp);
}

void
print_arr(int *arr, size_t n)
{
	printf("{");
	for (int i = 0; i < n; i++) {
		printf("%d, ", arr[i]);
	}
	printf("}\n");
}

#define _S(item) {#item, item}

bool
test_all()
{
	#include "test_arrays.h"
	TEST_ARR_INIT(testcases);

	sort_info_t sorters[] = {
		_S(insert_sort),
		//_S(bubble_sort),
		_S(merge_sort),
	};

	int *temparr = NULL;
	int temparr_len = 0;

	int allok = 1;

	for (int j = 0; j < ARRSZ(sorters); j++) {
		sort_info_t cursort = sorters[j];
		printf("[+] %s\n", cursort.name);

		for (int i = 0; i < ARRSZ(testcases); i++) {
			int len = testcases[i].len;

			printf("[+]    testing %s\n", testcases[i].name);
			if (len > temparr_len) {
				// TODO: EER????
				temparr_len = len;
				temparr = realloc(temparr, temparr_len * sizeof(*temparr));
				assert(temparr);
			}
			memcpy(temparr, testcases[i].unsorted, sizeof(*temparr) * len);
			cursort.func(temparr, len);
			int res = memcmp(temparr, testcases[i].sorted, sizeof(*temparr) * len);
			if (res != 0) {
				allok = 0;
				printf("[-] arrays does not match \n");
				printf("your\n");
				print_arr(temparr, len);
				printf("original\n");
				print_arr(testcases[i].sorted, len);
				break;
			}
		}
	}
	if (allok) {
		printf("[+] All OK!\n");
	}
	if (temparr)
		free(temparr);
	return allok == 1;
}

int
main(int argc, const char *argv[])
{
	test_all();
	return 0;
}