Select sort (illustration +c code)

Algorithm principle ：

Selection sort is a simple and intuitive sorting algorithm . It works on the principle of ：

First, find the smallest in the sequence （ Big ） Elements , Put it at the beginning of the sequence as the sorted sequence ;

then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , Put it at the end of the sorted sequence ;

Repeat the above steps , Until all elements are sorted .

One 、 Image simulation   Selection sort   The process

We choose ten numbers 0~9 As our sort number , And break it up . Then we will arrange them in ascending order . Here's the picture ：

  The process of sorting is to repeat the steps in the above principle in a cycle , Now let's simulate the image in a round by round cycle .

1、 The first cycle

① Initialize the minimum value

Before formal sorting , Let's initialize first , The task of initialization is to select a minimum value , Of course , It is impossible for the computer to know which is the minimum value before starting the comparison . So we have to assume a , First, use the minimum value of this assumption to compare with each value , Finally, the real minimum value is obtained .

Here we choose the first number 5 As the minimum value of initialization assumption .

② Find the minimum

Now let's take the hypothetical minimum 5 Compare with each value .

When the computer is held 5 Go to the 0 when , comparison ,0 smaller , At this time, the computer will 5 Put back , Take it 0 Then compare with each remaining value .

 

In fact, you can already see 0 It is the smallest of these ten numbers , But according to the principle of selective sorting , The computer is still required to compare with the rest one by one , That is to say 7 It can be determined that this number is the minimum value . You need to know that there is such a process , Here we don't use images to simulate one by one , Please fill in the picture by yourself .

The next? , Let's go straight to the minimum Put at the end of the sorted sequence . Of course, this is the first cycle , The sorted sequence has not yet been generated .0 It is the beginning number of the sorted sequence .

③ Location switching

When the minimum value is found , We are going to put the minimum value in front of the sequence . In fact, it is location Exchange . This round of position exchange is digital 5 And number 0 The exchange of positions .

After exchanging ,0 Is the sorted sequence , No further operations will be performed on the sorted sequence .

2、 The second cycle

① Initialize the minimum value

The second round of initialization begins , Let's continue to choose the assumed minimum , This time, , We still choose the first number as the assumed minimum , It should be noted that ,0  It is already a sorted sequence , We have to choose the first number from the unordered sequence , That is to say (5、1、8、6、2、3、4、9、7) Numbers in an unordered sequence 5.

② Find the minimum

When 5 Go to the 1 when , comparison 1 Than 5 Small establishment .

take 5 Put back , Take it 1.

When 1 Compare them bit by bit 7 when , This round of searching for the minimum value is completed , determine 1 That's the minimum . 

③ Location switching

take 1 Move to sorted sequence (0) At the end of .

After exchanging ,(0,1) It's an ordered sequence ,(5、8、2、3、4、9、7) It's an unordered sequence  

3、 The third cycle

① Initialize the minimum value

Select the first number of the unordered sequence 5 As the assumed minimum .

② Find the minimum

When 5 Compare them bit by bit 2 when , Less than established ,5 Put back .

 

  Take it 2, Compare them bit by bit 7 when , determine 2 That's the minimum .

 

③ Swap places

4、 The fourth cycle

 ① Initialize the minimum value

② Find the minimum

8 Go to the 6 when , Less than established ,8 Put back .

Take it 6 Compare bit by bit , Go to the 5 Time is less than established ,6 Put back .

  Take it 5 Compare bit by bit , Go to the 3 Time is less than established ,5 Put back .

  Take it 3 Compare bit by bit , Compared to 7 When determining 3 That's the minimum .

③ Swap places

take 3 Move to sorted sequence (0、1、2) The end of the sequence .

After four cycles , We have sorted the smallest four numbers , Completing the final sorting requires ten rounds of such a cycle . The purpose of each cycle is to find the minimum value , And then at the end of the sorted sequence . There is no repetition of images . You can understand the idea . Next , We enter the code design phase .

Two 、 Program code design （C Language ）

Code description ：

1、selection_sort Select sorting function for , The formal parameter in its parameter list needs to receive two values ：“ Array ” and “ The length of the array ”.

2、 There's a variable in the function min, Subscript used to record the minimum .

3、 There is an external for loop , Used to traverse each element of the array

, external for The loop is nested inside a layer for loop , The inner loop is used to find the minimum , Record minimum subscript .

4、 Exit the inner layer for There are three exchange statements after the loop , Used to move the minimum value to the end of the sorted sequence .

C The language code ：

#include<stdio.h>

void selection_sort(int *arr,int len)
{   
	int min;                          // The subscript used to store the minimum value 
	
	for (int i = 0; i<=len; i++)
	{   min = i;                     // Initialize the minimum value of the selection hypothesis , The first number of the unordered sequence is selected ,
                                     // Here is the subscript 
	    for (int j = i; j<=len; j++)
	    {
			if (arr[j]<arr[min])     // If smaller values are encountered , Then record the minimum subscript 
			{
				min = j;
			}
		}
		// Inner loop exit , The minimum value is determined 
		// Move the minimum value to the end of the sorted sequence 
		int tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
	}
}

int main()
{
	int arr[] = {5,0,1,8,6,2,3,4,9,7};
	int len = sizeof(arr) / sizeof(int);
	printf(" Value to be sorted ：");
	for (int i = 0; i <= len - 1; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	printf(" Sorted values ：");
	selection_sort(arr,len-1);// Call the select sort function 
	for (int i = 0; i <= len - 1; i++)
	{
		printf("%d ", arr[i]);
	}
}

Running results ：