QuickSort (worst-cases... special data)
- From: Sem <semyazz@xxxxxxxxx>
- Date: Mon, 5 May 2008 12:32:43 -0700 (PDT)
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
.
- Follow-Ups:
- Re: QuickSort (worst-cases... special data)
- From: Tom Truscott
- Re: QuickSort (worst-cases... special data)
- Prev by Date: Re: 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 by Date: Re: QuickSort (worst-cases... special data)
- Previous by thread: Third CEU Summerschool on Advanced Statistics and Data Mining (June 30th-July 11th, 2008)
- Next by thread: Re: QuickSort (worst-cases... special data)
- Index(es):