Jump to content

Sorting algorithms/Strand sort: Difference between revisions

Sorting algorithms/Strand sort (view source)

Revision as of 02:33, 4 August 2012

97 bytes added ,  11 years ago
→‎{{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 sortpush(intslist *arl, intnode lene) {
if (!l->head) l->head = e;
{▼
if (l->tail) l->tail->next = e;
node_t all[len], head, shead, merged, *cur, *next, *stail;
l->tail = e;
}
 
node removehead(slist *l) {
/* linkify */
node e = l->head;
for (int i = 0; i < len; i++) {▼
if (e) {
all[i].v = ar[i];
all[i].nextl->head = all + i + 1e->next;
staile->next = 0;▼
}
return e;
all[len - 1].next = 0;
}
head.next = all;
shead.next = merged.next = 0;
 
void join(slist *a, slist *b) {
while (head.next) {
push(a, b->head);
/* take strand */
cur a->tail = &headb->tail;
}
stail = shead.next = head.next;
 
void merge(slist *a, slist *b) {
while (next = cur->next) {
slist r = {0};
if (next->v >= stail->v) {
while (a->head && b->head)
cur->next = next->next;
push(&r, removehead(a->head->v <= b->head->v ? a : b));
stail = stail->next = next;
} else
cur = next;
}
▲ stail->next = 0;
 
join(&r, a->head ? a : b);
/* merge */
len*a = 0r;▼
cur = merged.next;
b->head = b->tail = 0;
next = shead.next;
}
stail = &merged;
 
void sort(int *ar, int len)
▲{
node_t all[len];
 
// array to list
▲ for (int i = 0; i < len; i++) {
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);
/* while both lists contain elements, append the smaller one */
while (next && cur) {
if (next->v <= cur->v) {
stail = stail->next = next;
next = next->next;
} else {
stail = stail->next = cur;
cur = cur->next;
}
}
/* append the rest of the survivor to the end of merged */
stail->next = next ? next : cur;
}
 
cur = &merged;
// list to array
▲ len = 0;
whilefor (curint i = cur->next)0; res.head; ar[leni++], res.head = curres.head->v;next)
ar[i] = res.head->v;
}
 
void show(char *title, int *x, int len)
int main()▼
{
printf("\n%s ", title);▼
int x[] = {-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2};▼
for (int i = 0; i < SIZElen; i++) printf(" %3d", x[i]);▼
#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)
 
▲ printfshow("before sort:", x, SIZE);
sort(x, sizeof(x)/sizeof(int));
show("after sort: ", x, SIZE);
 
return 0;
printf("\nafter sort: ");
for (int i = 0; i < SIZE; i++) printf(" %3d", x[i]);
▲ 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>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/179367"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information