-3

Possible Duplicate:
Quicksort: Choosing the pivot

I read a statement:

The performance of quicksort falls on already sorted/almost sorted lists if the pivot is not randomized.

Please help explain this. I would have expected more comparisons probably - but not more swaps. I thought the worst case of a quick sort was sorting an inverted array.

Community
  • 1
  • 1
IUnknown
  • 9,301
  • 15
  • 50
  • 76

1 Answers1

1

I think that you have a sequence of numbers like {29, 24, 20, 19, 16, ...} an algorithm that discovers that it is a monotonically decreasing sequence and if we want an ascending sort simply reverses the sequence is more efficiently.

Mihai8
  • 3,113
  • 1
  • 21
  • 31