Assignment You will need to fork your JSFiddle for your List

Assignment You will need to fork your JSFiddle for your List into a new Fiddle. In this Fiddle we are going to add sorting functions. This is a great time to clean up your list with things that you have learned. You should automatically populate the List with 20 element (random strings). Once you have completed this - you will add 2 sort functions, you can use any sort method that you desire for each of the sort functions. You can also delineate the functions by the name of the Sort function - so your functions might be QuickSort() and MergeSort() - if you chose to implement those 2 algorithms (you can select from any sort functions). The interface should have buttons to (1) Repopulate the list with Random strings. (2) Sort list with selected algorithm 1 (3) Sort list with selected algorithm 2 and (4) Insert a new random string entered by the user into the list. After each operation it should display the new list. Create Randomized String List Sort with GoogleSort Sort with EnginSort Enter String Here Insert String The option 4 here will insert the new string entered by the user (you will need a check box) in the correct sorted position and you should print the new list with the new element on the screen.

Solution

I have written the javascript code for both merge and quick sort. The idea behing merge and quick sort remains the same where we split the array for merge sort recurisvely and then merge smaller chunks of sorted array into the final array.

Merge sort javascript code:

function mergeSort(arr) {

   recurse_merge_sort(0, arr.length - 1);
   return arr;
  
   function recurse_merge_sort(lowerBound, upperBound){          
       var mid;

       if (lowerBound === upperBound){
           return;
       }

       mid = Math.floor((upperBound + lowerBound)/2);

       // sort lower half of array
       recurse_merge_sort(lowerBound, mid);

       // sort upper half similarly.
       recurse_merge_sort(mid + 1, upperBound);
      
       // merge sorted array
       Merge_arr(lowerBound, mid, upperBound);
   }

   function Merge_arr(lowerBound, mid, upperBound){

       var temp = []; // Buffer array
       var lower = lowerBound;
       var upper = mid + 1;
       var i = 0;
       var totalLength = upperBound - lowerBound + 1;

       while(lower <= mid && upper <= upperBound){
           if (arr[lower] < arr[upper]){
               temp[i] = arr[lower];
               lower += 1;
           } else {
               temp[i] = arr[upper];
               upper += 1;
           }
           i += 1;
       }

       // check left array and copy directly
       while (lower <= mid){
           temp[i] = arr[lower];
           i += 1;
           lower += 1;
       }

       // check right array and copy directly.
       while(upper <= upperBound){
           temp[i] = arr[upper];
           i += 1;
           upper += 1;
       }

       // Copy the sorted array.
       for(i = 0; i < totalLength; i += 1){
           arr[lowerBound + i] = temp[i];
       }
   }
}

Quick sort code: Quick sort is based on the concept of selecting the pivot element usually the mid element in the array and then sorting the left center and right chunk of the array based on the pivot selected. Once the sorting is done we do a merge to get the sorted array.

function quickSort(arr){
  
   recurse_quicksort(0, arr.length - 1);
   return arr;

   function recurse_quicksort(left, right){
       var pivot;
       var partition;

       var size = right - left + 1;

       //use helper sort for smaller array size.
       if (size < 10){
           helper_sort(left, right);
       } else{

           // select pivot on array
           pivot = median_arr(left, right);

           // array partitioning based on pivot
           partition = partition_arr(left, right, pivot);

           // sort the array based on partition
           recurse_quicksort(left, partition - 1);
           recurse_quicksort(partition + 1, right);
       }
   }

   function partition_arr(left, right, pivot){

       var leftIndex = left;

       var rightIndex = right - 1;

       while(true){

           while(arr[++leftIndex] < pivot);
           while(arr[--rightIndex] > pivot);

           if(leftIndex >= rightIndex){
               break;
           }else{
               swap(leftIndex, rightIndex);
           }
       }
      
       swap(leftIndex, right - 1);
       return leftIndex;
   }

   function median_arr(left, right){
       var mid = Math.floor((left + right)/2);

       if(arr[left] > arr[mid]){
           swap(left, mid);
       }

       if(arr[left] > arr[right]){
           swap(left, right);
       }

       if(arr[mid] > arr[right]){
           swap(mid, right);
       }

       swap(mid, right - 1);

       return arr[right - 1];
   }

   function helper_sort(left, right){
       var outer;
       var inner;
       var temp;

       for (outer = left + 1; outer <= right; outer += 1) {
           // selec an element in the array for sorting.
           temp = arr[outer];
           inner = outer;

           while(inner > left && arr[inner-1] >= temp) {
               arr[inner] = arr[inner-1];
               inner -= 1;
           }

           arr[inner] = temp;
       }
   }

   function swap(index1, index2){
       var temp = arr[index1];
       arr[index1] = arr[index2];
       arr[index2] = temp;
   }
}