-6
\$\begingroup\$

I kinda stumbled upon this new sorting algorithm a few weeks ago and I would appreciate some pointers on how to improve the code (Since I'm a a novice c++ programmer. Been only programming in c++ for a few months) or maybe a completely different approach to implement strand sort.

#include <stdio.h>

typedef struct node_t *node, node_t;

struct node_t 
{
    int v;
    node next;
};

typedef struct 
{
    node head,
    tail;
} slist;

void push(slist *l, node e)
{
    if (!l->head) l->head = e;
    if (l->tail)  l->tail->next = e;
    l->tail = e;
}

node removehead(slist *l)
{
    node e = l->head;
    if (e) 
    {
        l->head = e->next;
        e->next = 0;
    }
    return e;
}

void join(slist *a, slist *b)
{
    push(a, b->head);
    a->tail = b->tail;
}

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));

     join(&r, a->head ? a : b);
     *a = r;
     b->head = b->tail = 0;
 }

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);
    }

    // list to array
    for (int i = 0; res.head; i++, res.head = res.head->next)
        ar[i] = res.head->v;
}

//function to print the array of items
void show(const char *title, int *x, int len)
{
    printf("%s ", title);
    for (int i = 0; i < len; i++)
        printf("%3d ", x[i]);
    putchar('\n');
}

//driver function to test the algorithm
int main(void)
{
    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;
}

I would like suggestions of any kind to improve the code be it with respect to the syntax or the logic of the program or suggestions to improve the efficiency of the program or to make it run faster.

\$\endgroup\$
  • 4
    \$\begingroup\$ Voting to close as the code submitted is from RosettaCode and therefore is off-topic. See diff. Also, why not just copy the C++ code? \$\endgroup\$ – Snowhawk Jun 28 '17 at 21:36
1
\$\begingroup\$
  • Do not typedef the pointer. It creates more problems than it solves. Also, declare each variable on its own line. In any case, don't do

        node head,
        tail;
    

    It is very hard to read.

  • Avoid naked loops. Every loop implements some (possibly important) algorithm, which deserves a name. Especially if you feel obliged to explain it in the comment. Consider array_to_list and list_to_array functions.

    Similarly, the loop

        while ((e = removehead(&list)))
            push((!strand.head || e->v >= strand.tail->v) ? &strand : &rem, e);
    

    (greedily) extracts a sorted sorted sublist into strand, and keeps the remaining in rem. An extract_sorted_sublist function would explain your intent more clearly.

  • The

        (!strand.head || e->v >= strand.tail->v) ? &strand : &rem
    

    is pretty much unreadable. Besides, !strand.head is satisfied only once, at the very first iteration of the loop. Better make it explicit:

        node_t * e = removehead(&list);
        push(&strand, e);
        while ((e = remove head(&list))) {
            push((e->v >= strand.tail.v)? &strand: &rem, e);
        }
    

    I also recommend to not use ternary here.

    Along the same lines, it is not necessary to initialize e in the loop header.

  • In a list context removehead is conventionally known as pop.

  • Performance wise, the algorithm is inherently quadratic, and I don't see how you can do better while keeping the algorithm.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.