1

What is the most efficient method I can use to sort an array of integers by selecting one integer at a time and inserting it anywhere in the array? Or, inserting it at the end or the beginning of the array?

I'm looking for an algorithm that can do this in the minimum number of steps, unlike selection sort.

secretstuff
  • 91
  • 9
  • 2
    Take a look on [what-is-a-the-fastest-sorting-algorithm-for-an-array-of-integers](http://cs.stackexchange.com/questions/18536/what-is-a-the-fastest-sorting-algorithm-for-an-array-of-integers) – Missu Sep 29 '15 at 10:32
  • 1
    We are here to solve your issues in programs not writing a program itself. – Dilip Kumar Sep 29 '15 at 10:33
  • @Missu I am not looking for an algorithm to sort the array, but I am trying to understand how to sort it by removing elements and placing them anywhere else in the array in the minimum steps. Manually I am not able to identify how to do it other than intuition, thats why want to know how to do it in this method. – secretstuff Sep 29 '15 at 10:36
  • 1
    Take a look here: _https://en.wikipedia.org/wiki/Sorting_algorithm_ –  Sep 29 '15 at 11:34
  • By "select one integer and insert it anywhere", do you mean that in your use-case, inserting/deleting an element in the middle is `O(1)`, rather than `O(n)` as it would ordinarily be considered to be? – Sneftel Sep 29 '15 at 11:52
  • My advise would be to read up on algorithm theory, but do so sceptically. Because computer scientists are very bad at understanding computers. Perhaps they once were correct, in the 1950s or so, but today's computers are far too complex to just use "number of comparisons" as efficiency metrics. It might be far more relevant to for example count the number of branches in each algorithm, after which you can throw all your books about traditional algorithm theory in the garbage bin. – Lundin Sep 29 '15 at 11:55
  • 1
    If your goal is the minimum number of writes there is [Cycle Sort](https://en.wikipedia.org/wiki/Cycle_sort). If your goal is speed I'd start with the sort in your language library (`qsort` in C). – Blastfurnace Sep 29 '15 at 11:59
  • @Sneftel Yeah, It would be one operation, finally I dont want the sorted array but the number of such deletion and insertion of elements needed(minimum) to get the sorted array. – secretstuff Sep 29 '15 at 12:03
  • 1
    @Missu - The fastest sort for 32bit and 64bit integer arrays is RadixSort. http://stackoverflow.com/questions/32188370/fastest-sort-algorithm-for-millions-of-uint64-rgbz-graphics-pixels/32188749#32188749 http://stackoverflow.com/questions/8082425/fastest-way-to-sort-32bit-signed-integer-arrays-in-javascript – Louis Ricci Sep 29 '15 at 12:53
  • Depending on how you interpret the picking and placing elements requirement, a [heap sort](http://en.wikipedia.org/wiki/Heapsort) would probably be the fastest. A quick sort would be faster and in place, but heap sort is closer to the idea of picking and placing elements. – rcgldr Sep 29 '15 at 18:31

1 Answers1

0

You need to figure out the longest sequence of sorted elements. Then the number of steps is the number of elements that are not in the sequence.

Since the elements that don't belong to the selected sequence are out of order you need to move each of them to the right position. Since each move is a step according to your description, and you already picked the longest sorted sequence, this will give you the least number of steps.

Sorin
  • 11,863
  • 22
  • 26