Sort 2 bubble sort and quick sort (recursive and non recursive explanation)

Preface

One 、 Bubble sort

Bubble sort ： It's an exchange sort , The basic idea is this , Compare keywords of adjacent records , Exchange if reverse order , Until there are no records in reverse order .

Of course , Our protagonist today is the fast platoon to be introduced later , I believe my friends are already familiar with bubbling , I'll just briefly mention .

Code ：

// Bubble sort : Two two comparisons 
void BubblSort(int *arr,int n)
{
    
	for (int end = n; end > 0; end--)
	{
    
		int flag=0;// Optimize , Prevent already in an orderly situation , Let's make meaningless comparisons 
		for (int i = 1; i < end; i++)
		{
    
			if (arr[i]>arr[i - 1])
			{
    
				Swap(&arr[i], &arr[i - 1]);
				flag=1;
			}
		}
		if(flag==0)
			break;
	}
}

summary ：

1. Time complexity ：O(N²)
2. Spatial complexity ：O(1)
3. stability ： Stable

Two 、 Quick sort

The basic idea of fast platoon ： The records to be arranged are divided into two independent parts by one sort , The keywords of one part of the records are smaller than those of the other , Then the two parts of records can be sorted separately , In order to achieve the purpose of orderly sequence .

How to divide it into these two parts ？

• Find a keyword in the to be sorted （key） To segment , We usually choose the leftmost or rightmost .

1. Left and right pointer method

1. Define two variables to record Subscripts , Respectively left=0、right=n
2. Look for the ratio on the right key Small value , Look for the left side key Big value
3. The details are , Move first right Come to find Xiao , After finding , Move again left Come and find big , Then exchange , When left>=right When , stop it , Exchange again left and key Value on .（ The first split is completed ）
4. Then a recursive

When we were writing code , It should be analyzed into two parts first
1. First write the first split ,
2. Then write several times .

Code ：

void Swap(int *p, int *q)
{
    
	int temp = *p;
	*p = *q;
	*q = temp;
}

void PartSort1(int* arr, int begin, int end)
{
    	
	if (begin >= end)
		return;
	int left = begin,right=end;
	int keyi = left;// In the above introduction key The subscript 
	while (left < right)
	{
    
		// Looking for a small 
		while (left<right&&arr[right]>=arr[keyi])
		{
    
			right--;
		}
		// Looking for big 
		while (left<right&&arr[left]<=arr[keyi])
		{
    
			left++;
		}
		// In exchange for 
		Swap(&arr[left], &arr[right]);
	}	
	Swap(&arr[keyi], &arr[left]);
	int meeti = left;// Meeting point 
// The interval of the last two parts [begin,keyi-1][keyi+1,end]
// recursive 
	PartSort1(arr, begin, meeti - 1);
	PartSort1(arr, meeti+1,end);

}

2. Excavation method

The digging method is a little similar to the left and right pointer method above .

1. Find the leftmost keyword key And record ,arr[0] For a pit , Define two variable record subscripts ,left=0、right=n
2. On the right, look for Xiao , After finding , Fill in the small value to arr[0] in , The small value found is located in a new pit
3. Then look for the big one on the left , After finding , Put the big value into the new pit , Their position has become a new pit , To and fro .
4. When left>=right when , stop it , And then put key Put it in the new pit （ The first split is over ）
5. recursive

Code ：

// Excavation method , Quick line up 
void  PartSort4(int* arr, int begin, int end)
{
    
	if (begin >= end)
		return;
	int key = arr[begin];
	int left = begin;
	int right = end;
	while (left < right)
	{
    
		// Looking for a small 
		while (left < right&&arr[right]>=key)
		{
    
			--right;
		}
		// Put it in the pit on the left , A new pit is formed on the right 
		arr[left] = arr[right];
		// Looking for big 
		while (left< right&&arr[left]<=key)
		{
    
			left++;
		}
		// Put it in the pit on the right , A new pit is formed on the left 
		arr[right] = arr[left];
	}
	arr[left] = key;// hold key Put it into the new pit 
	int meeti = left;
	// The interval of the last two parts [begin,meeti-1][meeti+1,end]
	// recursive 
	PartSort4(arr, begin, meeti - 1);
	PartSort4(arr, meeti+1, end);
}

3. Front and back pointer method

1. We can know from the meaning of the title , Define two variables to record Subscripts , And the subscript is the context ,left=0、right=left+1.
2. Don't forget , We are here to split , So we need to define a keyword （key）, Take the leftmost value as the keyword , And save the subscript keyi.
3. arr[right]<arr[left],left++, In exchange for , then right++（ Here I do some optimization in the code ）
4. until right>n when , Just stop , Then exchange arr[left] and arr[keyi]（ The first split is completed ）
5. recursive （ Some optimization is done in recursion ： When the data is very large , Recursion all the time may overflow the stack , We can sort after a period of time , Sort directly by insertion ）

Code ：

void  PartSort3(int* arr, int begin, int end)
{
    
	if (begin >= end)
		return;
	if (end - begin > 17)// Optimize 
	{
    
		int left = begin;
		int right = left + 1;
		int keyi = begin;
		while (right <= end)
		{
    
			
			if (arr[right] < arr[keyi] && ++left != right)
			{
    
				Swap(&arr[right], &arr[left]);
			}
			++right;
		
		}
		Swap(&arr[left], &arr[keyi]);
		keyi = left;// Now left The position of is the place of division 
		// The interval of the last two parts [begin,keyi-1][keyi+1,end]
		// recursive 
		PartSort2(arr, begin, keyi - 1);
		PartSort2(arr, keyi + 1, end);
	}
	else
	{
    
		InsertSort(arr + begin, end - begin + 1);		
	}
}

4. Fast platoon optimization （ Take the three Numbers ）

After reading the above three methods , We should have found , When an array is ordered , Each time we segment, we only get subsequences that are one record smaller than the last time , Notice that the other one is empty , At this time, our time complexity is O(N²)

therefore , We can take the middle of three numbers to optimize

• Find subscript 0 Value , And the subscript is n Value , And the subscript is （n+0）/2 Value , Use their median as key

Code ：

// Take the three Numbers , Find the middle value 
int GetMidIndex(int *arr,int left,int right)
{
    
	int mid = (left + right) >> 1;
	if (arr[left] > arr[mid])
	{
    
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return left;
		else
			return right;
	}
	else//arr[left]<=arr[mid]
	{
    
		if (arr[left]>arr[right])
			return left;
		else if (arr[mid] < arr[right])
			return mid;
		else
			return right;		
	}
}

5. Iterative implementation （ Non recursive ）

This is our big meal , It is said that fast scheduling is implemented by recursion , How can we use non recursive implementation ？

We have to use stack or queue to achieve this

1. The stack is to store the subscript of the interval we want to sort
2. Put the subscript of the interval we want to do on the stack , And then put in , Take it out again .（ Each time you put it in, it's different ）
3. Every time you take out a section , We all sort this interval in a single run
4. Then divide the interval subscript into two parts , Then put it on the stack , Come and pick it up next time
5. The flag to judge the end is whether there are unprocessed intervals in the stack
6. The condition to judge whether the interval subscript needs to be put into the stack is , Whether the number of elements in the interval is greater than 1
7. After the platoon , Destroy the stack

Code ：

// Non recursive fast scheduling , iteration 
void QuickSortNonR(int* a, int left, int right)
{
    
	// Create a stack 
	Stack st;
	// Initialization stack 
	StackInit(&st, 10);
	// Enter the large range first 
	if (left < right)
	{
    
		StackPush(&st, right);
		StackPush(&st, left);
	}
	// Stack is not empty. , It indicates that there is an unprocessed interval 
	while (StackEmpty(&st) != 0)// Termination conditions 
	{
    
		left = StackTop(&st);
		StackPop(&st);
		right = StackTop(&st);
		StackPop(&st);
		// Quickly arrange a single sequence 
		int div = PartSort5(a, left, right);// This function is used to sort in a single run 
		// [left div-1]
		//  The greater than 1 The number of intervals continues to be stacked 
		if (left < div - 1)// Conditions for judging whether it is necessary to continue sorting 
		{
    
			StackPush(&st, div - 1);
			StackPush(&st, left);
		}

		// [div+1, right]
		if (div + 1 < right)
		{
    
			StackPush(&st, right);
			StackPush(&st, div + 1);
		}
	}
	StackDestroy(&st);// Finally, destroy the stack 
}

summary ：

1. The overall performance and usage scenarios of quick sort are quite good , That's why we call it quick sort
2. Time complexity ：O(N*logN)
3. Spatial complexity ：O(logN)
4. stability ： unstable

summary

If you have any questions, please point them out , Learning together , See you next time .