Quick sort -- after lorguka TLE, I finally chose three-way cutting

Melo~ 2021-11-25 17:57:27

Write in the front

This article , Let's talk about sorting algorithms , We've talked about it before Simple insert sort and ta Optimized version of Shell Sort , In this section, we will contact a more “ senior ” Algorithm. -- Quick sort .
In the valley of Los Angeles , Encountered a card optimization problem , If you don't optimize the fast platoon , There will be several points TLE Of , Later, we can do all kinds of optimization around this problem , Let's start with quick sort .

Ideas

If our computer could run every second 10 100 million times , So right. 1 Hundreds of millions of them , bucket Sorting only needs 0.1 second , and Bubbling Sorting requires 1 Ten million seconds , achieve 115 It's been a long time , Isn't it scary ? Is there a sort algorithm that can be faster without wasting space ? That's it “ Quick sort ”!
Suppose we're right now “** 6 1 2 7 9 3 4 5 10 8” this 10 Number to sort . First of all, find any number in the sequence as the base number ( Don't be frightened by this term , This is a number for reference , You'll know what it's used for later ). For convenience , Just let the first number 6 As a benchmark . Next , You need to put all... In this sequence Larger than the reference number The number of is placed in 6 Of On the right , Than The reference number is small The number of is placed in 6 Of On the left **, It's like this arrangement .

3 1 2 5 4 6 9 7 10 8

In the initial state , Numbers 6 At the end of the sequence 1 position . Our goal is to 6 Move to a position in the middle of the sequence , Suppose this position is k. Now we need to find this k, And take The first k position It's the dividing point , All the numbers on the left are less than or equal to 6, The numbers on the right are greater than or equal to 6.

The method is actually very simple : From the initial sequence “ 6 1 2 7 9 3 4 5 10 8” Start at both ends “ Probe ”. First find a smaller one from right to left 6 Number of numbers , And then go from left to right and find one greater than 6 Number of numbers , And then exchange them . You can use it here Two variables i and j, Point to the left and right of the sequence respectively . Let's give these two variables a nice name “ sentry i” and “ sentry j”. At the beginning, let the sentry i To the far left of the sequence ( namely i=1), Point to numbers 6. Let the sentry j To the far right of the sequence ( namely j=10), Point to numbers 8.
image.png
image.png
image.png

Picture source : 《 AHA algorithm 》

Complete flow chart

image.png

If mid Take the leftmost word , When itself is in order , Will become a bubble sort , become n square

image.png

( Example ) Luogu 1177 Quick sort

https://www.luogu.com.cn/problem/P1177

Wrong version

No optimization , Order will TLE

#include <iostream>
#include<cstdio>
int a[1000001];// Define global variables , These two variables need to be used in the subfunction
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Recursive method
void quicksort(int left, int right) {
// For example, it can be concluded that if the left is greater than or equal to the right, it will return to ?
// Greater than is :index just ==right, And then we're going to (index+1,right)
if (left >= right) {
return;
}
// Default datum index It's the one on the far left , And i Start on the left ,j From the right
int i = left, j = right, index = left;
// refactoring
// The big premise , The two didn't meet
while (i != j) {
// You have to judge i<j, Because the big premise outside , It may destroy
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
// if i,j Haven't met yet
if (i < j) {
swap(&a[i], &a[j]);
}
}
// When you come out i,j Must meet
swap(&a[i],&a[index]);
// take i Assigned to datum
index = i;
quicksort(left, index - 1);
quicksort(index + 1, right);
}

image.png

First get mid, Then let the left heel mid In exchange for

Because it is a unilateral search , The last two points are TLE

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>
void swap(int arr[], int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void QuickSort(int arr[], int left, int right)
{
int i, pivot;
if (left >= right)
return;
pivot = left;
swap(arr, left, (left + right) / 2);
for (i = left + 1; i <= right; i++) // Unilateral search , This can be a two-way search
if (arr[i] < arr[left])
swap(arr, i, ++pivot);
swap(arr, left, pivot);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
int main()
{
int n;
int *arr;
int i;
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++)
scanf("%d", arr + i);
QuickSort(arr, 1, n);
for (i = 1; i <= n; i++)
printf("%d ", arr[i]);
return 0;
}

image.png

Just the last point TLE 了 , And the last point , just Constant column The situation of

#include <iostream>
#include<cstdio>
int a[100010];// Define global variables , These two variables need to be used in the subfunction
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Recursive method
void quickSort(int left, int right) {
// For example, it can be concluded that if the left is greater than or equal to the right, it will return to ?
// Greater than is :index just ==right, And then we're going to (index+1,right)
if (left >= right) {
return;
}
// Default datum index It's the one on the far left , And i Start on the left ,j From the right
int i = left, j = right, index ;
int mid=(left+right)/2;
swap(&a[left],&a[mid]);
index=left;
// refactoring
// The big premise , The two didn't meet
while (i != j) {
// You have to judge i<j, Because the big premise outside , It may destroy
while (a[j] >= a[left]&&i<j) {
j--;
}
while(a[i] <= a[left]&&i<j){
i++;
}
// if i,j Haven't met yet
if (i < j) {
swap(&a[i], &a[j]);
}
}
// When you come out i,j Must meet
swap(&a[i],&a[index]);
index = i;
quickSort(left, index - 1);
quickSort(index + 1, right);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort(0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}

replay mid( Consider the constant column )

You haven't hit the triple yet , Pick up to mid If it is the smallest, it will degenerate to bubbling n square

#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quickSort(int* arr, int low, int high) {
// If the length does not meet the requirements , Go straight back to
if (low >= high) {
return;
}
int left = low;
int right = high;
// Select the middle as the benchmark , Note that take the middle value , Instead of Subscripts , Because the subscript may change in subsequent exchanges
// such as left Go to the mid here , and right It stopped mid On the right , Then I will exchange ,arr[mid] It's changed
int mid = arr[(low + high) >> 1];
while (left <= right) {
// Notice that it's less than , If it is less than or equal to , The constant column will always left Move , and right Don't move , Become n square
while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Recursively call
//right At the end of interval one
quickSort(arr,low, right);
//left Went to the head of interval two
quickSort(arr, left, high);
}
int main()
{
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a[i];
}
quickSort(a,1,n);
for (i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

flow chart

From here mid yes 60

image.png

here left and right Have met

  • then left Find that the conditions are not met ,86>mid(60),left still 86
    • right Meet the conditions ,right Go to --, Go to the 15 Stop there
  • then left dissatisfaction <=right, Just start recursion
    • Recursive interval ① yes : [42,15] ( Are less than or equal to 60)
    • Section ② yes : [86,68] ( Greater than or equal to 60)
 while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
// Recursively call
//right At the end of interval one
quickSort(arr,low, right);
//left Went to the head of interval two
quickSort(arr, left, high);

problem

Because I didn't put the hub in the right position , As a result, the length of the finally separated interval will be one more element : Pivot ( Will this affect time efficiency )

If you test with a certain amount of data , The gap in time efficiency is not very big .

** Combine three numbers to take the middle ( Temporary God )

#include<cstdio>
#include<iostream>
#include"RcdSqList.h"
using namespace std;
//int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Take the three Numbers
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort(int* arr, int low, int high) {
// If the length does not meet the requirements , Go straight back to
if (low >= high) {
return;
}
int left = low;
int right = high;
// Select the middle as the benchmark , Note that take the middle value , Instead of Subscripts , Because the subscript may change in subsequent exchanges
// such as left Go to the mid here , and right It stopped mid On the right , Then I will exchange ,arr[mid] It's changed
// Call triple fetch , Get the middle number
int mid = arr[getmid(arr, low, high)];
while (left <= right) {
// Notice that it's less than , If it is less than or equal to , The constant column will always left Move , and right Don't move , Become n square
while (arr[left] < mid) {
left++;
}
// Also note that it is greater than
while (arr[right] > mid) {
right--;
}
// Note here that it is less than or equal to , For convenience left and right Jump directly to the left and right of the hub
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
// Recursively call
//right At the end of interval one
quickSort(arr, low, right);
//left Went to the head of interval two
quickSort(arr, left, high);
}
int main()
{
int n, i;
/*cin >> n;*/
/*for (i = 1; i <= n; i++)
{
cin >> a[i];
}*/
int a[100] = { 0,42 ,90,30,86,42,15,57,20 };
quickSort(a, 1, 8);
for (i = 1; i <= 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
}

summary

Finally, download the test points , Then I read the blog , Find the reason for the timeout , It's actually completely orderly
Then take the standard answer debug once , Finally found the difference , It's the constant column when both of them move , I'm just a mobile , It degenerates into n Squared

Be careful

want < No, not <=

** To enlarge the problem , such as j Go straight to the left , Zoom in until you walk all the way i Where are you going !

The feeling from watching the dark horse video ....
The problem is very serious , Will become n square
If you put the benchmark to the far left , If it is in order, it will time out

xxxx Pivot to choose the value with the middle size , To solve a completely orderly situation ( Get three out of three .)

  • Note that taking the middle value here does not mean taking the middle value of the interval , But the size is Head and tail and Interval median Three values are arranged In the middle the
    • If you take the value in the middle of the interval , It doesn't solve the problem of complete order , such as 5 4 1 2 3 , take mid be equal to 1, It's the smallest case again , Last mid Put it in the right place ( That is, the first position ), Recursion to his left and right , It doesn't have the effect of turning the original interval into two halves , Just got the section on the right , It's equivalent to just reducing one element ( similar Bubbling Just put an element in the right place )

Give Way left++ The condition should be < Number ! , Let me go after the exchange left++,right--, This solves the case of constant Columns

If we don't move after the exchange , that > You have to change it to >=, This will move , But it becomes a single pointer movement , Or degenerate into n Squared

After the exchange moves ,left and right It's just the beginning and end of two intervals

** Three way cutting method

https://www.luogu.com.cn/problem/P1177( It's still a template question )

Let's look at the code first

#include<cstdio>
#include<iostream>
using namespace std;
int a[100010];
// Exchange element positions
void swap(int* a, int* b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Take the three Numbers
int getmid(int* array, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (array[left] <= array[right])
{
if (array[mid] < array[left])
return left;
else if (array[mid] > array[right])
return right;
else
return mid;
}
else
{
if (array[mid] < array[right])
return right;
else if (array[mid] > array[left])
return left;
else
return mid;
}
}
void quickSort_2(int rcd[], int low, int high) {
if (low >= high) {
return;
}
// Call triple fetch , Get hub location
int pivot=getmid(rcd,low,high);
// Put the pivot value in low Location ( In exchange for )
swap(&rcd[low],&rcd[pivot]);
// The pivot value is equal to rcd[low]
int pivotVal = rcd[low];
//i Used to traverse an interval
int left, right, i;
// Traverse the interval directly from the next position of the hub
left = low, right = high, i = low + 1;
// Traverse the entire interval
while (i <= right) {
// If less than the hub value
if (rcd[i] < pivotVal) {
// You have to put it in front , Follow left In exchange for
swap(&rcd[i], &rcd[left]);
// After the exchange ,i In exchange for one i The value in front , It must have been compared , therefore i++
i++;
//left In exchange for one i The value of the original position , Also compared , therefore left++
left++;
}
// If greater than the hub value
else if(rcd[i]>pivotVal)
{
// You have to put it in the back , Follow right In exchange for
swap(&rcd[i], &rcd[right]);
//right In exchange for one i The value of the original position , Also compared , therefore right++
right--;
//i Immobility , Because it's the other one i The new value behind , I haven't compared
}
// Equal to
else
{
i++;
}
}
quickSort_2(rcd, low, left - 1);
quickSort_2(rcd, right + 1, high);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
quickSort_2(a,0, n - 1);
for (int i = 0; i < n; i++) {
i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
}

Rough flow chart

Here, let's default that the pivot is the leftmost element , Easy to understand ( In the actual situation, press the code above to take the middle followed by the leftmost exchange )

Use one i To traverse this interval , I need one more left And a right The pointer

  • When rcd[i] Greater than the hub value , Like in the picture 90
  • When rcd[i] Less than the hub value , Like in the picture 20
  • When rcd[i] When equal to the pivot value , Like in the picture 42

See the text description in the figure for details

So in summary , If the position is a The value that has been compared with the hub value , Or change to a value that has been compared with the hub value ( It would be You need to update Check his pointer position )
image.png

advantage

  • Reduce the comparison of repeated elements , Because the repeating elements are already arranged as a single part in one sort , After that, you only need to sort other elements that are not equal to the repeating element .

At the end

  • here we are Quick line up here , In fact, it has involved some recursive Knowledge , Related to recursion is actually “ Binary search ”、“ Merge sort ” etc. , This column will also continue to update relevant knowledge , Welcome to study together !
Please bring the original link to reprint ,thank
Similar articles

2021-11-25

2021-11-25

2021-11-25

2021-11-25