QuickSort (worst-cases... special data)
in [Theory]
|
Prev: Another approach to decide on existence of a real root for Univariate Polynomials with Integer Coefficients, and a possible Multivariate extension for 3-SAT
Next: Questions on turing machine problems
From: Sem on 5 May 2008 15:32 I've got a problem with QuickSort's analysis. The worst-case complexity is O(n^2) and in my analys I have data generated in that way... I think it is called A-shape and Vshape sequences... Making it clearly it looks like that: i have array : 2,4,6,8,10,9,7,5,3 - A shaped and Vshaped - 9,7,5,3,1,2,4,6,8 In theoretical calculus and if i sort it on "paper" i have this same number of steps, but when i made measurments for various numbers of elements but arrays looks like A and Vshaped... and theoretical both of those measurments should give those same diagrams but... practically they are completly different... QuickSort works faster for Vshaped array and much slower for Ashaped... and moreover it break down about 100 000 elements (Ashaped ofcoz)... I think it is caused by some troubles with memory or something like that but mayby someone know why it behaves like that
From: Tom Truscott on 5 May 2008 16:48 >I've got a problem with QuickSort's analysis. >The worst-case complexity is O(n^2) and in my analys I have data >generated in that way... >I think it is called A-shape and Vshape sequences... The worst-case sequence depends on how quicksort selects the pivot. If it uses median-of-1st,last,middle then both A and V should be equally bad. Some quicksorts use the median of e.g. 9 elements, or choose "randomly". That is still worst-case O(N^2) but not for the simple A and V patterns. There is a worst-case O(N) median algorithm, and a quicksort that uses it can be worst-case O(NlgN). Tom Truscott
From: Sem on 5 May 2008 17:38 On 5 Maj, 22:48, t...(a)login021.unx.sas.com (Tom Truscott) wrote: > >I've got a problem with QuickSort's analysis. > >The worst-case complexity is O(n^2) and in my analys I have data > >generated in that way... > >I think it is called A-shape and Vshape sequences... > > The worst-case sequence depends on how quicksort selects the pivot. > > If it uses median-of-1st,last,middle then both A and V should be equally bad. > Some quicksorts use the median of e.g. 9 elements, or choose "randomly". > That is still worst-case O(N^2) but not for the simple A and V patterns. > > There is a worst-case O(N) median algorithm, > and a quicksort that uses it can be worst-case O(NlgN). > > Tom Truscott I see i forgot to write that i have to choose always middle element and both sequences have bad timings, but V is much better than A... but they are still O(n^2) but different... so again, what can cause it?
From: Chris F Clark on 5 May 2008 18:03
Sem <semyazz(a)gmail.com> writes: > I see i forgot to write that i have to choose always middle element > and both sequences have bad timings, but V is much better than A... > but they are still O(n^2) but different... so again, what can cause it? Have you tried profiling the code to see where the time is being spent? If you have two cases that take different amounts of time, I would think that they would have different execution profiles. |