Quick sort c++

#include <iostream>
using namespace std;
// Swap two elements - Utility function  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
   
// partition the array using last element as pivot
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);   
   
    for (int j = low; j <= high- 1; j++) 
    { 
        //if current element is smaller than pivot, increment the low element
        //swap elements at i and j
        if (arr[j] <= pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
   
//quicksort algorithm
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        //partition the array 
        int pivot = partition(arr, low, high); 
   
        //sort the sub arrays independently 
        quickSort(arr, low, pivot - 1); 
        quickSort(arr, pivot + 1, high); 
    } 
} 
   
void displayArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        cout<<arr[i]<<"\t"; 
      
} 
   
int main() 
{ 
    int arr[] = {12,23,3,43,51,35,19,45}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"Input array"<<endl;
    displayArray(arr,n);
    cout<<endl;
    quickSort(arr, 0, n-1); 
    cout<<"Array sorted with quick sort"<<endl; 
    displayArray(arr,n); 
    return 0; 
}

Quick sort c++

#include<iostream>
using namespace std;

int solve(int arr[], int s, int e, int &pivotIndex)
{
    int i=s,j=e;
    while(i<pivotIndex && j>pivotIndex)
    {
        while(arr[i]<=arr[pivotIndex])
        {
            i++;
        }
        while(arr[j]>arr[pivotIndex])
        {
            j--;
        }
        
        if(i<pivotIndex && j>pivotIndex)
        {
            swap(arr[i++],arr[j--]);
        }
    }
    
}

int partition(int arr[], int s, int e)
{
    int count=0;
    int pivot = arr[s];
    for(int i=s+1;i<=e;i++)
    {
        if(arr[i]<=pivot)
        {
            count++;
        }
    }

    int pivotIndex = s + count;
    swap(arr[pivotIndex], arr[s]);

    return solve(arr,s,e,pivotIndex);

    /* Or we can do same here no need to call function
    int i=s,j=e;
    while(i<pivotIndex && j>pivotIndex)
    {
        while(arr[i]<=arr[pivotIndex])
        {
            i++;
        }
        while(arr[j]>arr[pivotIndex])
        {
            j--;
        }
        
        if(i<pivotIndex && j>pivotIndex)
        {
            swap(arr[i++],arr[j--]);
        }
    }

    return pivotIndex;
    
    */
}

void helper(int arr[], int s, int e)
{
    if(s>=e)
    {
        return;
    }

    // partition of array
    int p = partition(arr,s,e);

    // sorting left part
    helper(arr,s,p-1);

    // sorting right part
    helper(arr,p+1,e);

}

void quickSort(int input[], int size) {

    helper(input,0,size-1);
}

int main()
{
    int size = 6;
    int input[1000] = {5,6,0,9,1,4};
    
    quickSort(input,size);
    for(int i=0;i<size;i++)
    {
        cout<<input[i]<<" ";
    }

}

Quick sort c++

/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std; 

// A utility function to swap two elements 
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 

/* This function takes last element as pivot, places 
the pivot element at its correct position in sorted 
array, and places all smaller (smaller than pivot) 
to left of pivot and all greater elements to right 
of pivot */
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far

    for (int j = low; j <= high - 1; j++) 
    { 
        // If current element is smaller than the pivot 
        if (arr[j] < pivot) 
        { 
            i++; // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

/* The main function that implements QuickSort 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
        at right place */
        int pi = partition(arr, low, high); 

        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
} 

// Driver Code
int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    quickSort(arr, 0, n - 1); 
    cout << "Sorted array: \n"; 
    printArray(arr, n); 
    return 0; 
} 

// This code is contributed by rathbhupendra

Source: geeksforgeeks.org

Similar codes

-1 vote230 views1 answer
How to initialize static member variable of a class in c++
C++
0 vote249 views1 answer
Compile c++ MPI Program
C++
1 vote245 views1 answer
Binary exponentiation
C++
20 votes249 views4 answers
Cin getline
C++
0 vote252 views1 answer
Ind the number of digits of a given integer n .
C++
0 vote232 views2 answers
C++ uint8_t header
C++
2 votes244 views1 answer
C++ print colorful
C++
0 vote201 views1 answer
Footnote appears in the middle latex
C++
12 votes230 views2 answers
How can I convert a string in char in c++?
C++
2 votes222 views2 answers
C++ typedef array
C++