Aron Silvester

Ranch Hand

Posts: 63

posted 2 years ago

Alright, this is the first time I'm learning this sorting algorithm so It's kind of confusing. I thought of another case, where the pivot always chosen were always the highest or lowest value in the array. This will result in a worst case for a quick sort, which would be 0(n^2). One such case would be the array {8,7,6,5,4,3,2}. 8 is the pivot and we put it in its right place in the array, with elements smaller than the pivot before it, and larger elements after it. The next iteration will look like {7,6,4,4,3,2,8}. The next pivot will be 7 and the next iteration will be {6,5,4,3,2,7,8}. This goes on until they are sorted from least to greatest, which results in n^2 comparison, the worst case for a quick sort.

Agree or disagree?

Knute Snortum wrote:I believe that's correct if you're using the first element as your pivot.

Alright, this is the first time I'm learning this sorting algorithm so It's kind of confusing. I thought of another case, where the pivot always chosen were always the highest or lowest value in the array. This will result in a worst case for a quick sort, which would be 0(n^2). One such case would be the array {8,7,6,5,4,3,2}. 8 is the pivot and we put it in its right place in the array, with elements smaller than the pivot before it, and larger elements after it. The next iteration will look like {7,6,4,4,3,2,8}. The next pivot will be 7 and the next iteration will be {6,5,4,3,2,7,8}. This goes on until they are sorted from least to greatest, which results in n^2 comparison, the worst case for a quick sort.

Agree or disagree?

posted 2 years ago

It looks right; but of course you can short-circuit that by selecting the your pivots at random. I believe there are also versions that try to ensure that you select a "good-quality" pivot, but I've forgotten exactly how they go about it.

Winston

Conrado Sanchez wrote:Agree or disagree?

It looks right; but of course you can short-circuit that by selecting the your pivots at random. I believe there are also versions that try to ensure that you select a "good-quality" pivot, but I've forgotten exactly how they go about it.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here