High speed saving sorting algorithm

Is there a faster sorting algorithm that doesn’t waste space? Quicksort! Doesn’t that sound like a fancy name to me.

Suppose we now sort the 10 numbers 6, 1, 2, 7, 9, 3, 4, 5, 10, 8. Start by picking a random number in the sequence as a reference number (don’t be intimidated by the term, it’s just a reference number, you’ll see what it does later). Just for convenience, let’s use the first number 6 as our base number. Next, we need to place all numbers greater than the base number in the sequence to the right of 6, and all numbers less than the base number to the left of 6, in something like the following arrangement:

3 1 2 5 4 6 9 7 10 8

In its initial state, the number 6 is the first digit in the sequence. So our goal is to move the 6 somewhere in the middle of the sequence, let’s say it’s k. So now we need to find this k, and we have the KTH bit, where everything on the left is less than or equal to 6, and everything on the right is greater than or equal to 6. Think about it. Is there a way you can do that?

The sorting algorithm is very powerful

The method is simple: start with the initial sequence “6, 1, 2, 7, 9, 3, 4, 5, 10, 8”. You go from right to left and you find a number less than 6, and then you go from left to right and you find a number greater than 6, and you swap them. I can use two variables, I and j, to point to the left and right of the sequence. Let’s give these two variables nice names sentry I and Sentry J. Start by having the sentry I point to the far left of the sequence (I =1) and to the number 6. Have the sentry J point to the far right of the sequence (that is, =10) and point to the number.

First, sentry J. Because the base number set here is the leftmost number, it is important that sentry J be first (think for yourself why). The sentry J moves left step by step (j -) until he finds a number less than 6 and stops. Then the sentry I moves to the right step by step (I ++) until it finds a number greater than 6 and stops. Finally, Sentry J stops at the number 5, and Sentry I stops at the number 7.

Now swap the values of the elements pointed to by sentinel I and sentinel J. The sequence after the swap is as follows:

6 1 2 59, 3, 4,7 10 8





This is the end of the first exchange. Next, Sentry J continues to move to the left. (Again, sentry J must start first.) He found four, which is less than the base number six, and stopped. Sentry I also continues to move to the right. He finds 9 (which is larger than the base number of 6, which is sufficient) and stops. At this point, the exchange is performed again, and the sequence after the exchange is as follows:

6 1 2 5 4 3 9 7 10 8

The second exchange ends and the probe continues. Sentry J continued to move to the left. He found 3 (less than the base number 6, which would satisfy him) and stopped again. Sentry I continues to move to the right. Oops! Now Sentry I meets Sentry J, and sentry I and Sentry J both walk up to 3. At this point, Probe ends. We swap base numbers 6 and 3. The sequence after the swap is as follows:

3 1 2 5 4 6 9 7 10 8





This is where the first round of “probing” really ends. At this point, the base number 6 is the cut-off point, and everything to the left of 6 is greater than or equal to 6. And just to review the process, the job of sentry J is to find something less than the base number, and the job of sentry I is to find something greater than the base number, until I meets j.

OK, end of explanation. Now the base number 6 is back in place, and it happens to be the sixth digit in the sequence. At this point, we have split the original sequence into two sequences with 6 as the cut-off point. The sequence on the left is “3, 1, 2, 5, 4” and the sequence on the right is “9, 7, 10, 8”. Then you need to process these two sequences separately. Because the sequence to the left and right of 6 is still very confusing. But it doesn’t matter, now that we know how to do this, we can just simulate the sequence to the left and right of 6. Now let’s deal with the sequence to the left of 6.

The sequence on the left is “3, 1, 2, 5, 4”. Adjust the sequence so that everything to the left of 3 is less than or equal to 3 and everything to the right of 3 is greater than or equal to 3. All right, let’s get started

If your simulation is correct, the sequence after adjustment should be as follows:

2, 1, 3, 5, 4

OK, so now the 3 is back. Next you need to deal with the sequence “2, 1” to the left of 3 and “5, 4” to the right. Adjust the sequence “2 1” with 2 as the base number, and the sequence after processing is “1 2”, by which 2 has been returned. The sequence “1” has only one number and does not require any processing. So far we have finished processing the sequence “2 1” and the resulting sequence is “1 2”. The processing of sequence “5 4” is similar to this method, and the final sequence is as follows:

1 2 3 4 5 6 9 7 10 8

For the sequence “9, 7, 10, 8”, the process is also simulated until a new subsequence cannot be split. You end up with a sequence like this, as follows

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

At this point, the sorting is complete. If you are careful, you may have noticed that each round of quicksort is essentially a round of base numbers, and the sort is finished until all the numbers are in place. The last heroic figure illustrates the process of the whole algorithm.

Why is that?

Quicksort is faster because each swap is a jump compared to bubble sort. Set a reference point for each sort, place all numbers less than or equal to the reference point to the left, and all numbers greater than or equal to the reference point to the right. So instead of doing a bubble sort where you’re swapping between neighboring numbers, you’re swapping a lot more distance. So the total number of comparisons and swaps is reduced, and the speed is naturally increased. Of course, in the worst case, it could still be that two adjacent numbers are swapped. So the worst time for quicksort is the same as the worst time for bubble sort is O(N2), and its average time is O(NlogN). Quicksort is based on an idea called dichotomy. We’ll come back to dichotomy, and we’ll talk about that. Here’s the code

Code implementation:

public class QuickSortExam { public static void main(String[] args) { int arr[] = {5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int low, int high) { int i, j, temp, t; if (low > high) { return; } i = low; j = high; //temp = arr[low]; While (temp <= arr[j] &&i < j) {j--; while (temp <= arr[j] &&i < j) {j--; While (temp >= arr[I] &&i < j) {I ++; } // If (I < j) {t = arr[j]; arr[j] = arr[i]; arr[i] = t; } System.out.println(Arrays.toString(arr)); } arr[low] = arr[I]; arr[i] = temp; // Recursively call the left half array quickSort(arr, low, J-1); // Recursively call the right half of the array quickSort(arr, j + 1, high); }}Copy the code
The output is: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] step [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8] 5 [5, 3, 2, 6, 4, 1, 0, 7, 9, 10, 8] 5 [5, 3, 2, 0, 4, 1, 6, 7, 9, 10, 8] 5 [4, 5, 3, 2, 0, 1, 6, 7, 9, 10, 8] 1 [1, 0, 2, 3, 4, 5, 6, 7, 9, 10, 8] 1 [1, 0, 2, 3, 4, 5, 6, 7, 9, 10, 8] 2 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8] 3 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8] 6 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8] 7 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 8] 9 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 10] 9 [0, 1, 2, 3, 4, 5, 6, 7, 9, 8, 10] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Process finished with exit code 0Copy the code