0

I have to implement Quick Sort but with a worst case of O(n log n). I can implement anything found in the literature, but so far all I can find is this thing called BSort that doesn't make much sense to me. Does anyone know of any references to algorithms that are easily implemented? Or papers on the subject?

Yes it is for class, but this part I can get help on, I just have to implement it on my own.

Thanks

Dixon Steel
  • 1,021
  • 4
  • 12
  • 27

3 Answers3

0

This is what i found. I have never tried to implement it or look at the alghoritm but it says it has the worst case O(n log n). It is a combination of quicksort and heapsort

http://en.wikipedia.org/wiki/Introsort

I believee none of the alghoritms(upgrades of quicksort)that get O(nlogn) worst case have simple solutions.

IamSneaky
  • 23
  • 7
0

Your question is not quite clear to me.

If you implement Quicksort (e.g. as defined here) it will have a worst case runtime of O(n**2). You can't avoid that if you are implementing "pure" Quicksort.

Do you want a different sorting algorithm that has an O(n*log(n)) worst case, or do you want an optimization to Quicksort?

Either way, that link I gave you will give you some ideas for algorithms.

I've never heard of BSort, can you give a link?

Steve
  • 8,469
  • 1
  • 26
  • 37
0

there is an old question that seems the same:

Can we do Quick sort with n logn worst case complexity?

Did you already take a look on that?

Community
  • 1
  • 1
Michele mpp Marostica
  • 2,445
  • 4
  • 29
  • 45