Sorting 2 linked list of 50000 numbers with a limited set of operations

Question

So I have this project for school : I have a linked list of 50 000 numbers and a second empty list. I only have a very limited panel of instructions. They are :

• "sa" swaps the first two elements of list 1

• "sb" swaps the first two elements of list 2

• "ss" is "sa" and "sb" at the same time

• "pa" : push top element of list 2 on top of list 1

• "pb": push top element of list 1 on top of list 2

• "ra": rotate list 1 (first element becomes last)

• "rb":rotate list 2 (first becomes last)

• "rr": "ra"and "rb" at once

• "rra": rotate list 1 (last becomes first)

• "rrb": rotate list 2(last becomes first)

• "rrr": "rra" and "rrb" at once

I have to implement a sorting algorithm in c and the goal is to do it with the smallest amount of instructions. I tried with a very simple algorithm that rotated list one until the maximum was on top and then pushed it in list 2 repeatedly until everything was in list 2 and then pushed everything back in list 1, but I was not able to sort lists of more than 5k numbers in a reasonable amount of time

Answer 1

I think I've figured out how to do this using quick sort. Here's some pseudocode.

edit: updated pseudocode to focus on what it's doing and not unnecessary syntax

quicksort(int n)
    if n == 1 return
    int top_half_len = 0
    choose a median //it's up to you to determine the best way to do this
    for 0 to n {    //filter all values above the median into list 2
        if (value > median) {
            push list 1 top to list 2 //list 2 stores the larger half
            top_half_len++
        }
        rotate list 1 forward
    }

    //reverse the list back to original position
    rotate list 1 backward (n - top_half_len) times

    //push larger half onto smaller half
    push list 2 top to list 1 top_half_len times

    //recursively call this on the larger half
    quicksort(top_half_len)

    //rotate smaller half to front
    rotate list 1 forward top_half_len times

    //recursively call this on smaller half
    quicksort(n - top_half_len) 

    //reverse list back to original position
    rotate list 1 backward top_half_len times

Basically, it splits the list into a portion smaller or equal than the median (smaller half) and a portion greater than the median (larger half). Then it calls itself on both of these halves. Once they're length 1, the algorithm is done, since a 1 length list is sorted. Google quick sort for an actual explanation.

I'm think this should work, but I may have missed some edge case. Don't blindly follow this. Also, if you were dealing with arrays, I'd recommend you stop the quick sort at a certain recursion depth and use heap sort (or something to prevent the worst case O(n^2) complexity), but I'm not sure what would be efficient here. update: according to Peter Cordes, you should use insertion sort when you get below a certain array size (IMO you should at a certain recursion depth too).

Apparently merge sort is faster on linked lists. It probably wouldn't be too hard to modify this to implement merge sort. Merge sort is pretty similar to quick sort. why is merge sort preferred over quick sort for sorting linked lists

Answer 2

The problem statement is missing a compare function, so I would define compare(lista, listb) to compare the first node of lista with the first node of listb and return -1 for <, 0 for =, 1 for greater, or all that is really needed for merge sort is 0 for <= and 1 for >.

Also missing is a return value to indicate a list is empty when doing pa or pb. I would define pa or pb to return 1 if source list is not empty and 0 if source list is empty (no node to copy).

It's not clear if the goal is smallest amount of instructions refers to the number of instructions in the source code or the number of instructions executed during the sort.

-

Smallest number of instructions in the code would rotate list2 based on compares with list1 to insert nodes into list2 at the proper location. Start with a pb, and set list2 size to 1. Then rb or rrb are done to rotate list2 to where the next pb should be done. The code would keep track of list2 "offset" to smallest node in order to avoid endless loop in rotating list2. Complexity is O(n^2).

-

I'm thinking the fastest sort and perhaps fewest number of instructions executed is a bottom up merge sort.

Do a bottom up merge sort while rotating the lists, using them like circular buffers / lists. Copy list1 to list2 to generate a count of nodes, using the sequence | count = 0 | while(pb){rb | count += 1 }.

Using the count, move every other node from list2 to list1 using {pa, rr}, n/2 times. Always keep track of the actual number of nodes on each list in order to know when the logical end of a list is reached. Also keep track of a run counter for each list to know when the logical end of a run is reached. At this point you have two lists where the even nodes are on list1 and odd nodes are on list2.

Run size starts off at 1 and doubles on each pass. For the first pass with run size of 1, merge even nodes with odd nodes, creating sorted runs of size 2, alternating appending the sorted pairs of nodes to list1 and list2. For example, if appending to list1, and list1 node <= list2 node, use {ra, run1count -= 1}, else use {pa, ra, run2count -= 1}. When the end of a run is reached, the append the rest of the remaining run to the end of a list. On the next pass, merge sorted runs of 2 nodes from the lists, alternately appending sorted runs of 4 nodes to each list. Continue this for runs of 8, 16, ... until all nodes end up on one list.

So that's one pass to count the nodes, one pass to split up the even and odd nodes, and ceil(log2(n)) passes to do the merge sort. The overhead for the linked list operations is small (rotate removes and appends a node), so the overall merge should be fairly quick.

The number of instructions on the count pass could be reduced with while(pb){count +=1}, which would copy list1 to list2 reversed. Then spitting up list2 into list1 would also be done using rrr to unreverse them.

Complexity is O(n log(n)).