Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

arxiv.org

Post reply on HN
Print view View original

1–10 of 13 posts

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#2

Post by BetaCygni »

> An attempt to solve this problem has been randomization as shown already in Hoare’s first articles on Quicksort [1]. On the other hand, this does not change the statistical probability for bad cases.

I really like the randomization solution. Worst case? What worst case?

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#3

Post by matslina »

BetaCygni wrote: post #2

> An attempt to solve this problem has been randomization as shown already in Hoare’s first articles on Quicksort [1]. On the other hand, this does not change the statistical probability for bad cases. I really like the randomization solution. Worst case? What worst case?

Well, the worst case is still there. You're just going to have a very hard time crafting an input that triggers it.

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#5

Post by Kenji »

I remember, at uni, in the second semester, we had an assignment to specifically craft a sequence of n numbers 1..n that would trigger the worst case (#permutations) in a quicksort algorithm that always takes the first number in the array as the pivot. It was a nightmare. I spent days on it, and I was barely able to scrape together a notation to specify such a series. Turns out the sample solutions were like "The appropriate sequence is not easy to write. The sequence must be designed such that every chosen pivot halves the area that will be stored." Well, yeah.

EDIT: I wrote worst case #permutations. That's the best case #comparisons. So, no, I don't mean a sorted sequence ;)

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#7

Post by rachbowyer »

Kenji wrote: post #5

I remember, at uni, in the second semester, we had an assignment to specifically craft a sequence of n numbers 1..n that would trigger the worst case (#permutations) in a quicksort algorithm that always takes the first number in the array as the pivot. It was a nightmare. I spent days on it, and I was barely able to scrape together a notation to specify such a series. Turns out the sample solutions were like "The app…

If quicksort always takes the first element in the array as the pivot, then an array that is already sorted is the worst case.

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#8

Post by TheLoneWolfling »

Kenji wrote: post #5

I remember, at uni, in the second semester, we had an assignment to specifically craft a sequence of n numbers 1..n that would trigger the worst case (#permutations) in a quicksort algorithm that always takes the first number in the array as the pivot. It was a nightmare. I spent days on it, and I was barely able to scrape together a notation to specify such a series. Turns out the sample solutions were like "The app…

Doesn't a sorted array trigger the worst case in that case? Either ascending or decending. It's one of the reasons not to choose the first element as the pivot, iirc.

A much more interesting case is the median-of-three pivot. (Namely, median of first / middle / last elements). You can still do it, however.

Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]

#10

Post by [deleted] »

Kenji wrote: post #5

I remember, at uni, in the second semester, we had an assignment to specifically craft a sequence of n numbers 1..n that would trigger the worst case (#permutations) in a quicksort algorithm that always takes the first number in the array as the pivot. It was a nightmare. I spent days on it, and I was barely able to scrape together a notation to specify such a series. Turns out the sample solutions were like "The app…

[deleted]
Post reply on HN