quick_sort.cpp File Reference

Quick sort algorithm. More...

#include <cstdlib>
#include <iostream>

Include dependency graph for quick_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors

Functions
int	sorting::partition (int arr[], int low, int high)
void	sorting::quickSort (int arr[], int low, int high)
void	show (int arr[], int size)
int	main ()

Detailed Description

Quick sort algorithm.

Implementation Details - Quick Sort is a divide and conquer algorithm. It picks and element as pivot and partition the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick the first element as pivot
2. Always pick the last element as pivot (implemented below)
3. Pick a random element as pivot
4. Pick median as pivot

The key process in quickSort is partition(). Target of partition is, given an array and an element x(say) of array as pivot, put x at it's correct position in sorted array and put all smaller elements (samller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time

Function Documentation

main()

int main

(

void

)

Driver program to test above functions

           {
    int size;
    std::cout << "\nEnter the number of elements : ";
 
    std::cin >> size;
 
    int *arr = new int[size];
 
    std::cout << "\nEnter the unsorted elements : ";
 
    for (int i = 0; i < size; ++i) {
        std::cout << "\n";
        std::cin >> arr[i];
    }
    quickSort(arr, 0, size);
    std::cout << "Sorted array\n";
    show(arr, size);
    delete[] arr;
    return 0;
}

show()

void show	(	int	arr[],
		int	size
	)

                               {
    for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
    std::cout << "\n";
}