Originally Posted by
Kalovale
1. Why is their implementation efficient even in the case of duplicates?
2. Why did I get StackOverFlow errors?
1. The magic is in this segment:
Code:
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
It moves any value less than the pivot to one partition and any value larger than the pivot to the other partition. So any value equal to the pivot stays where they were. Whereas your code would move all values equal to the pivot to a single partition. I've never actually seen quick sort implemented their way. It's quite cool.
2. Essentially each duplicate value causes an extra recursive call. You ran out of memory for function stacks.
Bookmarks