📗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
sort(A,i);
sort(B,j);
merge(A,B,E,i,j);//Merge A and B into E
}
else
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++];
else
d[result++] = c[second++];
}
//consider the rest
if (first > endOfFirst)
{
//second paragraph left
for(int q = second;q <= endOfSecond;q++)
d[result++] = c[q];
}
else
{
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
merge(x,y,i,i+segmentSize-1,i+2*segmentSize-1);
i = i+2*segmentSize;
}
//There are less than 2*segmentSize elements left
if(i+segmentSize < n)
merge(x,y,i,i+segmentSize-1,n-1);
else
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 log2n
- 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
j--;
}
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
i++;
}
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