Question

Sort 33, 77, 22, 11, 34, 21, 88, 90, 42 using Quick sort. Write the algorithm. show work

Answer 1

Program in c++:

#include<iostream> 
using namespace std;  
void swap(int* a, int* b)  //function to swap two element
{  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
int partition (int arr[], int low, int high)  
{  
    int pivot = arr[high]; //take last element as pivot  
    int i = (low-1); // Index of smaller element  
  
    for (int j = low; j <= high - 1; j++)  
    {  
         
        if (arr[j] < pivot)// If arr[j] is smaller than the pivot 
        {  
            i++; // increment index of smaller element  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  // places  the pivot element at its correct position in sorted array
    return (i + 1);  // return partition index
}  
  
void quickSort(int arr[], int low, int high)  //low = Starting index,high = Ending index 
{  
    if (low < high)  
    {  
        int q = partition(arr, low, high);  
        quickSort(arr, low, q - 1);  // Separately sort elements before  partition 
        quickSort(arr, q + 1, high); // Separately sort elements and after partition
    }  
}  
  
int main()  
{  
    int arr[] = {33,77,22,11,34,21,88,90,42};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    quickSort(arr, 0, n - 1);  
    cout << "Sorted array is :";  
    int i;  
    for (i = 0; i < n; i++){ 
        cout<<arr[i]<<" ";  
    }
    
    return 0;  
}  

Output:

Algorithm for sort function

here,

1. low is a starting index and high is ending index
2. arr is a array.
3. q is a index partition index

QuickSort(arr[],low,high)

{

if(low<high){  

q=Partition(arr,low,high);

QuickSort(arr,low,q-1); // sort before partition index (q)

QuickSort(arr,q+1,high);  // sort after partition index (q)

}

}

Algorithm for Partition function:

Partition(arr[],low,high)

{

pivot=arr[high];

i=low-1;

for(j=low;j<=high-1;j++){

if(arr[j]<pivot){

i=i+1;

swap arr[i] and arr[j]

}

}

swap arr[i+1] and arr[high]

return i+1

}

demonstration For partition function:

int arr[] = {33,77,22,11,34,21,88,90,42}

low=0,high=8,pivot=arr[high]=42

i=-1

j loop from low to high-1

j=0, check arr[j]<=pivot which istrue, increase i by 1(i=0) swap (arr[i],arr[j])

arr[]={33,77,22,11,34,21,88,90,42}

j=1 check arr[j]<=pivot which is false . no change

j=2 check arr[j]<=pivot which is true increase i by 1(i=1) swap (arr[i] ,arr[j])

arr[]={33,22,77,11,34,21,88,90,42}

j=3 check arr[j]<=pivot which is true increase i by 1(i=2) swap (arr[i] ,arr[j])

arr[]={33,22,11,77,34,21,88,90,42}

j=4 check arr[j]<=pivot which is true increase i by 1(i=3) swap (arr[i] ,arr[j])

arr[]={33,22,11,34,77,21,88,90,42}

j=5 check arr[j]<=pivot which is true increase i by 1(i=4) swap (arr[i] ,arr[j])

arr[]={33,22,11,34,21,77,88,90,42}

j=6 check arr[j]<=pivot which is false . no change

j=7  check arr[j]<=pivot which is false . no change

j loop is end and value of j=8 and i=4

swap arr[i+1] and arr[high]

arr[]={33,22,11,34,21,42,88,90,77}

return index of 42 which is 5 to QuickSort function (42 at its correct position in sorted array)

Now In QuickSort function again call for before and after partition index. This process is done recursivly until low<high

At last we get sorted array