Sorting using a custom API - removeAndAppend

Question

We are given an API -

removeAndAppend(val)
//Removes val and appends it to the given collection

we need to sort the collection using this API..

I know that I can do this by -

for i <- N to 1
    extract max //in O(n) 
    removeAndAppend.. //Consider this O(1)

this is quadratic..

The question is can I do better than this..?

EDIT: We can do READ operations on collection like - compare(val1, val2)

I can imagine a linked list can allow u to removeAndAppen in constant time.. i dont think language/pseudo code matters here.. please correct me if i m wrong — abipc, Aug 20 '13 at 14:21
Take a look at [this question](http://stackoverflow.com/q/5732974/264775) about insert and remove in Java. Does it sound like what you're looking for? — thegrinner, Aug 20 '13 at 14:25

score 1 · Answer 1 · answered Aug 20 '13 at 14:51

1

You can use recursion, and many collections, split the in-parameter collections on its first element: lesserequal, and greater, recurse on both and merge. Complexity of merge-sort, search internet.

answered Aug 20 '13 at 14:51

Joop Eggen

107,315
7
83
138

I don't think you're allowed to remove an element from one collection and insert it into another. – Bernhard Barker Aug 21 '13 at 08:40

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

With no additional data structures / constant space restriction:

The O(n²) algorithm you described is essentially selection sort.

If you have access to an iterator of some kind (if not, how else would you access elements in the collection?), I believe one can do better by using a custom merge-sort as follows:

Compare element 1 and 2. removeAndAppend the smaller one, then removeAndAppend the remaining one. Do the same for element 3 and 4, 5 and 6, ... and element n-1 and n.

Now you'll have sorted subcollections of 2 elements each.
Merge indices (1,2) and (3,4). To do this, have 2 iterators starting from the beginning. Start by incrementing the one twice. Then proceed to do a merge-sort as usual using the removeAndAppend function. Do the same for (5,6) and (7,8), (9,10) and (11,12), ... and (n-3,n-2) and (n-1,n).

Now you'll have sorted subcollections of 4 elements each.
Merge size 4 collections similar to above, then 8, 16, 32, etc., until you reach the collection size.

The whole process will look something like this:

// setSize is how large sets we're currently merging
for setSize = 1; setSize <= n/2; setSize *= 2
  iterator left = begin
           right = begin
  for pos = 1 to n/(2*setSize)
    // here right and left are both at the beginning
    // even after the previous iteration of the loop,
    //   since we've removed and appended all other elements
    // so we only need to increase right by setSize
    right += setSize

    for i = 1 to 2*setSize
      if (left.value <= right.value)
        removeAndAppend(left)
      else
        removeAndAppend(right)

The above is just a basic draft, it might not be 100% correct and doesn't account for when the collection isn't a power of 2 (which will happen often). You need to be careful in this case otherwise you might wrap around, or not go far enough and end up with a partially sorted collection.

The complexity analysis should be almost identical to regular merge-sort and result in an O(n log n) running time.

With additional data structures / no constant space restriction:

Extract all the elements into another collection, sort this in O(n log n) (using a sorting algorithm of your choice) and iterate through the sorted set, calling removeAndAppend on the original collection for each.

If you're not allowed to extract elements, this method can still be used by having a collection of indices instead and, to do a compare, simply look up the applicable elements. However, for this to be efficient, you'll need constant time lookup by index.

I was looking for this - "If there is a constant space restriction (this seems like the most probable case), I don't think you can do better than quadratic." I think the quoted statement is correct because I need to do some processing(some logic for ordering) before using removeAndAppend.. removeAndAppend on N elements is definitely linear time.. Can we prove that quadratic is the best we can get..? I am not good at this :( — abipc, Aug 21 '13 at 12:36
I cannot do merge sort without O(n) space.. I was expecting something in place..or at the most constant space.. But I get the idea u r describing.. tnx — abipc, Aug 21 '13 at 14:23
We're reusing the same space as the input, so it should classify as O(1) **extra** space (which is usually how we define space complexity). — Bernhard Barker, Aug 21 '13 at 15:01

score 0 · Answer 3 · edited May 23 '17 at 10:31

0

RemoveAndAppend append at the end of collection?

Well, if this method has O(1) seems like the crucial question is how to find current max in the unprocessed part of collection - once the max is remove and append to the end.

Look at What is the best way to get the minimum or maximum value from an Array of numbers?

edited May 23 '17 at 10:31

Community

1
1

answered Aug 21 '13 at 06:41

Martin Podval

1,097
1
7
16

score 0 · Answer 4 · answered Aug 21 '13 at 09:06

0

Read the entire collection, sort it in your application, then "removeAndAppend" the values in the right order (which is now known).

answered Aug 21 '13 at 09:06

usr

168,620
35
240
369

Sorting using a custom API - removeAndAppend

4 Answers4

Linked