Hello Sir,
I was studying the sorting algorithms from this repository and testing out the code on a few different arrays. I noticed that the QuickSort implementation sometimes fails to sort correctly or throws a StackOverflowError on larger, unsorted arrays.
While tracing the execution in 4 Other Problems/QuickSort.java, I believe I found the root cause in the quickSort method:
int partitionIndex = partition(nums, low, high);
quickSort(nums, 0, partitionIndex - 1); // <-- Left recursive call
quickSort(nums, partitionIndex + 1, high);
Because the left recursive call uses a hardcoded 0 instead of the low variable, it attempts to sort from the absolute beginning of the array every time, rather than the beginning of the current sub-problem. This seems to overwrite already sorted sections.
Changing that 0 to low appears to resolve the issue perfectly during my local testing.
Thank you for sharing all these resources, they have been really helpful for my DSA practice!
Hello Sir,
I was studying the sorting algorithms from this repository and testing out the code on a few different arrays. I noticed that the
QuickSortimplementation sometimes fails to sort correctly or throws aStackOverflowErroron larger, unsorted arrays.While tracing the execution in
4 Other Problems/QuickSort.java, I believe I found the root cause in thequickSortmethod:Because the left recursive call uses a hardcoded 0 instead of the low variable, it attempts to sort from the absolute beginning of the array every time, rather than the beginning of the current sub-problem. This seems to overwrite already sorted sections.
Changing that 0 to low appears to resolve the issue perfectly during my local testing.
Thank you for sharing all these resources, they have been really helpful for my DSA practice!