CODEWITHSUNDEEP
algorithmsortingquicksort
eouti
eouti

Reputation: 5658

Quicksorting binary array

I would like to know how many comparisons, in the worst case, does Quicksort need to sort an binary array of size n.
I can't find out what the worst case for this problem. [0 1 0 1 0 1..] ?
Cheers,
eo

Upvotes: 1

Views: 134

Answers (2)

Rami Jarrar
Rami Jarrar

Reputation: 4643

Sorting an array that consists of a small number of unique keys is common in practice. One would like an algorithm that adapts to O(n) time when the number of unique keys is O(1). Which in your case there are just two unique keys.

QuickSort is O(nlogn) on average, But O(n^2) on worst case, for your case I've tested the quicksort algorithm on this array [ 0 1 1 0 1 0 1 0 0 0 1 0 1 ] , the lenght of the array is 13 elements, and the algorithm takes 170 iteration to sort this array, which is n^2.

And this pseudo code for O(n) algorithm:

let n0 <- 0;
for i=0  to lenght(A)
    if A[i] == 0
        A[n0] = 0;
        ++n0

for i=n0 to lenght(A)
    A[i] = 1

Upvotes: 0

Alceu Costa
Alceu Costa

Reputation: 9899

Not exactly quicksort, but if you want to sort a binary array you can do it in O(n). Just count how many 1's and 0's you have then write then in the order you want.

For example, for the following array:

[0 1 0 1 0 1 1]

You can count, in O(n) that you have three 0's and four 1's. Then you just rewrite your array first with the three 0's and then with the four 1's.

Upvotes: 1

Related Questions