This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Now the IT industry is not as easy to mix as before, too many employees, resulting in a surplus of junior programmers, which indirectly leads to the company’s recruitment threshold is becoming higher and higher, requiring programmers to master more and more knowledge. Algorithms are also a topic that has been debated for a long time. Should programmers master algorithms at all? Different people have different answers, but in fact, many companies have certain requirements for algorithm, some companies directly ask candidates to handwritten algorithm questions during the interview. This has produced a great test for the technical requirements of programmers, so in the face of today’s environment, we must master the algorithm, in order to occupy a place in the future work. So what I’m going to do is I’m going to introduce a couple of sorting algorithms that I hope will help you.

1. Bubble sort

Bubble Sort is a relatively simple sorting algorithm. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if they are in the wrong order (from largest to smallest, from A to Z). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted. The algorithm gets its name from the fact that larger elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

Presentation:

The code is as follows:

@Test
public void bubbleSort(a) {
	int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
	// Count the number of comparisons
	int count = 0;
	// The first round of comparison
	for (int i = 0; i < arr.length - 1; i++) {
		// Second round of comparison
		for (int j = 0; j < arr.length - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// Switch places
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
			count++;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("All together :" + count + "Time");
}
Copy the code

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] a total of 105 comparisonsCopy the code

I’m sure you can write this code, and that’s how you write bubble sort. We can use a Boolean variable to optimize this generation. In the above program, we have found that the number of comparisons is 105. Optimized code:

@Test
public void bubbleSort(a) {
	int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
	// Count the number of comparisons
	int count = 0;
	for (int i = 0; i < arr.length - 1; i++) {
		boolean flag = true;
		for (int j = 0; j < arr.length - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// Switch places
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = false;
			}
			count++;
		}
		if(flag) {
			break;
		}
	}
	System.out.println(Arrays.toString(arr));
	System.out.println("All together :" + count + "Time");
}
Copy the code

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] a total of 95 comparisonsCopy the code

We first define a Boolean variable to true at the start of the loop, and then set the value to false if elements are swapped. So, we can use this Boolean variable to determine if any elements were swapped. If the Boolean variable is true, then the array elements have not been swapped. If the Boolean variable is true, then the array elements are sorted. It can also be seen from the results that the number of comparisons is indeed reduced a lot.

2. Select sort

Selection sort is a simple and intuitive sorting algorithm. It works by first picking the smallest (or largest) element from the data elements to be sorted, storing it at the beginning of the sequence, then finding the smallest (or largest) element from the remaining unsorted elements, and placing it at the end of the sorted sequence. And so on until the total number of data elements to be sorted is zero. Selection sort is an unstable sort method.

Presentation:

The code is as follows:

@Test
public void SelectionSort(a) {
	int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
	for (int i = 0; i < arr.length - 1; i++) {
		int index = i;
		for (int j = 1 + i; j < arr.length; j++) {
			if (arr[j] < arr[index]) {
				index = j;// Save the subscript of the smallest element}}// The index of the smallest element has been found
		// Swap the smallest element with the preceding element
		int temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
	}
	System.out.println(Arrays.toString(arr));
}
Copy the code

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code

The implementation is also very simple. First, an index variable is defined in the outer loop to store the value of I. This is to avoid repeated comparison, because at the end of each round of comparison, the first I elements are sorted, so there is no need to compare again, just start from I. The following comparison is based on the index position of the element, if the index position of the element after the comparison is the minimum, there is no need to swap, do not move. If an element smaller than the one at index is found, the index of that element is assigned to index, and the comparison continues until the comparison is complete. After the comparison, the index obtained is the minimum value in the array. In this case, only the element at index and the element at I need to be swapped.

3. Insert sort

Insertion sort is a simple, intuitive and stable sorting algorithm. If there is an orderly data sequence, the requirements in this has been inserted into a row of good data sequence number, but still request after inserting the data sequence order, this time using a new method for sorting, insertion sort, insertion sort of basic operation is to insert a data to the already sorted data in order, The algorithm is suitable for sorting a small amount of data, and the time complexity is O(n^2). It’s a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array but excludes the last element (the array has one more space to insert), and the second part contains only that element (the element to be inserted). After the first part is sorted, insert the last element into the sorted first part. The basic idea of insertion sort is that each step inserts a record to be sorted into the appropriate position in the previously sorted array according to the size of its key code value until all inserts are complete.

Presentation:

The code is as follows:

@Test
public void InsertionSort(a) {
	int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
	for (int i = 1; i < arr.length; i++) {
		// Define the number to be inserted
		int insertValue = arr[i];
		// Find the index before the number to be inserted
		int insertIndex = i - 1;
		while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}
		arr[insertIndex + 1] = insertValue;
	}
	System.out.println(Arrays.toString(arr));
}
Copy the code

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code

So in this case, because we don’t know the elements of the array, we can only think of the first element of the array as an ordered sequence, so starting from the second element of the array is the element we need to find the insertion position. So the outer loop starts at 1, stores arr[I], the current second element, and finds the index of the element that preceded it, i-1, through a while loop. We should exit the loop when insertIndex is less than 0, because we are comparing all the previous elements. During the comparison, if the element to be inserted is smaller than the previous element, the previous element is moved back, that is, the value of the previous element is assigned directly to the position of the element to be inserted. Because the element to be inserted is already saved in the beginning, you simply assign the value of the element to be inserted to its predecessor. Because insertIndex decays in the while loop, its preceding element should be subscript insertIndex + 1. If the value of the element to be inserted is greater than the value of the previous element, then the while loop is not entered, so that the position after insertIndex + 1 is still where it was, so the value does not change after the assignment, and so on.

4. Hill sort

Traditional insertion sort algorithm, there are some problems in some scenarios, such as,3,4,5,1 [2] such an array, when we carry on the insertion sort, found to insert number is 1, and if you want to insert the 1 to the front, need to go through four steps, respectively will be 5, 4, 3, 2 back. So the conclusion is that if the smaller number is the number we need to insert, then the efficiency will be lower. Given the shortcomings of this scenario, Hill sort was born, which is a more efficient version of insert sort.

Let’s start with the concept of Hill sort:

Shell’s Sort, also known as “Diminishing Increment Sort”, is a more efficient and improved version of direct insert Sort. Hill sort is an unstable sort algorithm. The method is named after D.L.Shell, who proposed it in 1959. Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

Presentation:

If you don’t understand the animation, here are some more static images:

Code implementation:

@Test
public void ShellSort(a) {
	int[] arr = { 3.44.38.5.47.15.36.26.27.2.46.4.19.50.48 };
	for (int gap = arr.length / 2; gap > 0; gap /= 2) {
		// Group array elements
		for (int i = gap; i < arr.length; i++) {
			// Iterate over the elements in each group
			for (int j = i - gap; j >= 0; j -= gap) {
				// Swap elements
				if (arr[j] > arr[j + gap]) {
					int temp = arr[j];
					arr[j] = arr[j + gap];
					arr[j + gap] = temp;
				}
			}
		}
	}

	System.out.println(Arrays.toString(arr));
}
Copy the code

Running results:

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code

So in the program above, the array length is 15, so in the first round, the array is divided into 15/2 = 7 groups, and the elements of each group are iterated separately. In the first round, the spacing between the groups is 7, so the number of groups divided is really just the spacing between the elements. The elements of each group can then be compared, then swapped, and so on.