Merge sort in a simple way
Someone once said that
It turns out it was Kurt Vonnegut.
I did not seek to prove this statement. I tried to refute my stupidity.
Suppose we have two arrays of numbers sorted in ascending order.
')
It is necessary to merge them into one ordered array.
This is a merge sort task.
What it is? There is an answer on the Internet, there is a description of the algorithm, but I did not understand it from one sitting and decided to figure it out myself. To do this, you need to understand the basic principle of the algorithm so that you can recreate the algorithm from memory in relation to its task.
Let's go gradually and use what lies on the surface: we will take one element from each array in turn, compare them and “merge” into one array. We will put the smaller element first, the larger - the second. Then after the first pass, everything is fine:
And after the second pass is not very:
It is clear that it is necessary to compare the elements with those already added.
Let we have a certain temporary buffer from elements compared at each step. After the first pass, 21 and 10 will fall into it. After the comparison, we will move the smaller element 10 from the buffer to the resulting array and leave the larger element 21, because we do not know what will be behind it.
After the second pass, the buffer will be 21, 23 and 11. It is not clear what to do with them, it is possible to compare more than two elements, but not so simple.
Let us then agree that we will take one element from each array into this buffer. Since it is easier to compare two elements with each other, and indeed we have two entities - two arrays. Then, after the second pass, the buffer will be 21 and 11, because the “representative” of the first array in the buffer is already there — this is 21. We compare them and send the smaller one to the resulting array. Then after the second pass we will have in the resulting array:
And in the buffer - 21.
On the third pass, we take into the buffer from the second array 41, because the “representative” of the first array in the buffer has remained. Compare 21 and 41, and finally remove from buffer 21.
After the third pass, we will have in the resulting array:
On the fourth pass we will compare two values ​​from the buffer - 41 and 23. In the resulting array will be:
That is just now - on the fourth, and not on the second pass - the result was correct. It turns out that in the loop one should remember the current index for each array, and the cycle itself can be a length equal to the sum of the lengths of the arrays.
What shall we do when the resulting array consists of:
The buffer will be 3000 from the second array, and in the first - all the elements run out? Since we have sorted the arrays, we simply take 3000 from the buffer and the remaining 5000. That is, we need to check for each index whether we have exceeded the number of elements in each of the arrays.
And if we have no sorted arrays? Usually the task is to sort one array. Then merge sorting can also be used.
Let the first array (for example, take several elements from it) has the following arrangement of elements:
We will sort it. Once it is easier to compare two elements, then we split the array equally into two:
and
It will turn out on three elements. Lot! We split each array equally, we get four arrays:
We now sort each of the arrays by simply comparing the first and second elements (where they are):
And we will merge back the previous algorithm - through the buffer. After the first merge, we get two arrays:
And again we merge - already in one array:
So we sorted the merge array.
Thus, merge sorting implies partitioning the array equally until a few smaller ones are obtained from one array - no more than two elements in size. Two elements can be easily compared with each other and ordered according to their requirements: ascending or descending.
After splitting, an inverse merge follows, in which at one moment of time (or during a loop pass) one element from each array is selected and compared to each other. The smallest (or largest) element is sent to the resulting array, the remaining element remains relevant for comparison with an element from another array in the next step.
Example of sorting by increasing two sorted arrays:
Here:
a1 and a2 are arrays to be merged;
a3 is the resulting array;
i and j are indices for arrays a1 and a2, respectively, which point to the current elements at each step and form the same buffer.
The first two conditions check that the indices do not exceed the limits of the number of elements in the arrays. The third and fourth conditions provide the movement to the array of the smallest element from the first array and from the second, respectively.
Let's format the given code as a recursive function, which will divide arrays as long as possible with the parameters corresponding to the whole array at the first call, its halves at the second and third calls, etc.
Here:
a is an array;
lo - the position of the first element in the array (for the first iteration = 0);
hi is the position of the last element in the array (for the first iteration = a.length - 1).
Java Algorithms
Cat's Cradle Quotes
... any scientist who was not a charlatan.
It turns out it was Kurt Vonnegut.
I did not seek to prove this statement. I tried to refute my stupidity.
Suppose we have two arrays of numbers sorted in ascending order.
')
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; It is necessary to merge them into one ordered array.
int[] a3 = new int[a1.length + a2.length]; This is a merge sort task.
What it is? There is an answer on the Internet, there is a description of the algorithm, but I did not understand it from one sitting and decided to figure it out myself. To do this, you need to understand the basic principle of the algorithm so that you can recreate the algorithm from memory in relation to its task.
Started for health
Let's go gradually and use what lies on the surface: we will take one element from each array in turn, compare them and “merge” into one array. We will put the smaller element first, the larger - the second. Then after the first pass, everything is fine:
10, 21 And after the second pass is not very:
10, 21, 11, 23 It is clear that it is necessary to compare the elements with those already added.
Start again
Let we have a certain temporary buffer from elements compared at each step. After the first pass, 21 and 10 will fall into it. After the comparison, we will move the smaller element 10 from the buffer to the resulting array and leave the larger element 21, because we do not know what will be behind it.
After the second pass, the buffer will be 21, 23 and 11. It is not clear what to do with them, it is possible to compare more than two elements, but not so simple.
Let us then agree that we will take one element from each array into this buffer. Since it is easier to compare two elements with each other, and indeed we have two entities - two arrays. Then, after the second pass, the buffer will be 21 and 11, because the “representative” of the first array in the buffer is already there — this is 21. We compare them and send the smaller one to the resulting array. Then after the second pass we will have in the resulting array:
10, 11 And in the buffer - 21.
On the third pass, we take into the buffer from the second array 41, because the “representative” of the first array in the buffer has remained. Compare 21 and 41, and finally remove from buffer 21.
After the third pass, we will have in the resulting array:
10, 11, 21 On the fourth pass we will compare two values ​​from the buffer - 41 and 23. In the resulting array will be:
10, 11, 21, 23 That is just now - on the fourth, and not on the second pass - the result was correct. It turns out that in the loop one should remember the current index for each array, and the cycle itself can be a length equal to the sum of the lengths of the arrays.
We are coming to an end, but suddenly
What shall we do when the resulting array consists of:
10, 11, 21, 23, 24, 40, 41, 50, 65, 75, 76, 78, 77, 86, 98, 101, 190, 900, 1100, 1200, 2100, 2200, 2300, 2400, 2500, The buffer will be 3000 from the second array, and in the first - all the elements run out? Since we have sorted the arrays, we simply take 3000 from the buffer and the remaining 5000. That is, we need to check for each index whether we have exceeded the number of elements in each of the arrays.
Complicate the task
And if we have no sorted arrays? Usually the task is to sort one array. Then merge sorting can also be used.
Let the first array (for example, take several elements from it) has the following arrangement of elements:
2100, 23, 40, 24, 2, 1. We will sort it. Once it is easier to compare two elements, then we split the array equally into two:
2150, 23, 40 and
24, 2, 1. It will turn out on three elements. Lot! We split each array equally, we get four arrays:
2100, 23 40 24, 2 1 We now sort each of the arrays by simply comparing the first and second elements (where they are):
23, 2100 40 2, 24 1 And we will merge back the previous algorithm - through the buffer. After the first merge, we get two arrays:
23, 40, 2100 1, 2, 24 And again we merge - already in one array:
1, 2, 23, 24, 40, 2100 So we sorted the merge array.
In the dry residue
Thus, merge sorting implies partitioning the array equally until a few smaller ones are obtained from one array - no more than two elements in size. Two elements can be easily compared with each other and ordered according to their requirements: ascending or descending.
After splitting, an inverse merge follows, in which at one moment of time (or during a loop pass) one element from each array is selected and compared to each other. The smallest (or largest) element is sent to the resulting array, the remaining element remains relevant for comparison with an element from another array in the next step.
Express in code (java)
Example of sorting by increasing two sorted arrays:
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int[] a3 = new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k<a3.length; k++) { if (i > a1.length-1) { int a = a2[j]; a3[k] = a; j++; } else if (j > a2.length-1) { int a = a1[i]; a3[k] = a; i++; } else if (a1[i] < a2[j]) { int a = a1[i]; a3[k] = a; i++; } else { int b = a2[j]; a3[k] = b; j++; } } Here:
a1 and a2 are arrays to be merged;
a3 is the resulting array;
i and j are indices for arrays a1 and a2, respectively, which point to the current elements at each step and form the same buffer.
The first two conditions check that the indices do not exceed the limits of the number of elements in the arrays. The third and fourth conditions provide the movement to the array of the smallest element from the first array and from the second, respectively.
Merge sort function
Let's format the given code as a recursive function, which will divide arrays as long as possible with the parameters corresponding to the whole array at the first call, its halves at the second and third calls, etc.
private void SortUnsorted(int[] a, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; SortUnsorted(a, lo, mid); SortUnsorted(a, mid + 1, hi); int[] buf = Arrays.copyOf(a, a.length); for (int k = lo; k <= hi; k++) buf[k] = a[k]; int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = buf[j]; j++; } else if (j > hi) { a[k] = buf[i]; i++; } else if (buf[j] < buf[i]) { a[k] = buf[j]; j++; } else { a[k] = buf[i]; i++; } } } Here:
a is an array;
lo - the position of the first element in the array (for the first iteration = 0);
hi is the position of the last element in the array (for the first iteration = a.length - 1).
Links
Java Algorithms
Cat's Cradle Quotes
Source: https://habr.com/ru/post/281675/
All Articles