PHP Program - Quick Sort
Quick sort is a divide and conquer algorithm. It is based on the idea of choosing one element as a pivot and partitioning the array around the pivot with left side of the pivot containing all elements less than the pivot and right side of the pivot containing all elements greater than the pivot. There are many ways to choose the pivot. Few of them are mentioned below:
- First element of the array
- Last element of the array
- Random element of the array
- Median index element of the array
The quick sort has less space complexity as compared to merged sort because it do not use auxiliary array.
Example:
To understand the quick sort, lets consider an unsorted array [-4, 1, 25, 50, 8, 10, 23] and discuss each step taken to sort the array in ascending order.
In the implementation of this example, the last element of the array is chosen as the pivot element. At the start of the partition process, variables i and j are created which are the same initially. As the partition progresses the value of i and j becomes different. i signifies the boundary between elements less than the pivot and elements greater than pivot. j signifies the boundary between elements greater than pivot and unpartitioned array.
After partition, it generates two partition with left side partition contains elements less than pivot and right side partition contains elements greater than pivot. The both partition are again partitioned with the same logic and this process continues till a partition has zero or one element. The final outcome of this process will be a sorted array.
Implementation of Quick Sort
<?php // function for quick sort which calls partition function // to arrange and split the list based on pivot element // quicksort is a recursive function function quicksort(&$Array, $left, $right) { if ($left < $right) { $pivot = partition($Array, $left, $right); quicksort($Array, $left, $pivot-1); quicksort($Array, $pivot+1, $right); } } // partition function arrange and split the list // into two list based on pivot element // In this example, last element of list is chosen // as pivot element. one list contains all elements // less than the pivot element another list contains // all elements greater than the pivot element function partition(&$Array, $left, $right) { $i = $left; $pivot = $Array[$right]; for($j = $left; $j <=$right; $j++) { if($Array[$j] < $pivot) { $temp = $Array[$i]; $Array[$i] = $Array[$j]; $Array[$j] = $temp; $i++; } } $temp = $Array[$right]; $Array[$right] = $Array[$i]; $Array[$i] = $temp; return $i; } // function to print array function PrintArray($Array, $n) { for ($i = 0; $i < $n; $i++) echo $Array[$i]." "; echo "\n"; } // test the code $MyArray = array(-4, 1, 25, 50, 8, 10, 23); $n = sizeof($MyArray); echo "Original Array\n"; PrintArray($MyArray, $n); quicksort($MyArray, 0, $n-1); echo "\nSorted Array\n"; PrintArray($MyArray, $n); ?>
The above code will give the following output:
Original Array -4 1 25 50 8 10 23 Sorted Array -4 1 8 10 23 25 50
Time Complexity:
The time complexity of quick sort is Θ(N²) in worst case and the time complexity in best and average cases are Θ(NlogN).
Recommended Pages
- PHP Program - To Check Prime Number
- PHP Program - Bubble Sort
- PHP Program - Selection Sort
- PHP Program - Maximum Subarray Sum
- PHP Program - Reverse digits of a given Integer
- PHP - Swap two numbers
- PHP Program - Fibonacci Sequence
- PHP Program - Insertion Sort
- PHP Program - Find Factorial of a Number
- PHP Program - Find HCF of Two Numbers
- PHP Program - Merge Sort
- PHP Program - Shell Sort
- Stack in PHP
- Queue in PHP
- PHP Program - Find LCM of Two Numbers
- PHP Program - To Check Armstrong Number
- PHP Program - Counting Sort
- PHP Program - Radix Sort
- PHP Program - Find Largest Number among Three Numbers
- PHP Program - Print Floyd's Triangle