Quick Sort in C++

Quick Sort:

Here is link for the detailed explanation and algorithm for quicksort: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more

Here is the algorithm for quickSort:

QuickSort(arr, start, end)

• Define pivot as arr[end]
• Get the location of the point of the pivot in resulting array, pivot=partition(arr, start, end)
• quicksort(arr, start, pivot-1)
• quicksort(arr, pivot+1, end)

Here is the code that implements this in c++:

void quicksort(int* arr, int start, int end){
	if(start<end){
	int part = Partition(arr, start, end);
	quicksort(arr, start, part-1);
	quicksort(arr, part+1, end);
	}
	}

Here is the algorithm for the partition of the array: The detailed explanation for partition function can be found here: https://rishabhjainiitbhu.blogspot.com/2019/08/sorting-algorithms.html#more 

Partition(arr, start, end)

• Define pivot = arr[end]
• p_index = start //this is the position we will place pivot the at.
• loop for i=start up to the end
• ..... if arr[i]<pivot
• ..........swap(arr[p_index], arr[i])
• ...........p_index++
• Once the loop is completed swap(arr[p_index], pivot).

Here is the code that implements this:

int Partition(int* arr, int start, int end){
	int pivot = arr[end];
	int p_index = start;
	for(int i=start;i<end;i++){
	if(arr[i]<=pivot){
	swap(&arr[i], &arr[p_index]);
	p_index++;
	}
	}
	swap(&arr[end], &arr[p_index]);
	return p_index;
	}