Anonymous user
Sorting algorithms/Strand sort: Difference between revisions
→{{header|C}}: modularize, sort of
m (Sort Clojure < CMake < Common Lisp < D.) |
(→{{header|C}}: modularize, sort of) |
||
Line 10:
typedef struct node_t *node, node_t;
struct node_t { int v; node next; };
typedef struct { node head, tail; } slist;
void
if (!l->head) l->head = e;
{▼
if (l->tail) l->tail->next = e;
l->tail = e;
}
node removehead(slist *l) {
node e = l->head;
for (int i = 0; i < len; i++) {▼
if (e) {
}
return e;
}
void join(slist *a, slist *b) {
push(a, b->head);
}
void merge(slist *a, slist *b) {
slist r = {0};
while (a->head && b->head)
push(&r, removehead(a->head->v <= b->head->v ? a : b));
▲ stail->next = 0;
join(&r, a->head ? a : b);
b->head = b->tail = 0;
}
void sort(int *ar, int len)
▲{
node_t all[len];
// array to list
all[i].v = ar[i], all[i].next = i < len - 1 ? all + i + 1 : 0;
slist list = {all, all + len - 1}, rem, strand = {0}, res = {0};
for (node e = 0; list.head; list = rem) {
rem.head = rem.tail = 0;
while ((e = removehead(&list)))
push((!strand.head || e->v >= strand.tail->v) ? &strand : &rem, e);
merge(&res, &strand);
}
// list to array
▲ len = 0;
ar[i] = res.head->v;
}
void show(char *title, int *x, int len)
int main()▼
{
int x[] = {-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2};▼
#define SIZE sizeof(x)/sizeof(int)▼
printf("%3d ", x[i]);
putchar('\n');
}
▲int main(void)
printf("before sort:");▼
{
▲ for (int i = 0; i < SIZE; i++) printf(" %3d", x[i]);
▲ int x[] = {-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2};
▲# define SIZE sizeof(x)/sizeof(int)
sort(x, sizeof(x)/sizeof(int));
show("after sort: ", x, SIZE);
return 0;
▲ printf("\n");
}</lang>outout<lang>before sort: -2 0 -2 5 5 3 -1 -3 5 5 0 2 -4 4 2
after sort: -4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5</lang>
|