Pseudocode and complexity for ith smallest element in an array

Question

I have to write an efficient pseudocode to find the i-th smallest element in an unsorted array with n elements,where n ,i and A[n] are input data.

In my opinion this means that I have to write the pseudocode for sorting an array in increasing order.I was about to do it with selection sort but I read the question again and it said efficient so lets do it with merge sort!

My pseudocode is :

    {

    n<---length[A]
    if (n<2)
       return

    mid <--- n/2
    left<---array of size(mid)
    right<---array of size(n- mid)
    for i<---0  to mid-1
    left[i]<--- A[i]
    for i<---mid  to n-1
    right [i-mid]<---A[i]
    Mergesort(left)
    Mergesort(right)
    Merge(left,right,A)
}

The complexity in all the cases (worst average best) is O(nlogn).Which means that this algorithm is very fast !

Is my solution correct

Edit: My question is very specific,it asks for an efficient algorithm.Which means we need a fast one.The ones you keep trying to add as duplicate arent efficient they have O(n) complexity

Possible duplicate of [How to find the kth largest element in an unsorted array of length n in O(n)?](http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on) — Saeid, Jan 01 '16 at 11:26
Please dont do this to me man,dont downvote the question...there is not a possible answer for me in that thread I have *already* solved it.. — Jane D., Jan 01 '16 at 11:28
@JaneD.: It should be clear that `O(n log n)` is asymptotically worse than `O(n)`, since `log n` increases without bounds. That is, for any constant `c`, there is an `n` such that `log n > c`, and consequently `n log n > cn`. I think you are confusing `O(log n)` (fast) with `O(n log n)` (reasonable, but not as fast as `O(n)`) — rici, Jan 01 '16 at 17:24
@JaneD.: You should not sort at all, or at least not more than necessary. That's why people usually recommend quickselect, which is O(n) if you use median-of-medians to select the pivot, or stochastic O(n) if you use randomized pivots. There is also an algorithm using a priority queue which is `O(n log i)`; in the worst case, where `i == n`, that's the same as `O(n log n)`, but if you expect `i` to be asymptotically smaller than `n`, it's worth considering. — rici, Jan 01 '16 at 19:26
And selection sort is awful. Even optimized to not sort the whole vector, it's `O(ni)`. — rici, Jan 01 '16 at 19:28
I should use linear search to do this so the complexity will be O(1) at best case and O(n) at worst case.I dont know about average case.Linear search would mean I can only use one for cycle in my pseudocode.How can I use only one cycle in my pseudocode to find the i-th smallest element? :( — Jane D., Jan 01 '16 at 20:58

score 0 · Answer 1 · edited May 23 '17 at 11:59

1 Your algorithm is not very fast.

With almost any known good standard sort, you can get O(n log n) to sort the entire array. Then take the ith (immediate in an array for example)

2 Your pseudocode is not finished. what does it return ?

Some considerations:

If i is rather little, just iterate and keep i minimum datas (insert every new data in a binary tree of the i most little datas, if it is less than the max of these datas). It will take < O(n) . log i

If i becomes big, just sort everything => O (n.log n)

And for further details, see the link already given by sudomakeinstall2:

How to find the kth largest element in an unsorted array of length n in O(n)?

Pseudocode and complexity for ith smallest element in an array

1 Answers1