There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger wrote:
Once that is done, the 'pivot' is in it's correct spot.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger wrote:If i recall correctly, if the dataset is already mostly sorted, quicksort is painfully slow, whereas a bubble sort would be rather peppy.
Ulrika Tingle wrote:
fred rosenberger wrote:If i recall correctly, if the dataset is already mostly sorted, quicksort is painfully slow, whereas a bubble sort would be rather peppy.
I don't think you recall correctly. Quicksort is never painfully slow. If you're extremely unlucky (when picking pivot elements) the complexity can degrade to O(N*N) but that's the worst case really. Not even if you're the unluckiest person in the world you should get the worst case more than maybe once in a lifetime.![]()
Apart from the unluck issue, Quicksort performs very well with both sorted, reversely sorted and random sequences. It's hard to beat Quicksort really.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger wrote:I re-wrote it using a bubble sort, and it started processing in five minutes.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
fred rosenberger wrote:ok...we don't seem to want to preserve my spacing. ignore where my i's and j's show up. It might work if you copy it all to a monospace font.
fred rosenberger wrote:When the data is sorted, quicksort IS slow. period.
fred rosenberger wrote:When the data is sorted, quicksort IS slow. period.
There are times and places where you should NOT use it.
What about when you want two elements with the same value left unchanged. I thought quicksort might exchange them, whereas merge sort leaves them unchanged? That is why the )]Arrays#sort() and similar methods use merge sort. They describe it as stable, meaning you can sort once then sort again on different criteria and get a combined sort. Like sorting on first name then last name, which would give Tingle Ulrich, Tingle Ulrika, Tingle Ulrike and Tingle Vera in order.Ulrika Tingle wrote: . . . Quicksort is the best general array sorting algorithm . . .
Campbell Ritchie wrote:and similar methods use merge sort.
fred rosenberger wrote: By adding new data to the end and using a quicksort, it was taking HOURS if not DAYS to finish. I would call that painfully slow.
I re-wrote it using a bubble sort, and it started processing in five minutes.
Jose Campana wrote:Given the complexity of this algorithm, I was wondering If it was adequate for it to be asked frequently as an interview question ?
I was recently told a guy failed to write down a pseudo-code about it on a blackboard during an interview.
I don't know exactly what to comment on this, but I certainly believe it's not something you happen to learn overnight or otherwise something that happens to be fundamental for your programming survival; given that you can find it solved all over the internet.
Now, that I have seen the length of our discussion about it I rest re-assured, that's probably an advanced topic.
What do you guys think ?
Ulrika Tingle wrote:Well, Quicksort is one of the most well-known algorithms in computer science. It's the fasterst sorting algorithm known to man. It's the quintessential divide-and-conquer recursive algoritm. I see no reason really why not every programmer should know how it works.
Mike Simmons wrote:I agree it's a great algorithm. But among working programmers with 5, 10 years or more of experience after graduating - it's extremely possible that there has been no practical need to actually code one's own Quicksort during all that time. Thus, I wouldn't really penalize an applicant who didn't remember enough about it to code one up on the spot in an interview. Of course I would want them to be able to discuss some other topics at length, based on their more recent experience.