Day 35 - Search and Sort Algorithms Part H: Quick Sort

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

Pseudocode

/* low --> Starting index, high --> Ending index */ quickSort(arr[], low, high) { if (low < high) { /* pi is partitioning index, arr[pi] is now at right place */ pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // Before pi quickSort(arr, pi + 1, high); // After pi } } 

Referance: https://www.geeksforgeeks.org/quick-sort/

Question

Type: Divide and Conquer

Given an unsorted list of elements, write a program to sort the given list using quick sort.

Example

input: [1, 5, 2, 7, 3, 4, 8, 9, 6] output: [1, 2, 3, 4, 5, 6, 7, 8, 9] 

Solution

JavaScript Implementation

to be added 

C++ Implementation

/* * @author : imkaka * @date : 6/2/2019 */ #include<iostream>  using namespace std; void swap(int& a, int& b){ int temp = a; a = b; b = temp; } void quickSort(int arr[], int left, int right){ if(right - left <= 1) return; //Pivot arr[left] int yellow = left +1; for(int green = left+1; green < right; ++green){ if(arr[green] < arr[left]){ swap(arr[yellow], arr[green]); yellow++; } } //Move Pivot to original place swap(arr[left], arr[yellow-1]); quickSort(arr, left, yellow-1); quickSort(arr, yellow, right); } void print(int arr[],int size){ for(int i = 0; i < size; ++i){ cout << arr[i] << " "; } cout << endl; } int main(){ int arr[] = {10, 25, 0, 23, 36, -1, 3, 1, 6}; int size = sizeof(arr)/sizeof(arr[0]); cout << "Before Sorting: "; print(arr, size); quickSort(arr, 0, size); cout << "After Sorting: "; print(arr, size); } 

Python Implementation

""" @author : imkaka @date : 5/2/2019 """ import sys def QuickSort(A, l, r): # sort A[l:r]  if r - l <= 1: return() #Pivot = A[l]  yellow = l + 1 for green in range(l + 1, r): if(A[green] <= A[l]): (A[yellow], A[green]) = (A[green], A[yellow]) yellow += 1 # Move Pivot into place  (A[l], A[yellow - 1]) = (A[yellow - 1], A[l]) QuickSort(A, l, yellow - 1) QuickSort(A, yellow, r) def main(): A = [20, 34, 1, 3, -2, 34, 65, 100, 0] print('Before Sorting', A) print(len(A)) QuickSort(A, 0, len(A)) print('After Sorting', A) if __name__ == '__main__': main()