Quick sort details

The main introduction of quicksort, and three fast sorting optimization, finally leads to three way quicksort.

For the original article, visit my technology blog, Tomato Tech

Definition (Baidu Encyclopedia)

Quicksort was proposed by C. A. R. Hoare in 1962. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

Algorithmic Steps (Wiki)

Pick an element from the sequence, called pivot,
Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation.
There is a recursive correlation between subarrays of values less than the reference element and those of values greater than the reference element.

Quicksort code Implementation (BASIC)

Analysis of the

First, find the base element;
Partition: All elements smaller than the base value are placed in front of the base value, and all elements larger than the base value are placed behind the base value;
To recursively sort the left and right subarrays

Graph (initial conditions are important)

Partition at a certain time

When e>v, I goes to I ++

When e

e interchangeably, j++, i++
,>

The final state is :(return j)

PHP code implementation

The most important thing to implement is the partition function, and the most important thing to implement the partition function is to initialize the state value.l,l+1)

// Partition arr[l...r]
// return p, such that arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
function partition(&$arr, $l, $r){
	$v = $arr[$l];
	$j = $l;

	for ($i=$l+1; $i <= $r ; $i++) { 
		if ($arr[$i] < $v) {
			swap($arr, $j+1, $i);
			$j++;
		}
	}
	swap($arr, $l, $j);
	return $j;
}

/** * [__quickSort sort arr[l...r]] *@param  [type] &$arr [description]
 * @param  [type] $l    [description]
 * @param  [type] $r    [description]
 * @return [type]       [description]
 */
function __quickSort(&$arr, $l, $r){
	if ($l >= $r) {
		return;
	}

	// Optimize point 1
	// if($r - $l <= 15){
	// insertSortCom($arr, $l, $r);
	// return;
	// }

	$p = partition($arr, $l, $r);

	__quickSort($arr, $l, $p- 1);
	__quickSort($arr, $p+1, $r);
}

function quickSort(&$arr, $n){
	__quickSort($arr, 0, $n- 1);
}
Copy the code

The execution time

MergeSort runs at:0.031744003295898S quickSort runs in the following time:0.02904486656189s
Copy the code

Optimization point 1

Again, I’m going to insert sort the array if it’s less than 16

function __quickSort(&$arr, $l, $r){
	// if ($l >= $r) {
	// return;
	// }

	// Optimize point 1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}

	$p = partition($arr, $l, $r);

	__quickSort($arr, $l, $p- 1);
	__quickSort($arr, $p+1, $r);
}
Copy the code

Optimization point 2

If the sequence is basically ordered

// //main
$n = 100000;
// $arr = generateRandomArray($n, 0, $n);
$arr = generateNearlyOrderedArray($n, 100);
$copy_arr = $arr;
testSort("mergeSort"."mergeSort", $copy_arr, $n);
testSort("quickSort"."quickSort", $arr, $n);
Copy the code

Time comparison of merge sort and quicksort algorithms

MergeSort runs at:0.32358503341675S quickSort runs in the following time:18.838504076004s
Copy the code

Analysis of the

When the array is nearly ordered, quicksort is extremely unbalanced and degenerates into O(N*N) time complexity algorithm

Is there a solution? Yes! Just randomly select the “base number” each time.

Problem solving (code implementation)

Swap ($arr, $l, rand($l, $r));

function partition(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	$j = $l;

	for ($i=$l+1; $i <= $r ; $i++) { 
		if ($arr[$i] < $v) {
			swap($arr, $j+1, $i);
			$j++;
		}
	}
	swap($arr, $l, $j);
	return $j;
}
Copy the code

The execution time

MergeSort runs at:0.21585202217102S quickSort runs in the following time:0.34276294708252s
Copy the code

To optimize the point 3

In the case of a large number of repeating elements

$n = 100000;
$arr = generateRandomArray($n, 0.10);
$copy_arr = $arr;
testSort("mergeSort"."mergeSort", $copy_arr, $n);
testSort("quickSort"."quickSort", $arr, $n);
Copy the code

The elapsed time

MergeSort runs at:0.89260506629944S quickSort runs in the following time:19.236886024475s
Copy the code

Analysis of the

When there are a lot of repeating elements in the sequence, we find that the fast sorting speed is slow, and we have reason to suspect that it may degenerate into O(n* N) time complexity again. In our code, arr[I] = v is placed on the right side, which causes partition to be extremely unbalanced:

Problem solving (code implementation)

** Scenario analysis **

The initial scenario
arr[i++

arr[j–

untili] >= e,j] <= e, swap(arr[j]); The elements that repeat $v are evenly distributed on both sides of the list

A final state

Code implementation

/ * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the second algorithm start -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * /


// Partition arr[l...r]
// return p, such that arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
function partition2(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	// arr[l+1...i) <= v; arr(j...r] >= v
	$i = $l+1;
	$j = $r;

	while (true) {
		while($arr[$i] < $v && $i <= $r){
			$i++;
		}
		while($arr[$j] > $v && $j >= $l+1){
			$j--;
		}
		if ($i > $j) {
			break;
		}
		swap($arr, $i, $j);
		$i++;
		$j--;
	}
	swap($arr, $l, $j);
	return $j;
}


function quickSort2(&$arr, $n){
	__quickSort2($arr, 0, $n- 1);
}

function __quickSort2(&$arr, $l, $r){
	// if ($l >= $r) {
	// return;
	// }

	// Optimize point 1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}

	$p = partition2($arr, $l, $r);

	__quickSort2($arr, $l, $p- 1);
	__quickSort2($arr, $p+1, $r);
}


/ * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- end of the second algorithm -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * /
Copy the code

Running time comparison

MergeSort runs at:1.1809809207916S quickSort runs in the following time:25.186847925186S quickSort2 run time is:0.20458602905273s
Copy the code

As can be seen, the optimized quicksort time complexity is back to O(N*logN). Optimization 2 algorithm can be derived from the three – way fast – platoon algorithm.

Three – way quicksort algorithm

define

Three-way quicksort is an optimized version of quicksort, which divides the array into three segments, namely less than the base element, equal to the base element and greater than the base element. In this way, it can efficiently handle the presence of the same elements in the array. Other characteristics are basically the same as quicksort.

graphic

The initial conditions

If the arr [i++

If the arr [arr[arr[i++, $lt++

If the arr [arr[arr[gt–, $i++

A final state

Code implementation

/ * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the third algorithm start -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * /

// Partition arr[l...r]
// return p, such that arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
function partition3(&$arr, $l, $r){

	swap($arr, $l, rand($l, $r));

	$v = $arr[$l];
	$lt = $l;
	$i = $l + 1;
	$gt = $r + 1;

	while($i < $gt){
		if ($arr[$i] == $v) {
			$i++;
		}elseif ($arr[$i] < $v) {
			swap($arr, $lt+1, $i);
			$lt++;
			$i++;
		}else{
			swap($arr, $gt- 1, $i);
			$gt--;
		}
	}
	swap($arr, $l, $lt);
	return array("lt" => $lt, "gt" => $gt);
}


function quickSort3(&$arr, $n){
	__quickSort3($arr, 0, $n- 1);
}

function __quickSort3(&$arr, $l, $r){
	// if ($l >= $r) {
	// return;
	// }

	// Optimize point 1
	if($r - $l <= 15){
		insertSortCom($arr, $l, $r);
		return;
	}


	$rt = partition3($arr, $l, $r);
	$lt = $rt['lt'];
	$gt = $rt['gt'];

	__quickSort3($arr, $l, $lt - 1);
	__quickSort3($arr, $gt, $r);
}

/ * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the end of the third kind of algorithm -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - * /
Copy the code

Time results

QuickSort2 runs at:0.43507099151611S quickSort3 run time is:0.19537496566772s
Copy the code

You can see that the 3-way quicksort algorithm is still very fast.

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato technology small stack and gold digging home page

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan

Definition (Baidu Encyclopedia)

Algorithmic Steps (Wiki)

Quicksort code Implementation (BASIC)

Analysis of the

Graph (initial conditions are important)

PHP code implementation

Optimization point 1

Optimization point 2

If the sequence is basically ordered

Analysis of the

Problem solving (code implementation)

To optimize the point 3

In the case of a large number of repeating elements

Analysis of the

Problem solving (code implementation)

Three – way quicksort algorithm

define

graphic

Code implementation

Related Posts

[Refactoring practices] How can the observer pattern be used to decouple code?

From the thread pool theory talk about why to read the source code

Python still falls short of Lisp in this area