Sorting has been a common algorithm in the interview, whether you are looking for a job, or postgraduate entrance examination, work use, cope with the final exam, etc., is very common, is also very important, so the common eight sorting algorithm, a comb. I hope it helps. This is the first article on selection sorting.

First, the principle of selection sorting

The principle of selection sort is easy to understand, so let’s do an example. These days students have to start military training, military training when you need to row position according to the height of the height. Suppose a group of students are arranged in a disorderly line on the playground. The drill sergeant goes from the front of the line to the back of the line and finds the lowest student to switch with the first student in the current line. The drill sergeant then comes back and finds the second-lowest student to switch with the second student in the current line. So the instructor ran back and forth again and again, and finally lined up the team.

Selection sort works the same way.

Given a set of records, the smallest record is obtained after a first round of comparison from beginning to end, and the position of the first record is swapped; Then the second comparison is made to other records excluding the first record, and the minimum record is exchanged with the second position record. This is repeated until only one comparison record remains.

We can use a GIF to illustrate this

(1) Red represents the current smallest element

(2) Green indicates the element being compared

(3) Yellow represents the elements that have been arranged

It doesn’t matter if you don’t understand the above, let’s look at it with another picture:

If you don’t understand it, you’ll have to read it a few more times. Let’s take a look at implementing it in code.

Two, code implementation

Let’s go straight to the code;

public static int[] selectSort(int[] arr) {
    // The first part
	if (arr == null || arr.length <= 0) {
		return null;
	}
    // Part 2
	for (int i = 0; i < arr.length; i++) {
        // Section 1 of Part 2
		int temp = arr[i];
		int flag = i; 
        // Section 2 of Part 2
		for (int j = i + 1; j < arr.length; j++) {
			if(arr[j] < temp) { temp = arr[j]; flag = j; }}// Section 3 of Part 2
		if (flag != i) {
			arr[flag] = arr[i];
			arr[i] = temp;
		}
	}
	return arr;
}
Copy the code

This is implemented in the Java language, and the code looks a little bit complicated, so let’s break it down,

Part I:

Here we first need to rule out some exceptions, and note that this code is used in any sorting algorithm. So you just need to understand it and remember it, whatever algorithm you’re writing it with.

Part II:

The second part is the part that actually implements the sorting, so this part is also divided. Start from start to finish.

(1) Section 1

// Section 1 of Part 2
int temp = arr[i];
int flag = i; 
Copy the code

This one is a little bit simpler, you declare some constants, temp is the position of the current array pointer. Flag represents the smallest or largest element subscript in the comparison process. You can kind of view it as the lowest student in this comparison. And some of you who didn’t.

(2) The second section

// Section 2 of Part 2
for (int j = i + 1; j < arr.length; j++) {
	if(arr[j] < temp) { temp = arr[j]; flag = j; }}Copy the code

If arr[j] is less than temp, swap places. Go to the end of the line and find the smallest one. The smallest.

(3) Section 3

// Section 3 of Part 2
if(flag ! = i) { arr[flag] = arr[i]; arr[i] = temp; }Copy the code

In this comparison, find the smallest person and switch places with the person in front. That’s the whole sorting algorithm. Now we can enter any set of data to test.

public class Test {
	// The array inside the array is arbitrary
	static int arr[] = { 36.38.98.21.76.13.46.53 };
	public static void main(String[] args) {
		System.out.println(Arrays.toString(arr));
		int[] result=selectSort(arr); System.out.println(Arrays.toString(result)); }} before sort [36.38.98.21.76.13.46.53] After sorting [13.21.36.38.46.53.76.98]
Copy the code

At this point, we have written the general selection sorting algorithm, but if the interviewer only asked to write this, to be honest, it is relatively simple, the most important is his deformation.

Improvement of selection sorting algorithm

Why improve? There are many disadvantages to the previous approach. In the previous algorithm, you could only pick the largest element or the smallest element per run, but it’s one element. So if I have N elements, I have to make N minus one trips. Now let’s think about it another way.

Each run not only records the largest element but also the smallest element, so you can kill two birds with one stone. You only have to do N over 2 trips. Save time and effort.

	// Select sort improved version
	   public static int[] selectSort(){
	       int minPoint;  // Store the smallest element
	       int maxPoint;  // Stores the largest element
	       int len = arr.length;
	       int temp;
	       // Only N/2 runs
	       for(int i=0; i<len/2; i++){ minPoint= i; maxPoint= i;for(int j=i+1; j<=len-1-i; j++){// The minimum value of each trip
	              if(arr[j]<arr[minPoint]){  
	                 minPoint= j;
	                 continue;
	              }
	              // The minimum value of each trip
	              else if(arr[j]>arr[maxPoint]){ maxPoint= j; }}// Swap the minimum with the previous value
	          if(minPoint! =i){ temp= arr[i]; arr[i]= arr[minPoint]; arr[minPoint]= temp;if(maxPoint== i){ maxPoint= minPoint; }}// Swap the maximum value with the following value
	          if(maxPoint! =len-1-i){  
	              temp= arr[len-1-i];
	              arr[len-1-i]= arr[maxPoint]; arr[maxPoint]= temp; }}return arr;
	   }
Copy the code

The improved method is also simpler, with only one more data recorded. We can use the same test code for testing. The effect is the same.

Iv. Algorithm analysis

This is a little bit easier to understand, you have N students, you have N minus 1 or N over 2 trips. So the time must be order N^2. In the case of a large number of swaps, selection sort is actually more efficient than bubble sort.