Hector Hansen Hector Hansen - 7 days ago 5
C Question

Sort a big number list (100k) as quickly as possible using limited operations

I have two list : list A containing a set of random numbers and list B empty. I have to sort the list A.

I can make limited operations on these two lists like :


  • move the first element of list A or B at the beginning of the list B or A

  • swap the two first elements of list A or B like
    32 41 8 9
    become
    41 32 8 9

  • make the last element of list A or B become the first in this list (rotation) like
    32 41 8 9
    become
    9 32 41 8

  • make the first element of list A or B become the last one in this list (rotation) like
    32 41 8 9
    become
    41 8 9 32



I have already set up an algorithm to sort the list A using the list B as the stack and the set of allowed operations, but it takes time when the list becomes large (more than 1000 elements) and is therefore not performing at all.

I have also try to set up a merge sort algorithm with this set of operations but with 10k of numbers it's take too many time (over 10 seconds).

Anyone have an idea of an efficient algorithm to perform this sort quickly ? I'm also using linked list and do my program in C to optimize the efficiency.

Answer

Using a linked list will allow a fast rotate. Using a merge sort should be fairly fast.

Use the rotates to treat A and B as queues. Treat each queue as two queues, a queue to retrieve elements from and a queue to append elements to. Use counts to keep track of the boundary between retrieved and appended elements.

For the initial pass, separate the elements into two queues, get an element from A, append to A, get another element from A, append to B. Once this is done, then A and B contain runs of size 1.

Merge runs from A and B, again alternating merged runs between A and B so when done with a merge pass, the queues are ready for the next pass.

Eventually all the elements end up on one list and the sort is done.

Comments