TODAY, We Are Talking About...

QUICK SORT

Divide & Conquer <& Combine

Uhh What it is???

Naja -It is a SORTING algorithm...

Let Me Explain

Here is the Javascript implementation

            'use strict'
          
      function quickSort(arr, lowIndex = 0, highIndex = arr.length - 1) {
        // Base case: if the lowIndex is greater than or equal to the highIndex, the array is already sorted
        if (lowIndex >= highIndex) {
          return;
        }

        // Choose a random pivot index between lowIndex and highIndex (inclusive)
        const pivotIndex = Math.floor(Math.random() * (highIndex - lowIndex + 1)) + lowIndex;
        const pivot = array[pivotIndex];

        // Swap the pivot element to the end of the array
        swap(array, pivotIndex, highIndex);

        // Perform partitioning and get the index of the pivot in its sorted position
        const leftPointer = partition(array, lowIndex, highIndex, pivot);

        // Recursively sort the subarrays on the left and right of the pivot
        quickSort(array, lowIndex, leftPointer - 1);
        quickSort(array, leftPointer + 1, highIndex);
      }

      // Function to partition the array around a pivot and return the pivot's final index
      function partition(array, lowIndex, highIndex, pivot) {
        // Initialize pointers for the partitioning process
        let leftPointer = lowIndex;
        let rightPointer = highIndex - 1;

        // Continue partitioning until the leftPointer crosses the rightPointer
        while (leftPointer < rightPointer) {
          // Move leftPointer to the right until finding an element greater than the pivot
          while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
            leftPointer++;
          }

          // Move rightPointer to the left until finding an element smaller than the pivot
          while (array[rightPointer] >= pivot && leftPointer < rightPointer) {
            rightPointer--;
          }

          // Swap the elements at leftPointer and rightPointer
          swap(array, leftPointer, rightPointer);
        }

        // Swap the pivot to its final sorted position
        if (array[leftPointer] > array[highIndex]) {
          swap(array, leftPointer, highIndex);
        } else {
          leftPointer = highIndex;
        }

        // Return the final index of the pivot
        return leftPointer;
      }

      // Function to swap two elements in an array
      function swap(array, index1, index2) {
        const temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
      }

        
      

NOW, is the time for

Algorithm Analysis

Of Course, In REAL Time

With MEDIAN of 3 Random Elements

Using Right Most Element for Pivot

Code implementation for STACK Method & MEDIAN of 3

            'use strict'

                  // quick sort with median 3 method
                  function quickSortMedian3(arr) {
                    const stack = [{ low: 0, high: arr.length - 1 }];
                  
                    while (stack.length) {
                      const { low, high } = stack.pop();
                      if (low < high) {
                        const pivotIndex = partitionMedian3(arr, low, high);
                        stack.push({ low, high: pivotIndex - 1 });
                        stack.push({ low: pivotIndex + 1, high });
                      }
                    }
                  }
                  
                  // partition function with median 3 method
                  function partitionMedian3(arr, lowIndex, highIndex) {
                    const midIndex = Math.floor((lowIndex + highIndex) / 2);
                  
                    // Sort low, mid, and high to determine the median
                    if (arr[lowIndex] > arr[midIndex]) {
                      swap(arr, lowIndex, midIndex);
                    }
                    if (arr[midIndex] > arr[highIndex]) {
                      swap(arr, midIndex, highIndex);
                    }
                    if (arr[lowIndex] > arr[midIndex]) {
                      swap(arr, lowIndex, midIndex);
                    }
                  
                    // Move the pivot to highIndex - 1 and return its index
                    swap(arr, midIndex, highIndex - 1);
                    return highIndex - 1;
                  }
                  
                  // helper method to SWAP elements
                  function swap(arr, i, j) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                  }
                  
                  // Calculation toolbox
                  function generateRandomArray(size) {
                    const arr = [];
                    for (let i = 0; i < size; i++) {
                      arr.push(Math.random());
                    }
                    return arr;
                  }
                  
                  function measureExecutionTime(func, arr) {
                    const start = performance.now();
                    func(arr);
                    const end = performance.now();
                    return end - start;
                  }
                  
                  function generateAscendingArray(size) {
                    const arr = [];
                    for (let i = 0; i < size; i++) {
                      arr.push(i);
                    }
                    return arr;
                  }
                  
                  function generateDescendingArray(size) {
                    const arr = [];
                    for (let i = size - 1; i >= 0; i--) {
                      arr.push(i);
                    }
                    return arr;
                  }
          
        
      

On TIME COMPLEXITY

Worst-Case:

When quicksort always has the most unbalanced partitions possible, the original call takes: \(cn \) time for some constant \( c \), the recursive call on \( n-1 \) elements takes \( c(n-1) \) time, the recursive call on \(n-2 \) elements takes \( c(n-2) \) time, and so on

\[ \begin{aligned} cn + c(n-1) + c(n-2) + \cdots + 2c &= c(n + (n-1) + (n-2) + \cdots + 2) \\ &= c((n+1)(n/2) - 1) \ . \end{aligned} \]

\[ \Theta (n^2) \]

Best-Case:

Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other. The former case occurs if the subarray has an odd number of elements and the pivot is right in the middle after partitioning, and each partition has \( (n-1)/2 \) elements. The latter case occurs if the subarray has an even number \( n \) of elements and one partition has \( n/2 \) elements with the other having \( n/2-1 \). In either of these cases, each partition has at most \( n/2 \) elements(similar to merge sort)

\[ \Theta(n \log_2 n) \]

Have Something to Say?
Leave a Comment at:

qquella.com/comments.html

Thank you for wanting to know more today then you did yesterday!