Data Structures | Chapter 18: Divide and Melt

📗Algorithm idea of ​​divide and rule

🔑 Break down the problem into two or more smaller problems

🔑 Solve each small problem separately

🔑Combine the answers to each small question to get the solution to the original question

📚 Merge Sort

🐇Sorting Thoughts by Dividing and Solving

  • Sorting algorithm using divide and conquer method:
  • Arrange n elements in non-increasing order
    • If n is 1, the algorithm terminates;
    • otherwise
      • split this collection of elements into two or more subcollections
      • Sort each subcollection separately
      • Merge sorted subsets into one set
  • That is, first make each subsequence in order, and then make the subsequences in order

🐇 Pseudo-code of sorting algorithm

template<class T>
void sort( T E, int n)
{//Sort n elements in E, k is a global variable
	if(n >= k)
		i = n/k;
        j = n-i;
		make A Include E in the front i elements
        make B Include E the rest of j elements
		merge(A,B,E,i,j);//Merge A and B into E 
        Use the insertion sort algorithm to E put in order

🐇 Divide and rule the time of the sorting algorithm

Let t(n) be the worst-case time spent by the divide-and-match sorting algorithm

But k=2, t(n) is the smallest, t(n)=O(nlogn)

🔑 Merge Sort - Divide and Sorting Algorithm with k=2

🐇Merge sort flow chart

🐇 Merge sort implementation

🥕 Two groups of merging functions are realized

🍃Two groups are merged to realize the idea

  • Merge two ordered segments
    • c[startOfFirst:endOfFirst] and c[endOfFirst+1:endOfSecond]
  • result segment d[startOfFirst:endOfSecond]
  • first and second are respectively the cursors of the two segments to be merged, and result is the cursor to track the position of the next element in the merged result segment.
  • Initial: first=startOfFirst, second = endOfFirst+1, result = startOfFirst;
  • When the two merged segments have not been processed, loop:
    • Compare the elements pointed by first and second, place the smaller one in the position pointed by result, and add 1 to the cursor and result for the smaller one
  • Copy the elements in the unprocessed segment to d in turn.

🍃Two sets of merge implementation code

template<class T>
void merge(T c[],T d[],int startOfFirst,int endOfFirst,
int endOfSecond)
	int first = startOfFirst,//Cursor for the first paragraph
		second = endOfFirst+1,//Cursor for the second paragraph
    	result = startOfFirst;//result section cursor
	//When the two merged segments have not been processed, the merge will continue
    while((first <= endOfFirst) && (second <= endOfSecond))
        if(c[first] <= c[second]) 
            d[result++] = c[first++];
            d[result++] = c[second++];
	//consider the rest
	if (first > endOfFirst)
        //second paragraph left
		for(int q = second;q <= endOfSecond;q++)
			d[result++] = c[q];
        for(int q = first;q <= endOfFirst;q++)
            d[result++] = c[q];

🥕 One-step merge implementation

Merge adjacent segments whose size is segmentSize, and realize the process:

template<class T>
void mergePass(T x[],T y[],int segmentSize,int n)
	int i = 0;
	while(i <= n-2*segmentSize)
    {//Merge two adjacent segments of size segmentSize
        i = i+2*segmentSize;
	//There are less than 2*segmentSize elements left
    if(i+segmentSize < n)
        for(int j = i;j <= n-1;j++)
			y[j] = x[j];//copy the last paragraph to y

🥕Merge sort mergeSort implementation

template<class T>
void mergeSort(T a[],int n)
{//Sort a[0:n-1] using the merge sort algorithm
	T*b = new T[n];
	int segmentSize = 1;//segment size
    while(segmentSize < n)
		mergePass(a,b,segmentSize,n);//merge from a to b 
        segmentSize += segmentSize;
		mergePass(b,a,segmentSize,n);//merge from b to a 
        segmentSize += segmentSize;

🐇Merge sort complexity analysis

  • Space complexity: O(n)
  • Time complexity: O(nlogn)
    • Merge times: l o g 2 n log_2n log2​n
  • Merge sort is stable

📚Quick Sort

🐇Basic idea of ​​quick sort

  • Take a number from the sequence as the base number

  • Partition

    • Put all numbers larger than this number to the right of it
    • All numbers less than or equal to it are placed to its left
  • Repeat the second step for the left and right intervals until there is only one number in each interval

🐇Quick sort implementation code

Quick Sort Application in Experiment 13

void Sort(node *array,int low,int high)//to sort
	if(low > high) return;//Scheduled, not working
	int i,j;
	node index;
	node index;
	index = array[low];//Define the base number 
	i = low;
	j = high;
 	while(i < j)
  		while(i < j && array[j].weight >= index.weight)
  			//Find the number smaller than the reference number from right to left
		if(j > i) 
			//Exchange array[i] and array[j], and move i one bit to the right 
			array[i++] = array[j];
		while(i < j && array[i].weight < index.weight)
			//From left to right, find the one that is larger than the base number
		if(j > i) 
			//Exchange array[i] and array[j], and shift j to the left
			array[j--] = array[i];
 	array[i] = index;//Datum point homing
 	Sort(array,low,i-1);//Recursively call quicksort for elements smaller than the reference point
 	Sort(array,i+1,high);//Recursively call quicksort for elements larger than the reference point

🐇Quick sort complexity analysis

🥕 Space Complexity

Recursive stack space: O(n)

🥕Time complexity

  • Worst case: the pivot element is the minimum or maximum element in the array, left is always empty (or right is always empty), time O( n 2 n^2 n2)
  • Best case: the number of elements in left and right is roughly the same, time O(nlogn)
  • Average complexity O(nlogn)

🥕Median Quick Sort

The median quicksort algorithm has better average performance.

  • It is not necessary to use a[leftEnd] as the base number
  • Take the element whose size is in the middle among {a[leftEnd], a[(leftEnd +rightEnd)/2], a[rightEnd]} as the reference number.

🔑 Reference blog

Super God Sort Summary Blog

C++ merge sort

Tags: Algorithm data structure

Posted by supermars on Tue, 17 Jan 2023 09:22:14 +0530