Sorting algorithms/Strand sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 10: / Line 10: @@
 typedef struct node_t *node, node_t;
 struct node_t { int v; node next; };
+typedef struct { node head, tail; } slist;
-void sort(int *ar, int len)
+void push(slist *l, node e) {
+	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].next = all + i + 1;
+		l->head = e->next;
+		e->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 = &head;
+	a->tail = b->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 */
+	*a = r;
-		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;
-	while (cur = cur->next) ar[len++] = cur->v;
+	for (int i = 0; res.head; i++, res.head = res.head->next)
+		ar[i] = res.head->v;
 }
+void show(char *title, int *x, int len)
-int main()
 {
+	printf("%s ", title);
-	int x[] = {-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2};
+	for (int i = 0; i < len; 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)
+	show("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>