Skip to content

Instantly share code, notes, and snippets.

@kotet
Created Jul 19, 2019
Embed
What would you like to do?
非再帰マージソート
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
typedef struct stack_element
{
int64_t *ptr;
size_t length;
int8_t state;
} stack_element_t;
stack_element_t make_stack_element(int64_t *ptr, size_t length, int8_t state)
{
return (stack_element_t){ptr, length, state};
}
enum
{
SPLIT,
MERGE,
};
void sort(int64_t *ary, size_t N)
{
// 3*log_2(x) < max(x,12)
stack_element_t *stack = malloc(sizeof(stack_element_t) * ((N < 16) ? 16 : N));
int64_t *buf = malloc(sizeof(int64_t) * N);
size_t depth = 0;
stack[depth++] = make_stack_element(ary, N, SPLIT);
while (depth)
{
stack_element_t current = stack[--depth];
size_t h = current.length / 2;
switch (current.state)
{
case SPLIT:
stack[depth++] = make_stack_element(current.ptr, current.length, MERGE);
if (2 <= current.length)
{
stack[depth++] = make_stack_element(current.ptr, h, SPLIT);
stack[depth++] = make_stack_element(current.ptr + h, current.length - h, SPLIT);
}
break;
case MERGE:
for (size_t i = 0; i < h; i++)
buf[i] = current.ptr[i];
size_t lhs = 0, rhs = h;
for (size_t i = 0; i < current.length; i++)
{
if (lhs < h && rhs < current.length)
current.ptr[i] = (buf[lhs] < current.ptr[rhs]) ? buf[lhs++] : current.ptr[rhs++];
else
current.ptr[i] = (lhs < h) ? buf[lhs++] : current.ptr[rhs++];
}
break;
default:
exit(1);
break;
}
}
free(stack);
free(buf);
}
int main(int argc, char const *argv[])
{
if (argc < 2)
{
puts("usage: ./merge 10");
exit(1);
}
size_t N = atoll(argv[1]);
int64_t *ary = malloc(sizeof(int64_t) * N);
srand(time(NULL));
for (size_t i = 0; i < N; i++)
{
ary[i] = rand() % N;
}
for (size_t i = 0; i < N; i++)
{
printf("%ld\t", ary[i]);
}
putchar('\n');
sort(ary, N);
for (size_t i = 0; i < N; i++)
{
printf("%ld\t", ary[i]);
}
putchar('\n');
free(ary);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment