Sort 2 linked lists of 50,000 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 have only a very limited group of instructions. It:

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

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

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

• "pa": click on top of list 2 on top of list 1

• "pb": click on top of list 1 on top of list 2

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

• "rb": rotate list 2 (first will be the last)

• "rr": "ra" and "rb" immediately

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

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

• "rrr": "rra" and "rrb" immediately

I need to implement a sorting algorithm in c, and the goal is to do this with the least amount of instructions. I tried with a very simple algorithm that rotated list one until the maximum was at the top, and then dragged it to list 2 until everything was on list 2, and then still dropped it on list 1, but I couldn't sort lists of more than 5 thousand numbers in a reasonable time

Answer 1

I think I figured out how to do this using quicksort. Here is some pseudo code.

edit: updated pseudo code to focus on what it does, rather than unnecessary syntax

quicksort(int n) if n == 1 return int top_half_len = 0 choose a median //it 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 

In principle, it splits the list into smaller or equal parts than the median (smaller half), and part larger than the average (large half). Then he calls himself both of these halves. As soon as they are 1 in length, the algorithm is executed, since a list of 1 length is sorted. A quick google search for an actual explanation.

I think this should work, but I might have missed some extreme case. Do not blindly follow this. Also, if you were dealing with arrays, I would recommend that you stop fast sorting with a specific recursion depth and use heap sorting (or something to prevent O (n ^ 2) worst case complexity), but I'm not sure what was would be effective here. update: according to Peter Cordes, you should use insertion sorting when you get below a certain array size (IMO you also have to have a certain recursion depth).

Apparently, sorting sorting is faster in linked lists. It would probably not be too difficult to change this to implement a merge sort. Merging sorting is pretty similar to quick sorting. why merge sort is preferred over speed sort for sorting linked lists

Answer 2

There is no comparison function in the description of the problem, so I would define compare (lista, listb) to compare the first node of the list with the first node of the listb and return -1 for <, 0 for =, 1 for more or everything that is really needed to sort the merge is 0 for <= and 1 for>.

There is also no return value indicating that the list is empty when pa or pb is executed. I would define pa or pb to return 1 if the source list is not empty, and 0 if the source list is empty (no node to copy).

It is not clear whether the target is the smallest number of instructions, refers to the number of instructions in the source code or the number of instructions executed during sorting.

 - 

The smallest number of commands in the code will rotate list2 based on a comparison with list1 to insert nodes into list2 in the right place. Start with pb and set list2 to 1. Then rb or rrb is executed to rotate list2 to where the next pb should be executed. The code will track the "offset" of list2 to the smallest node to avoid an infinite loop in a rotating list2. Complexity is O (n ^ 2).

 - 

I think the fastest sorting, and possibly the least number of instructions executed, is a merge sort from bottom to top.

Do a merge sort from bottom to top as you rotate lists, using them as circular buffers / lists. Copy list1 to list2 to generate the number of nodes using the sequence | count = 0 | whereas (pb) {rb | count + = 1}.

Using the counter, move all the other nodes from list2 to list1, using {pa, rr}, n / 2 times. Always keep track of the actual number of nodes in each list to find out when the logical end of the list is reached. Also track the run counter for each list to see when the logical end of the run is reached. At the moment, you have two lists where even nodes are in list1, and odd nodes are in list2.

The launch size starts at 1 and doubles on each pass. For the first pass, with run size 1, even nodes with odd nodes are combined, creating sorted runs of size 2, alternating the addition of sorted pairs of nodes in list1 and list2. For example, if you add to the list1 and list1 node <= list2 node, use {ra, run1count - = 1}, otherwise use {pa, ra, run2count - = 1}. When the end of execution has been reached, add the rest of the remaining run to the end of the list. In the next pass, the merge sorts the runs from 2 nodes from the lists, alternately adding the sorted runs of 4 nodes to each list. Continue this for runs 8, 16, ... until all nodes are in the same list.

So, to go through the counting of nodes, one pass separates the even and odd nodes, and ceil (log2 (n)) proceeds to sort the merge. The overhead for linked list operations is small (rotate removes and adds node), so general merging should be pretty quick.

The number of instructions on the counter can be reduced by using while (pb) {count + = 1}, which would copy list1 to list2 in reverse order. Then flipping list2 to list1 will also be done using rrr to cancel them.

Complexity is O (n log (n)).