preface

Hi everyone, thanks for supporting the first two posts. Today I’m going to give you notes on merge, quicksort, and quickselect, which are three examples of divide-and-conquer algorithms. This time there is the use of stack proof algorithm time limit oh! In addition, the code has been put on the code cloud.

Divide and conquer algorithm

The basic idea of divide-and-conquer algorithm is to decompose a scale N problem into K smaller sub-problems, which are independent from each other and have the same properties as the original problem. The solution of the original problem can be obtained by solving the subproblem. It is a divided objective completion program algorithm, simple problems can be solved by dichotomy. Merge, quick sort, and quick select are three typical examples of divide-and-conquer.

Java corresponding algorithm

General sorting uses the Java provided merging algorithm, collections.sort (..) . Quick selection is generally used to solve TopN problems. The following three algorithms are introduced respectively.

1 merge sort

Introduction to the

Merge-sort is an efficient sorting algorithm based on merging operations.

Algorithm is introduced

The basic operation of the algorithm is to merge two sorted tables. The following example illustrates the merge process:

Algorithm Description

• If N=1, there’s only one element, just return it
• Otherwise, merge the first half and the last half separately to obtain the sorted two parts, and then merge them according to the above algorithm.

Core code Sample

private static <AnyType extends Comparable<? super AnyType>> 
	void mergeSort(AnyType[] a, AnyType[] tmpArray,
				int left, int right) {
 if(left < right) { int center = (left + right) / 2; Center =1 mergeSort(a, tmpArray, left, center); mergeSort(a, tmpArray, center + 1, right); merge(a, tmpArray, left, center + 1, right); }} /** * merge function, basic step of merge sort * @param a raw data array * @param tmpArray merge the third temporary array * @param leftPos to start with the left part, Start with @param rightPos and end with @param rightEnd. */ private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, Int rightEnd = rightPos - 1; int rightEnd = rightPos - 1; int tmpPos = leftPos; Int numElements = rightEnd - leftPos + 1; // mergewhile (leftPos <= leftEnd && rightPos <= rightEnd) {
	    if (a[leftPos].compareTo(a[rightPos]) <= 0) {
		tmpArray[tmpPos++] = a[leftPos++];
	    } else{ tmpArray[tmpPos++] = a[rightPos++]; }}while (leftPos <= leftEnd) {
		tmpArray[tmpPos++] = a[leftPos++];
	}
	while(rightPos <= rightEnd) { tmpArray[tmpPos++] = a[rightPos++]; } // Copy sorted data into the original array, only rightEnd unchanged.for(int i = 0; i < numElements; i++, rightEnd--) { a[rightEnd] = tmpArray[rightEnd]; }}Copy the code

Analysis of the

According to the previous description, the following general formula can be obtained:

I’m going to use the summation, and I’m going to derive it, and I’m going to divide both sides by N

Then multiply both sides by N to get the time bound:

2 Quick Sort

Introduction to the

The basic idea of Quicksort is: By sorting the sorted data into two independent parts, one part of all the data is smaller than the other part of all the data, and then according to this method to the two parts of the data respectively for quick sorting, the whole sorting process can be carried out recursively, in order to achieve the entire data into an ordered sequence

Algorithm is introduced

• Simple step 4

1. If the number of elements in S is 0 or 1, return, or the elements in S are less than CUTOFF, and S will be sorted
2. Take the pivot element V with the median of three numbers
3. Divide S-{v} into two disjoint sets and determine the position of pivot element V:
   
   
   

   

4. Divide and conquer the rest in the following order
   
   
   

   

• For example
• • The median value of the three numbers is pivot element
    
    That is, the median of left end, right end and center is the pivot, (which can actually reduce the number of comparisons by 14%). Put the minimum on the left, the maximum on the right, the median on the second right, and the original median on the second right.
    
    
    

    

• • Split your
    
    
    

    

Core code schematic

/** * @param a raw array * @param left left margin * @param right right margin * @return*/ private static <AnyType extends Comparable<? super AnyType>> AnyType median3(AnyType[] a, int left, int right) { int center=(left+right)/2;if(a[center].compareTo(a[left])<0){
		swapReferences(a, left, center);
	}
	if(a[right].compareTo(a[left])<0){
		swapReferences(a, left, right);
	}
	if(a[right].compareTo(a[center])<0){
		swapReferences(a, center, right);
	}
		swapReferences(a, center, right-1);
	returna[right-1]; } /** * private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] a, int left, int right) {if(left+CUTOFF<=right){// Pivot AnyType pivot=median3(a,left,right); int i=left; int j=right-1;while(true){// I find the element greater than the pivot elementwhile(a[++i].compareTo(pivot)<0); //j finds an element less than the pivotwhile(a[--j].compareTo(pivot)>0);
			if(i<j){
				swapReferences(a, i, j);
			}else{// I >j, this round of segmentation endbreak; } // Swap I with pivots swapReferences(a, I, right-1); // Divide and conquer, quickSort(a,0,i-1); quickSort(a,i+1,right); }else{ insertSort(a, left, right); }}Copy the code

Time complexity

• The worst

• Average case and best case

• Mean case analysis

Let’s say S1, every size is equally likely. Because of this assumption, it can be known that

The average value of is

To sum:

3 Quick Selection

Problem description

Find the KTH least element in the disordered set.

Algorithm is introduced

Processing in accordance with the idea of quick sorting:

1. If S=1, K=1 return the elements in S directly, if

code

/** * Quick selection of core * @param a raw array * @param left left * @param right right * @param k bits to select */ private static<AnyType extends Comparable<? super AnyType>> void quickSelect(AnyType[] a, int left, int right, int k) {if(left+CUTOFF<=right){
	AnyType pivot=median3(a, left, right);
	int i=left;
	int j=right-1;
	while(true) {while(a[++i].compareTo(pivot)<0);
		while(a[--j].compareTo(pivot)>0);
		if(i<j){
			swapReferences(a, i, j);
		}else{
			break;
		}
	}
	swapReferences(a, i, right-1);
	if(k<=i){
		quickSelect(a, left, i-1, k);
	}else if(k>i+1){ quickSelect(a, i+1, right, k); }}else{ insertSort(a, left, right); }}Copy the code

conclusion

1. The average time limit for quicksort and merge sort is NlogN. Java uses merge by default.
2. Fast selection is the classical solution of TopN algorithm, but it is seldom used in my project

Full code address:

Code cloud: Merge & Quicksort: Click to view quick selection: Click to view Github: Merge & Quicksort quick selection