4
\$\begingroup\$

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$ 
\$\endgroup\$
  • \$\begingroup\$ it amazes me when you say your "examiner is not satisfied" as per the selection , insertion and now quick sort. \$\endgroup\$ – Siobhan Aug 3 '16 at 8:01
  • \$\begingroup\$ 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\$ – greybeard Aug 3 '16 at 8:30
1
\$\begingroup\$

Interesting question,

as far as I can tell, quicksort is recursive, your solution is not. Hence, your solution is not really quicksort.

Other than that, this makes me cringe:

  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;

just declaring a variable assigns the value undefined, there is no reason to assign it, so don't do it. Then right after you declared those variables, you assign values, which you could also do in the var statement. Finally, and this is truly a matter of tastes you could chain those statements:

  var pivotIndex = inputArray.length - 1,
      low_Index = 0,
      high_Index = (inputArray.length > 2) ? (inputArray.length - 2) : 0;

Even here, you could reflect on the repetition of inputArray.length and assign this to a shorter variable name, to make this more readable, and a fraction faster:

  var length = inputArray.length,
      pivotIndex = length - 1,
      low_Index = 0,
      high_Index = (length > 2) ? (length  - 2) : 0;

Then again, you are not using a consistent naming standard, always use lowerCamelCase in JavaScript. I think some professors dislike ternaries, I would avoid them in school or at least check with the professor.

  var length = inputArray.length,
      pivotIndex = length - 1,
      lowIndex = 0,
      highIndex = Math.max(length - 2, 0);

Other than that your white-spacing is far too generous, never use more than a double newline.

This probably also makes you loose points:

for(var low = low_Index; low < pivot_Index; low++){

I would use index instead of low, otherwise reading your code becomes too hard.

Finally, also check your code for repetition, you swap two entries a number of times, I would have written a dedicated function for that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.