Algorithm.txt

Algorithm:
Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the list).
Step 2 - Define two variables i and j. Set i and j to first and last elements of the list respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i > j.
Step 7 - Exchange the pivot element with list[j] element.


Program:
#include <bits/stdc++.h>
using namespace std; 
  
void swap(int* a, int* b) 
{  
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
int parting (int arr[], int low, int high) 
{ 
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) 
    { 
        if (arr[j] < pivot) 
        { 
            i++; 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

void quick_sort(int arr[], int low, int high) 
{  
    if (low < high) 
    { 
        int pi = parting(arr, low, high); 
  
        quick_sort(arr, low, pi - 1); 
        quick_sort(arr, pi + 1, high); 
    } 
} 
  
void printing(int arr[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
   
} 
  

int main() 
{ 
    int arr[10000];
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i<n; i++){
    arr[i] = i;
}
   
    quick_sort(arr, 0, n - 1); 
    cout << "Sorted array: \n"; 
    printing(arr, n); 
    return 0; 

}