CODEWITHSUNDEEP
c++sorting
user1161604
user1161604

Reputation: 353

What is the best sorting algorithm in this situation?

myarray = empty
n = 10000
range = 1000
loop 1 to n {
    x = random number between 1 and range 
    if x not in myarray {
        add x to myarray
        sort myarray
        do something 
    }
}

I considered insertion sort, but that would require elements to shift. And quicksort would be bad on already sorted lists. The best I could think of now is a Min Heap. Is there some lesser known sorting algorithm that's better for this situation? Is it in C++'s STL?

Upvotes: 3

Views: 380

Answers (3)

juliomalegria
juliomalegria

Reputation: 24941

The very best option when you know that the numbers you're sorting will always be between 0 and a max_value is Counting sort, with an unsurpassable complexity: O(n).

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 373402

The best option would be to not sort the array at all and then wait until the end before sorting. Sorting repeatedly in an array will be expensive, because you will have to shift elements over one way or the other.

Since you are interested in the operations

  • Insert an element
  • Check if an element is there
  • Maintain sorted order

You should consider looking into a different structure than an array, perhaps a binary search tree, which supports fast (O(log n)) insertion and can be used to retrieve the sorted order.

Hope this helps!

Upvotes: 2

Mark Ransom
Mark Ransom

Reputation: 308530

You're looking for std::set. It keeps things sorted as you insert, and gives you a quick "not in" operation.

Upvotes: 9

Related Questions