Sort an array is the process of distributing all elements in a certain order. Very often this is useful. For example, in your inbox, emails are displayed based on the time they were received; new emails are considered more relevant than those you received half an hour, an hour, two or a day ago; when you go to your contacts list, names are usually in alphabetical order because it's easier to find something. All of these cases involve sorting the data before actually outputting it.
How does sorting work?
Sorting data can make searching within an array more efficient not only for people, but also for computers. For example, consider a case where we need to find out whether a certain name appears in a list of names. To find out, we need to check each element of the array against our value. Searching an array with many elements may be too inefficient (costly).
However, let's assume that our array of names is sorted alphabetically. Then our search begins with the first letter of our value and ends with the letter that comes next in the alphabet. In this case, if we got to this letter and did not find the name, then we know for sure that it is not in the rest of the array, since we have already passed our letter in alphabetical order!
It's no secret that there are better algorithms for searching inside sorted arrays. Using a simple algorithm, we can search for a specific element in a sorted array containing 1,000,000 elements using only 20 comparisons! The downside, of course, is that sorting an array with such a huge number of elements is relatively expensive, and it's definitely not done for the sake of a single search query.
In some cases, sorting an array makes searching unnecessary. For example, we are looking for a student's best score on a test. If the array is not sorted, then we will have to look through each element of the array to find the highest score. If the array is sorted, then the highest score will be either in the first position or in the last (depending on how the array is sorted: ascending or descending order), so we don't need to search at all!
Sorting is typically done by repeatedly comparing pairs of array elements and replacing the values if they meet certain criteria. The order in which these elements are compared depends on which sorting algorithm is used. The criteria consist of how the array will be sorted (for example, ascending order or descending order).
To swap two elements we can use the function std::swap() from the C++ standard library, which is defined in algorithm. In C++11, std::swap() was moved to the utility header file:
#include
#include #include int main() int a = 3 ; int b = 5 ; std::cout<< "Before swap: a = " << a << ", b = " << b << "\n" ; std::swap(a, b); // swap the values of variables a and b std::cout<< "After swap: a = " << a << ", b = " << b << "\n" ; |
The result of running the program above:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
After performing the replacement operation, the values of the variables a and b are swapped.
Sorting arrays using selection method
There are many ways to sort arrays. Array sorting by selection is perhaps the easiest to understand, although it is also one of the slowest.
For sorting an array by selecting from smallest to largest element the following steps are performed:
Starting with the element at index 0, we look for the smallest value in the array.
The found value is swapped with the zero element.
We repeat steps No. 1 and No. 2 for the next index in the array.
In other words, we look for the smallest element in the array and move it to the first place. Then we look for the second smallest element and move it to the second place after the first smallest element. This process continues until the array runs out of unsorted elements.
Here is an example of how this algorithm works in an array with 5 elements:
{ 30, 50, 20, 10, 40 }
First we look for the smallest element, starting at index 0:
{ 30, 50, 20, 10 , 40 }
Then we swap the smallest element with the element at index 0:
{ 10 , 50, 20, 30 , 40 }
Now that the first element of the array is sorted, we ignore it. We are looking for the next smallest element, but starting from index 1:
{ 10 , 50, 20 , 30, 40 }
And swap it with the element at index 1:
{ 10 , 20 , 50 , 30, 40 }
Now we can ignore the first two elements. We look for the next smallest element, starting at index 2:
{ 10 , 20 , 50, 30 , 40 }
And swap it with the element at index 2:
{ 10 , 20 , 30 , 50 , 40 }
We look for the next smallest element, starting at index 3:
{ 10 , 20 , 30 , 50, 40 }
And swap it with the element at index 3:
{ 10 , 20 , 30 , 40 , 50 }
We look for the next smallest element, starting at index 4:
{ 10 , 20 , 30 , 40 , 50 }
And we swap it with the element at index 4 (self-replacement is performed, i.e. we do nothing):
{ 10 , 20 , 30 , 40 50 }
{ 10, 20, 30, 40, 50 }
Note that the last comparison will always be a single comparison (i.e. a self-replacement), which is an unnecessary operation, so in fact we can stop the sort before the last element of the array.
Sorting arrays using selection method in C++
Here's how this algorithm is implemented in C++:
#include
#include #include int main() const int length = 5 ; // Loop through each element of the array // (except the last one, it will already be sorted by the time we get to it) < length - 1 ; ++ startIndex ) // The smallestIndex variable stores the index of the smallest value we found in this iteration // Start with the smallest element in this iteration being the first element (index 0) int smallestIndex = startIndex ; // Then look for a smaller element in the rest of the array < length ; ++ currentIndex ) // If we find an element that is smaller than our smallest element, if (array [ currentIndex ]< array [ smallestIndex ] ) // then remember it smallestIndex = currentIndex ; // smallestIndex is now the smallest element // Swap our initial smallest number with the one we found std::swap(array[startIndex], array[smallestIndex]); // Now that the entire array is sorted, display it on the screen for (int index = 0 ; index< length ; ++ index ) std::cout<< array [ index ] << " " ; return 0 ; |
The most confusing part of this algorithm is inside another loop (called a nested loop). The outer loop (startIndex) iterates through the elements one by one (one by one). In each iteration of the outer loop, the inner loop (currentIndex) is used to find the smallest element among the elements that remain in the array (starting at startIndex + 1). smallestIndex keeps track of the index of the smallest element found by the inner loop. Then smallestIndex changes value from startIndex . Finally, the outer loop (startIndex) passes this element and the process repeats.
Clue: If you have trouble understanding how the program above works, try writing it down on a piece of paper. Write the starting (unsorted) elements of the array horizontally on a line at the top of the worksheet. Draw arrows indicating which elements are startIndex , currentIndex , and smallestIndex at the moment. Loop through the program manually and redraw the arrows as the indices change. After each iteration of the outer loop, draw a new line showing the current state of the array (the location of its elements).
Text sorting is performed using the same algorithm. Just change the array type from -a to and initialize it with the appropriate values.
std::sort()
Since sorting arrays is a very common operation, the C++ standard library provides a built-in sorting function − std::sort(). It is located in the algorithm header file and is called as follows:
#include
#include #include int main() const int length = 5 ; int array [length] = (30, 50, 20, 10, 40); std::sort(array, array + length) ; for (int i = 0 ; i< length ; ++ i ) std::cout<< array [ i ] << " " ; return 0 ; |
Test
Task No. 1
Write on a piece of paper how to sort the following array using the selection method (as we did above):
{30, 60, 20, 50, 40, 10}
Answer #1
30 60 20 50 40 10
10
60 20 50 40 30
10 20
60
50 40 30
10 20 30
50 40 60
10 20 30 40
50
60
10 20 30 40 50
60 (self-replacement)
10 20 30 40 50 60
(self-replacement)
Task No. 2
Rewrite the program code from the subtitle “Sorting Arrays by Selection in C++” so that the sorting is done in descending order (largest to smallest number). Although this may seem complicated at first glance, it is actually very simple.
Answer #2
Just change:
If (array< array)
if (array [ currentIndex ]< array [ smallestIndex ] ) |
If (array > array)
if (array [ currentIndex ] > array [ smallestIndex ] ) |
Also smallestIndex should be renamed to largestIndex:
#include
#include #include int main() const int length = 5 ; int array [length] = (30, 50, 20, 10, 40); // Loop through every element of the array except the last one for (int startIndex = 0 ; startIndex< length - 1 ; ++ startIndex ) // largestIndex is the index of the largest element we have found so far int largestIndex = startIndex ; // Loop through each element of the array starting from startIndex + 1 for (int currentIndex = startIndex + 1 ; currentIndex< length ; ++ currentIndex ) // If the current element is greater than our largest element, if (array [ currentIndex ] > array [ largestIndex ] ) // then this is the new largest element in this iteration largestIndex = currentIndex ; // Swap our starting number with the largest element found std::swap (array [ startIndex ] , array [ largestIndex ] ) ; // Display the sorted array on the screen for (int index = 0 ; index< length ; ++ index ) std::cout<< array [ index ] << " " ; return 0 ; |
Task No. 3
This task is a little more difficult.
Another simple method for sorting elements is "bubble sort"(or more "bubble sort"). The idea is to compare a pair of values that are nearby, and if the specified criteria are met, the values from this pair are swapped. And thus the elements “bubble” to the end of the array. Although there are several ways to optimize bubble sort, for this assignment we will stick with the unoptimized version since it is simpler.
For a non-optimized version of bubble sort, the following steps are performed to: sort an array from smallest to largest value:
The array element at index 0 is compared with the array element at index 1. If the element at index 0 is greater than the element at index 1, then the values are swapped.
We then move to the next pair of values: the element at index 1 and the element at index 2, and so on until we reach the end of the array.
We repeat step No. 1 and step No. 2 until the entire array is sorted.
Write a program that will sort the following array using bubble sort according to the rules above:
const int length(9); int array = ( 7, 5, 6, 4, 9, 8, 2, 1, 3 );
const int length(9); |
At the end of the program, print the sorted elements of the array.
Clue: If we can only sort one element in one iteration, then this means that we will need to repeat the loop as many times as there are numbers in our array (its length) in order to ensure that the entire array is sorted.
Answer #3
#include
#include #include int main() const int length(9); int array [length] = (7, 5, 6, 4, 9, 8, 2, 1, 3); for (int iteration = 0 ; iteration< length - 1 ; ++ iteration ) // Loop through each array element up to the last element (not inclusive) // Last element has no pair to compare for (int currentIndex = 0 ; currentIndex< length - 1 ; ++ currentIndex) { // If the current element is larger than the element after it, then swap them if(array[ currentIndex] > array[ currentIndex+ 1 ] ) std:: swap(array[ currentIndex] , array[ currentIndex+ 1 ] ) ; } } // Display the sorted array on the screen for(intindex= 0 ; index< length; ++ index) std:: cout<< array[ index] << " " ; return0 ; } |
Task No. 4
Implement the following two optimization solutions for the bubble sort algorithm you wrote in the previous assignment:
Notice that each time bubble sort is performed, the largest value in the array “bubbles” to the end. After the first iteration, the last element of the array is already sorted. After the second iteration, the penultimate element of the array is sorted, and so on. With each new iteration, we don't need to recheck elements that have already been sorted. Modify your loop so that you don't recheck elements that have already been sorted.
Lesson from the series: “Programming in Pascal”
The process of processing and searching for information when solving many problems is faster and more efficient if the data is arranged in a certain order. For example, various lists of students, students, employees - in alphabetical order, numerical data from highest to lowest (or vice versa), etc.
There are quite a few different methods array sorting, differing from each other in the degree of efficiency, which is understood as the number of comparisons and the number of exchanges made in the sorting process. Let's take a closer look at some of them.
Sort an array using simple selection method
At sorting an array The selection method uses a basic algorithm for searching for the maximum (minimum) element and its number.
Algorithm for sorting an array using the selection method:
- For the original array, select the maximum element.
- Swap it with the last element (the largest element will then remain in its place).
- Repeat pp. 1-2 with the remaining n-1 elements, that is, consider part of the array, starting from the first element to the penultimate one, find the maximum element in it and swap it with the penultimate (n-1)th element of the array, then with the remaining (n-2 )-two elements and so on until there remains one element already in its place.
Ordering the array will require (n-1) scans of the array. During the sorting process, the sorted part of the array will increase, and the unsorted part will, accordingly, decrease.
When sorting data, the contents of variables are exchanged. To exchange, you need to create a temporary variable that will store the contents of one of the variables. Otherwise, its contents will be lost.
Task 1. Sort an array of 10 elements in ascending order using simple brute force.
Let's write a procedure. The input parameter for it will be an array. It will also be the output parameter. Therefore, we describe it as a variable parameter (with the keyword var).
In the procedure, the outer loop on i determines the length of the considered part of the array. It will vary from n to 2.
The inner loop on j is used to find the maximum element and its number. It is reasonable to take the value of the last element of the considered part of the array as the initial value of the maximum.
Procedure code:
Program code of the main program:
| program primer_1; const n = 10; type myarray = array of integer; var a:myarray; Procedure sorting1(var a:myarray); (Linear sorting (selection sort)) ... begin (main) writeln("Enter source array:"); for i:=1 to n do read(a[i]); sorting1(a); writeln("Sorted array:"); for i:=1 to 10 do write(a[i]," "); writeln; end. |
The process of ordering elements in an array in ascending order using the selection method:
| Item number | 1 | 2 | 3 | 4 | 5 |
| Source array | 8 | 7 | 5 | 4 | 2 |
| First viewing | 2 | 7 | 5 | 4 | 8 |
| Second viewing | 2 | 4 | 5 | 7 | 8 |
| Third viewing | 2 | 4 | 5 | 7 | 8 |
| Fourth viewing | 2 | 4 | 5 | 7 | 8 |
When sorting an array in descending order, you need to move the minimum element. Why in the algorithm for finding the maximum element is it enough to change the “>” sign to the “” sign<«.
Sort an array using the simple exchange method (bubble method)
The most well-known sorting method is bubble sorting. Its popularity is explained by its catchy name and simple algorithm.
The method is based on the fact that during the execution of the algorithm, the “lighter” elements of the array gradually “float up”.
The peculiarity of this method is not the comparison of each element with all, but the comparison in pairs of neighboring elements. Several sequential scans of the array are performed from beginning to end. If adjacent elements are located “incorrectly”, then they are swapped.
Algorithm for sorting an array in ascending order using the simple exchange method:
- Let's start browsing with the first pair of elements (a and a). If the first element of this pair is greater than the second, then we swap them, otherwise we leave them unchanged. Then we take the second pair of elements (a and a), if the second is greater than the third, then we also change them, then we compare the third and fourth, and if the third is greater than the fourth, we change their places, etc. The last thing we compare is the (n-1)th and nth elements. During the first traversal of the array, all pairs of array elements a[i] and a will be looked at for i from 1 to (n-1). As a result, the maximum element of the array will be moved to the end of the array.
- Since the largest element is in its place, consider the part of the array without it, that is, from the first to the (n-1)th element. We repeat the previous steps for this part of the array, as a result of which the second largest element of the array will move to the last place of the considered one part of the array, that is, at the (n-1) place in the entire array.
- These actions continue until the number of elements in the current part of the array is reduced to two. In this case, you need to do a final comparison and order the last two elements.
It is easy to see that to transform an array consisting of n elements, it is necessary to scan it n–1 times, each time reducing the viewing range by one element.
Below is the text of the procedure for sorting an array in ascending order using the bubble method.
To order array elements in descending order of their values, when comparing array elements, replace the “>” sign with “<«.
The process of arranging elements in an array in ascending order using the exchange method:
| Item number | 1 | 2 | 3 | 4 | 5 |
| Source array | 8 | 7 | 5 | 4 | 2 |
| First viewing | 7 | 5 | 4 | 2 | 8 |
| Second viewing | 5 | 4 | 2 | 7 | 8 |
| Third viewing | 4 | 2 | 5 | 7 | 8 |
| Fourth viewing | 2 | 4 | 5 | 7 | 8 |
What is the idea behind selection sorts?
- In an unsorted subarray, a local maximum (minimum) is searched.
- The found maximum (minimum) changes places with the last (first) element in the subarray.
- If there are unsorted subarrays left in the array, see point 1.
However, now nonlinearity is in trend, therefore, without having written all the publications about insertion sorts, today I will start a parallel thread about selection sorts. Then I will do the same for other algorithmic classes: merge sorts, distribution sorts, etc. In general, this will allow you to write publications on one topic or another. With such thematic alternation it will be more fun.
Selection sort:: Selection sort
Simple and unpretentious - we go through the array in search of the maximum element. The found maximum is swapped with the last element. The unsorted part of the array has decreased by one element (does not include the last element where we moved the found maximum). We apply the same actions to this unsorted part - we find the maximum and put it in last place in the unsorted part of the array. And we continue this way until the unsorted part of the array is reduced to one element.
Def selection(data): for i, e in enumerate(data): mn = min(range(i, len(data)), key=data.__getitem__) data[i], data = data, e return data
Simple selection sort is a brute force double search. Can it be improved? Let's look at a few modifications.
Double selection sort: Double selection sort
A similar idea is used in , which is a variant of bubble sort. Walking through the unsorted part of the array, in addition to the maximum, we also find the minimum along the way. We put the minimum in first place, the maximum in last. Thus, the unsorted part is reduced by two elements at each iteration.
At first glance, it seems that this speeds up the algorithm by 2 times - after each pass, the unsorted subarray is reduced not on one side, but on both sides at once. But at the same time, the number of comparisons doubled, while the number of swaps remained unchanged. Double selection only slightly increases the speed of the algorithm, and in some languages it even works slower for some reason.
The difference between selection sort and insertion sort
It may seem that selection sort and sort are essentially the same thing, a general class of algorithms. Well, or insertion sort - a type of selection sort. Or selection sort - a special case of insertion sort. In both cases, we take turns extracting elements from the unsorted part of the array and redirecting them to the sorted area.The main difference: in insertion sort we extract from the unsorted part of the array any element and insert it into its place in the sorted part. In selection sort we purposefully look for maximum element (or minimal) with which we supplement the sorted part of the array. In insertions, we are looking for where to insert the next element, and in selection, we already know in advance which place we will put it, but at the same time we need to find an element that corresponds to this place.
This makes both classes of algorithms completely different from each other in their essence and the methods used.
Bingo sort:: Bingo sort
An interesting feature of selection sort is that the speed does not depend on the nature of the data being sorted.For example, if the array is almost sorted, then, as is known, insertion sort will process it much faster (even faster than quick sort). And a reverse-ordered array for insertion sort is a degenerate case; it will sort it for as long as possible.
And for selection sort, partial or reverse ordering of the array does not matter - it will process it at approximately the same speed as regular random. Also, for classical selection sort, it does not matter whether the array consists of unique or repeating elements - this has practically no effect on speed.
But in principle, you can get creative and modify the algorithm so that it works faster for some data sets. For example, bingo sort takes into account if the array consists of duplicate elements.
The trick here is that in the unordered part, not only the maximum element is remembered, but also the maximum for the next iteration is determined. This allows you, in case of repeating maxima, not to search for them again every time, but to put them in their place immediately as soon as this maximum is once again encountered in the array.
The algorithmic complexity remains the same. But if the array consists of repeating numbers, then bingo sorting will be tens of times faster than regular selection sort.
# Bingo sort def bingo(data): # First pass. max = len(data) - 1 nextValue = data for i in range(max - 1, -1, -1): if data[i] > nextValue: nextValue = data[i] while max and data == nextValue: max -= 1 # Subsequent passes. while max: value = nextValue nextValue = data for i in range(max - 1, -1, -1): if data[i] == value: data[i], data = data, data[i] max -= 1 elif data[i] > nextValue: nextValue = data[i] while max and data == nextValue: max -= 1 return data
Cycle sort:: Cycle sort
Cyclic sorting is interesting (and valuable from a practical point of view) because changes among the elements of an array occur if and only if the element is placed in its final place. This can be useful if rewriting an array is too expensive and to be careful with physical memory, you need to minimize the number of changes to array elements.
It works like this. Let's go through the array and call X the next cell in this outer loop. And we look at what place in the array we need to insert the next element from this cell. At the place where you need to paste there is some other element, we send it to the clipboard. For this element in the buffer, we also look for its place in the array (and insert it into this place, and send the element that ends up in this place to the buffer). And for the new number in the buffer we perform the same actions. How long should this process continue? Until the next element in the clipboard turns out to be the element that needs to be inserted into cell X (the current location in the array in the main loop of the algorithm). Sooner or later this moment will happen and then in the outer loop you can move to the next cell and repeat the same procedure for it.
In other selection sorts, we look for the maximum/minimum to put them in last/first place. In cycle sort, it turns out that the minimum in the first place in the subarray is itself, as it were, in the process of several other elements being placed in their rightful places somewhere in the middle of the array.
And here the algorithmic complexity also remains within O( n 2). In practice, cyclic sorting is even several times slower than regular selection sort, since you have to run through the array more and compare more often. This is the price for the minimum possible number of rewrites.
# Cyclic sorting def cycle(data): # We go through the array in search of cyclic cycles for cycleStart in range(0, len(data) - 1): value = data # We look for where to insert the element pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i]< value: pos += 1 # Если элемент уже стоит на месте, то сразу # переходим к следующей итерации цикла if pos == cycleStart: continue # В противном случае, помещаем элемент на своё # место или сразу после всех его дубликатов while value == data: pos += 1 data, value = value, data # Циклический круговорот продолжается до тех пор, # пока на текущей позиции не окажется её элемент while pos != cycleStart: # Ищем, куда переместить элемент pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 # Помещаем элемент на своё место # или сразу после его дубликатов while value == data: pos += 1 data, value = value, data return data
Pancake sorting
An algorithm that has been mastered by all levels of life - from to.
In the simplest version, we look for the maximum element in the unsorted part of the array. When the maximum is found, we make two sharp turns. First, we flip the chain of elements so that the maximum is at the opposite end. Then we flip the entire unsorted subarray, resulting in the maximum falling into place.
Such cordballets, generally speaking, lead to an algorithmic complexity of O( n 3). These are trained ciliates that tumble in one fell swoop (therefore, their performance has a complexity of O( n 2)), and when programming, reversing part of an array is an additional loop.
Pancake sorting is very interesting from a mathematical point of view (the best minds have thought about estimating the minimum number of turns sufficient for sorting); there are more complex formulations of the problem (with the so-called burnt side). The topic of pancakes is extremely interesting, perhaps I will write a more detailed monograph on these issues.
# Pancake sort def pancake(data): if len(data) > 1: for size in range(len(data), 1, -1): # Position of the maximum in the unsorted part maxindex = max(range(size), key = data.__getitem__) if maxindex + 1 != size: # If the maximum is not words, then you need to reverse it if maxindex != 0: # Flip it so # that the maximum is on the left data[:maxindex+1] = reversed(data[:maxindex +1]) # Reverse the unsorted part of the array, # the maximum falls into place data[:size] = reversed(data[:size]) return data
Selection sort is only as effective as the search for the minimum/maximum element in the unsorted part of the array. In all algorithms analyzed today, the search is carried out in the form of double search. And double search, no matter how you look at it, will always have an algorithmic complexity no better than O( n 2). Does this mean that all selection sorts are doomed to mean square complexity? Not at all, if the search process is organized fundamentally differently. For example, consider a data set as a heap and search within the heap. However, the topic of heaps is not even an article, but a whole saga; we will definitely talk about heaps, but another time.
All methods described below should be considered as special variants of the method known as direct selection method or sort by selection. What these methods have in common is finding (selecting) the maximum or minimum elements of an array and placing them in successive cells of the array.
Method for finding the minimum element
The essence of this method (bearing in mind the selected restrictions for the numerical example we are considering) is as follows.
At the first step, the minimum number among all the numbers in the array and its index, stored in another variable, for example, Imin, is found and stored in a variable, for example, Xmin, and then places in the array of the found minimum number are exchanged with the first element of the array: X:=X ; X:=Xmin;.
In our example, the minimum number Xmin=15 is in cell Imin=3, and rearranging the first and minimum numbers will lead to the following result
For i=3 we get Xmin=21 and Imin=4, and after rearrangement
For i=5 we get Xmin=34 and Imin=5, and after rearrangement
Thus, the outer loop should be executed n-1 times, and the number of executions of the inner loop will decrease from n-1 to 1. To sort the array in descending order, the first minimum number found should be swapped with the last one, the second one with the penultimate one, and so on.
Maximum element search method
This method differs from the previous one only in that the maximum elements are found. With the same organization of loops when implementing these methods, they will give exactly opposite results: if one leads to an increase in the numbers in the array, then the other leads to a decrease, and vice versa.
Index Search Method minimum element
This method differs from the method of searching for the minimum element and its index in that the inner loop is used to search only for the index of the minimum element, so permutations of numbers in the array at each step i, i=1, 2, ...,n-1 will have to be performed using additional variable, for example, R: R:=X[i]; X[i]:=X; X:=R;.
Maximum element index search method
This method differs from the previous one only in that the index of the maximum element is found. With the same organization of loops when implementing these methods, they will give exactly opposite results: if one leads to an increase in the numbers in the array, then the other leads to a decrease, and vice versa.
