I had a test on sorting using quick sort algorithm, which I have implemented. It's working fine.
But my examiner is not satisfied. They say that the solution which I provided is not a proper quicksort, my code partially deviates from the actual quicksort algorithm, and the code is a mess in certain places.
I took the quicksort explanation from wikipedia's quick sort's graphical explanation.
The examiner said to again go through the code again, which I have done. It works fine.
My code also uses the concept of "divide and conquer" as the "partition" function in the code only works on a certain part of input array.
What's my examiner pointing at that I'm missing?
function quickSort(inputArray){
var pivotIndex = undefined;
var low_Index = undefined;
var high_Index = undefined;
pivotIndex = inputArray.length - 1;
low_Index = 0;
high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;
partition(pivotIndex,low_Index,high_Index);
// the function which works on partitioned array
function partition(pivot_Index,low_Index,high_Index){
var temp = 0;
console.log("\nPivot Number : "+inputArray[pivot_Index]);
console.log("input Array : "+inputArray);
console.log("partitioned array : "+inputArray.slice(low_Index,pivot_Index+1));
for(var low = low_Index; low < pivot_Index; low++){
if(inputArray[low] > inputArray[pivot_Index]){
temp = inputArray[low];
inputArray[low] = inputArray[high_Index];
inputArray[high_Index] = inputArray[pivot_Index];
inputArray[pivot_Index] = temp;
pivot_Index = high_Index;
high_Index--;
low--;
}
}// end of for loop
if(inputArray[low_Index] > inputArray[high_Index]){
temp = inputArray[low_Index];
inputArray[low_Index] = inputArray[high_Index];
inputArray[high_Index] = temp;
pivot_Index = high_Index;
}
if(pivot_Index < inputArray.length - 1){
if((pivot_Index + 1) < inputArray.length - 1){
partition(inputArray.length - 1,(pivot_Index + 1),inputArray.length - 2);
}
if((pivot_Index - 2) >= 1){
partition((pivot_Index - 1),0,(pivot_Index - 2));
}
}// end of if condition
} // end of partition funtion
return inputArray;
} // end of quick sort function
When I run the above code for input
console.log("\nFinal Sorted Array "+quickSort([5,6,1,2,7,8,3]));
the output is
rahul@rahul:~/myPractise/Algo$ node sorting.js
Pivot Number : 3
input Array : 5,6,1,2,7,8,3
partitioned array : 5,6,1,2,7,8,3
Pivot Number : 5
input Array : 1,2,3,6,7,8,5
partitioned array : 3,6,7,8,5
Pivot Number : 6
input Array : 1,2,3,5,7,8,6
partitioned array : 7,8,6
Pivot Number : 7
input Array : 1,2,3,6,5,8,7
partitioned array : 5,8,7
Pivot Number : 5
input Array : 1,2,3,6,5,7,8
partitioned array : 1,2,3,6,5
Pivot Number : 8
input Array : 1,2,3,5,6,7,8
partitioned array : 6,7,8
Pivot Number : 3
input Array : 1,2,3,5,6,7,8
partitioned array : 1,2,3
Pivot Number : 8
input Array : 1,2,3,5,6,7,8
partitioned array : 5,6,7,8
Pivot Number : 3
input Array : 1,2,3,5,6,7,8
partitioned array : 1,2,3
Pivot Number : 8
input Array : 1,2,3,5,6,7,8
partitioned array : 5,6,7,8
Pivot Number : 3
input Array : 1,2,3,5,6,7,8
partitioned array : 1,2,3
Pivot Number : 8
input Array : 1,2,3,5,6,7,8
partitioned array : 5,6,7,8
Final Sorted Array 1,2,3,5,6,7,8
rahul@rahul:~/myPractise/Algo$
partition()
moves the pivot element/value quite a lot, and it looks avoidably complicated. Formatting style issues? Personal taste, IMO. Your examiner seems to like to keep anybody guessing. Does she object to Lomuto partitioning? Doesn't she answer questions like What disqualifies this as an implementation of quicksort? or Do you insist on Hoare partitioning?? \$\endgroup\$