My Blog
My Blog

Implementing Quick sort

Quick sort is divide and conquer method. although it does not divide in to two equal part like merge sort it divide int to dynamic partition to sort data

  1. Pick random value from the array which will call Pivot
  2. Reorder the array so that the item smaller than pivot it goes on left of it ,and  the item greater than  or equal to pivot it go to right of it , this is know as a partitioning
  3. Recursively call step 1 and 2 until list sorted

There many ways to picking up pivot from the array. either we choose left most item or right most item form array. in both way  If array is already sorted it will take worst case complexity . choosing a good pivot can improve the efficiency of the algorithm

 

we used the first item as a pivot . we can choose last item or median. lets Implement on PHP

function quickSort($array)
{
    $count = count($array);

    if ($count <= 1)
        return $array;


    $pivot = $array[0];
    $left = $right = array();

    for ($i = 1; $i < $count; $i++) {

        if ($array[$i] > $pivot) {
            $right[] = $array[$i];
        } else if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        }
    }

    return array_merge(quickSort($left), 
                       array($pivot), 
                       quickSort($right));
}

The worst case complexity causes with selection of pivot , here is the complexity

Worst case  O(n2)

Average case  O(nlog(n))

Best case O(nlog(n))

Sapce Complexity (worst case) O(log(n))