time complexity of quick sort code example

Example 1: what is time complexity of insertion sort

Time Complexity is: 
If the inversion count is O(n), 
then the time complexity of insertion sort is O(n).

Some Facts about insertion sort:
1. Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[1]
2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms
3. More efficient in practice than most other simple quadratic (i.e., O(n2)) 
algorithms such as selection sort or bubble sort
4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn)
when each element in the input is no more than k places away from its sorted position
5. Stable; i.e., does not change the relative order of elements with equal keys
6. In-place; i.e., only requires a constant amount O(1) of additional memory space
Online; i.e., can sort a list as it receives it

Example 2: quicksort

// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.youtube.com/watch?v=aXXWXz5rF64
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function partition(list, start, end) {
    const pivot = list[end];
    let i = start;
    for (let j = start; j < end; j += 1) {
        if (list[j] <= pivot) {
            [list[j], list[i]] = [list[i], list[j]];
            i++;
        }
    }
    [list[i], list[end]] = [list[end], list[i]];
    return i;
}

function quicksort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length - 1;
    }
    if (start < end) {
        const p = partition(list, start, end);
        quicksort(list, start, p - 1);
        quicksort(list, p + 1, end);
    }
    return list;
}

quicksort([5, 4, 2, 6, 10, 8, 7, 1, 0]);

Example 3: quicksort in code

// A full c++ quicksort algorithm no bs
// quicksort in code

#include <iostream>

using namespace std;

void QuickSort(int arr[], int start, int end);
int Partition(int arr[], int start, int end);
void SwapArrMem(int arr[], int a, int b);

int main()
{

	int arr[4]; //change the size of the array to your desired array size

	cout << "enter " << sizeof(arr) / sizeof(arr[0]) << " numbers. press enter after input" << endl;

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		
		cin >> arr[i];
	}

	cout << endl << "The sorted numbers are:" << endl << endl;



	QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		cout << arr[i] << endl;
	}

}

void QuickSort(int arr[], int start, int end)
{
	if (start >= end) return;

	int index = Partition(arr, start, end);
	QuickSort(arr, start, index - 1);
	QuickSort(arr, index + 1, end);
}

int Partition(int arr[], int start, int end)
{
	int pivotindex = start;
	int pivotvalue = arr[end];
	for (int i = start; i < end; i++)
	{
		if (arr[i] < pivotvalue)
		{
			SwapArrMem(arr, i, pivotindex);
			pivotindex++;
		}
	}
	SwapArrMem(arr, pivotindex, end);
	return pivotindex;
}

void SwapArrMem(int arr[], int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

Example 4: analysis of quick sort

T(n) = 2*T(n/2) + n                        // T(n/2) = 2*T(n/4) + (n/2)    

        = 2*[ 2*T(n/4) + n/2 ] + n
	= 22*T(n/4) + n + n
	= 22*T(n/4) + 2n                       // T(n/4) = 2*T(n/8) + (n/4)

	= 22*[ 2*T(n/8) + (n/4) ] + 2n
	= 23*T(n/8) + 22*(n/4) + 2n
	= 23*T(n/8) + n + 2n
	= 23*T(n/8) + 3n

	= 24*T(n/16) + 4n
	and so on....

	= 2k*T(n/(2k)) + k*n      // Keep going until: n/(2k) = 1  <==> n = 2k    

	= 2k*T(1) + k*n
	= 2k*1 + k*n
	= 2k + k*n               // n = 2k
	= n + k*n
	= n + (lg(n))*n
        = n*( lg(n) + 1 )
       ~= n*lg(n))