First we explore the idea of ​​the algorithm

Ideas: Quicksort array divided into two lists by comparing each element of the list with a selected element is called key element. These elements less than or equal key element to be taken forward and in the first list, the larger particles are put on the back key and the list of second child. Keep sharing such until the list are the same length 1

Content
1. The idea of ​​the algorithm
2. Install quicksort
3. Removal recursive quicksort
4. Using tail recursion in quicksort
5. Use quicksort is available in C
6. Sort the array structure by quicksort

There are ways to select the following key elements:
– Select the element at the bottom make heads or key elements.
– Select the element in the middle of the list as key elements.
– Select the median element in 3 element head, standing in the middle and end as key elements.

– Choose a random element as key elements (Either is selected for avoiding the special case)

Illustrations:

Install in C:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi

void quickSort(int *a, int l, int r)
{
	srand(time(NULL));	//khoi tao tham so ham rand()
	int key = a[l + rand() % (r-l+1)];	//lay khoa la gia tri ngau nhien tu a[l] -> a[r]
	//int key = a[(l+r)/2];
	int i = l, j = r;

	while(i <= j)
	{
		while(a[i] < key) i++;		// tim phan tu ben trai ma >=key
		while(a[j] > key) j--;		// tim phan tu ben trai ma <=key
		if(i <= j)
		{
			if (i < j)
				swap(int, a[i], a[j]);	// doi cho 2 phan tu kieu int a[i], a[j].
			i++;
			j--;
		}
	}
	//bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
	if (l < j) quickSort(a, l, j);	// lam lai voi mang a[l]....a[j]
	if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

int main ()
{
	int i, arr[] = { 40, 10, 100, 90, 20, 25 };
	quickSort(arr, 0, 5);
	for (i=0; i<6; i++)
		printf ("%d ", arr[i]);
	return 0;
}

The algorithm is installed from the line 6 to flow 29. In that line 21 swap(int, the[in], the[j]); is a constant for permutation 2 of a[in] and a[j] defined in line 4 and it is equivalent to the following code (you can change it directly in):

{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

You can also see the following code, with this code I have in the screen every variation of array, of l, r, in, j help them accurately observed change in step:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi

void quickSort(int *a, int l, int r)
{
	srand(time(NULL));	//khoi tao tham so ham rand()
	int key = a[l + rand() % (r-l+1)];	//lay khoa la gia tri ngau nhien tu a[l] -> a[r]
	//int key = a[(l+r)/2];
	int i = l, j = r;
	printf("\n\nl = %d   r = %d    select: key = %d  (random) ",l, r, key);

	while(i <= j)
	{
		//printf("n");
		printf("\n\n\ti : %d", i);
		while (a[i] < key) { i++; printf(" -> %d",i); }
		printf("\n\tj : %d", j);
		while (a[j] > key) { j--; printf(" -> %d",j); }
		if(i <= j)
		{
			if (i < j)
			{
				swap(int, a[i], a[j]);	// doi cho 2 phan tu kieu int a[i], a[j].
				printf("\n\tswap(a[%d], a[%d])  swap(%d, %d)", i, j, a[i], a[j]);
			}
			i++;
			j--;
			printf("\n\tarr[] : ");
			for (int i=0; i<8; i++)
				printf ("%d ", a[i]);
		}
	}
	//bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
	if (l < j) quickSort(a, l, j);	// lam lai voi mang a[l]....a[j]
	if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

int main ()
{
	int i, arr[] = { 2, 8, 7, 1, 3, 5, 6, 4  };
	int n = 8;
	printf("\n\nArray befor sort: ");
	for (i=0; i<n; i++)
		printf ("%d ", arr[i]);

	quickSort(arr, 0, n-1);

	printf("\n\nArray after sort: ");
	for (i=0; i<n; i++)
		printf ("%d ", arr[i]);
}

We found that the efficiency of the algorithm depends on the value selected markers (or key elements).

– Best case: each partition we have chosen elements median (larger particles or by half the number of elements and less than or equal half the remaining elements) as a landmark. When this sequence is partitioned into two equal parts, and we need log2(n) once the partition is sorted finish. I also visible in each partition we need to browse through n elements. So the complexity in the best case of O(nlog2(n)).

– Worst case: each part we choose to target elements the maximum value or minimum as a landmark. When this sequence is partitioned into two parts are not: part only one element, rest with n-1 elements. Therefore, n times we need to partition the new arrangement is complete. So the complexity in the worst case of O(n2).

* So we have the complexity of the following Quick Sort:
– Best case: The(nlog2n)
– Worst case: The(n2)
– Where the average: The(nlog2n)

Reduction in quic Sort recursive

The nature of the recursive algorithm parameters are stored in a stack recursion (stack) to turn retrieved handling. So if you are experiencing massive data will easily cause stack overflow. When removal of recursive recursive algorithm, with each call to the recursive quicksort we change by storing the values ​​of the left and right 2 subsequence in 2 Sl and Sr stack, when you need to call out. In addition we can also save common values ​​on the left and right 1 Stack, when removed will take 2 consecutive elements.

b1: Initialization 2 Stack empty Sl, Sr to save the values ​​l and r values ​​of each subarray.
b2: Initially the range in question from 0 to n-1, we note l to r in Sl and Sr
b3: Retrieved from Sl l, r from Sr
b4: Partition Series A[The] .. The[R] to 2 Series A[the]..The[j] and A[in]..The[r]
b5: If l < l and j j stored in Sl and Sr, If i < r i and r stored in Sl and Sr,
b6: If the stack is not empty back b3.

Here is the code installed, the code can use to stack in C , If you do not want or are not familiar with C stack can refer to a building 1 stack always.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>		// thu vien de khoi tao tham so cho ham rand()
#include<stack> 		// Su dung Stack trong C++
#define swap(type, a, b) {type temp = a; a = b; b = temp; }

using namespace std;

void quickSortUnRecursive(int *a, int l, int r)
{
	srand(time(NULL));
	stack Sl;		// Stack left
	stack Sr;		// Stack right
	Sl.push(l);			// dua phan tu dau tien l vao Sl
	Sr.push(r);			// dua phan tu dau tien r vao Sl

	while(!Sl.empty())	// trong khi stack khong rong
	{

		int l = Sl.top(); Sl.pop();		// lay phan tu dau tien trong Sl l ra
		int r = Sr.top(); Sr.pop();		// lay phan tu dau tien trong Sr r ra
		int key = a[l + rand() % (r-l+1)];
		int i = l, j = r;
		while (i <= j)		// phan hoach thanh 2 day con
		{
			while (a[i] < key) i++;
			while (a[j] > key) j--;

			if(i <= j)
			{
				if (i < j)
					swap(int, a[i], a[j]);
				i++;
				j--;
			}
		}
		if (l < j) { Sl.push(l); Sr.push(j); }	// dua 2 dau mut l va j vao Sl va Sr
		if (i < r) { Sl.push(i); Sr.push(r); }	// dua 2 dau mut i va r vao Sl va Sr
	}
}

int main ()
{
	int i, arr[] = { 40, 10, 100, 90, 20, 25 };
	quickSortUnRecursive(arr, 0, 5);
	for (i=0; i<6; i++)
		printf ("%d ", arr[i]);
	return 0;
}

Using tail recursion in Quick Sort

We can also use tail recursion algorithm to construct Quick Sort algorithm, ie only one recursive call of the function, but to do this we will have to choose the key element is the first element of the array or the last to arrange. Can we analyze this case as follows:

First, we determine the distribution ranges into 2 the following array:

int partition(int *a, int l, int r)
{
	int key = a[r];		// xac dinh khoa
	int i = l - 1, j;	// khoi tao i, j
	for (j=l; j<r; j++)	// duyet mang
		if (a[j] <= key) //neu a[j] <= key
		{
			i++;
			swap(int, a[i], a[j]);	// hoan vi
		}
	swap(int, a[i+1], a[r]);	// hoan vi voi phan tu khoa
	return i + 1;	// tra ve vi tri cua khoa
}

After dividing the range we are 2 row, array element left is the key less than or equal, the right is larger series of key elements.

Now we construct Quick Sort tail recursion as follows:

void TailRecursiveQuicksort(int *a, int l, int r)
{
	while (l<r)
	{
		int q = partition(a,l,r);	//lay vi tri khoa
		TailRecursiveQuicksort(a, l, q-1);		// sap xep day ben trai
		l = q + 1;		// khi day ben trai sap xep xong ta chuyen sang day ben phai
	}
}

Moreover, purpose so that when called recursively, Stack of us may have contained as little as possible, so we improved a bit algorithm as follows:

void TailRecursiveQuicksort_2(int *a, int l, int r)
{
	while (l<r)
	{
		int q = partition(a,l,r);
		if (q < (l + (r-l)/2))	//Neu vi tri khoa < 1/2 do dai day thi sap xep ben phai
		{
			TailRecursiveQuicksort_2(a, l, q-1);
			l = q + 1;
		}
		else	//Neu vi tri khoa >= 1/2 do dai day thi sap xep ben trai
		{
			TailRecursiveQuicksort_2(a, q + 1, r);
			r = q-1;
		}
	}
}

Use Quick Sort built in C

In C library has built for us qsort function and we can use it right.

#include<stdio.h>
#include<stdlib.h>

int arr[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a > *(int*)b );
}

int main ()
{
	  int n;
	  qsort (arr + 1, 4, sizeof(int), compare);
	  for (n=0; n<6; n++)
		 printf ("%d ",arr[n]);
	  return 0;
}

In the function call qsort: qsort (scars + 1, 4, sizeof(int), compare);
scars + 1 is the starting position sorted array, here is equivalent to a sort of element[1] = 10 and arrangement 4 element ie from a[1] to a[4].
sizeof(int) size 1 elements in the array. If the array type is actually going there is sizeof(float).
compare built with the following structure is used to define the array sorted ascending or descending

int compareMyType (const void * a, const void * b)
{
	return ( *(MyType*)a @ *(MyType*)b );
}

In that MyType is the type of array elements. “@” is an operation that is defined. In the library have defined for us 3 operations >, ==, <. In this example we use *(int*)the > *(int*)b to arrange increased, vice versa if *(int*)b > *(int*)will arrange a decrease.

Sort Quick Sort array structures available in C

Next we will do if we have 1 array of molecular structure Struct and want to sort by 1 Certain fields.

We will define 1 operations “@” to compare 1 Certain fields in the function bool operator then rebuild function int compare steel operations have been developed:

#include<iostream>
#include<cstdlib>
using namespace std;

struct St
{
	string name;
	int scores;
};

bool operator * ( const St &t, const St &u )	// dinh nghia phep toan "*"
{
	return t.name > u.name;	//sap xep tang dan theo ten
}

bool operator/( const St &t, const St &u )	// dinh nghia phep toan "/"
{
	return t.scores < u.scores;	//sap xep giam dan theo diem
}

int compare_name (const void * a, const void * b)
{
	return ( *( St*)a * *(St*)b );	//chi duoc su dung phep toan "*" de sap xep
}

int compare_scores (const void * a, const void * b)
{
	return ( *( St*)a / *(St*)b );	//chi duoc su dung phep toan "/" de sap xep
}

int main ()
{
	St arr[] = { {"Hien", 9}, {"Cuong", 7}, {"Nhung", 8}, {"Nam", 6} };

	int n = sizeof( arr ) / sizeof( St );
	qsort (arr, n, sizeof(St), compare_name);

	cout << "\nDanh sach xap xep tang dan theo ten:\n";
	for (int i = 0; i < n; i++ )
		cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;

	qsort (arr, n, sizeof(St), compare_scores);
	cout << "\nDanh sach xap xep giam dan theo diem:\n";
	for (int i = 0; i < n; i++ )
		cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;

	return 0;
}

In the above code I've used the special symbols * and / (which is more accurate than the normal symbols are used as multiplication and division) to define operations for arranging. We could use some characters such as math %, ^, *, /, +, -, >, =, < to define new operations.

Articles with references and translations from several sites:
recurial.com/programming/using-tail-recursion/
mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html
The book: introduction to algorithms
staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap08.htm
cplusplus.com/reference/cstdlib/qsort/?kw = qsort