Recently, I have been learning algorithm and data structure. Algorithm is the basic skill of a programmer, but I am not a major student, so I lack knowledge in this aspect. I found a set of corresponding courses on THE MOOC website, the main teacher is Liuyubobobo, from my learning experience and feelings, Bobo explained a very clear and thorough question, putonghua is good, suitable for beginners to understand and learn. I recommend this tutorial if you want to learn about algorithms and data structures. Address: coding.imooc.com/class/71.ht… This series of articles mainly presents the content of this course in the form of text. To do this, I want to deepen my understanding of the knowledge points on the video through the process of forming words. Second, I want to strengthen my ability to express myself.
This article mainly explains three basic sorting algorithms, selection sort, insertion sort, and bubble sort, its time complexity is 0(n^2) level, the implementation of the code using c++ language.
Selection sort
First given an array of unordered integers:
Select the basic idea of sorting
Start with index = 0, iterate through the array, get the smallest element index = 4, element value 1, and then swap index = 0 with the two elements index = 4, element value 1 at index = 0. The element at index = 4 has a value of 5. Red is the ordered region that has been sorted.
Once the smallest element is found and placed at the top of the array, the array is then iterated from index = 1. Find the second smallest element and swap it with index = 1. At this point, the value of the element at index = 1 is 2, and the value of the element at index = 2 is 4.
The third smallest element is then swapped with the element at index = 2. After the swap, the element at index = 2 is 3 and the element at index = 5 is 4.
It then iterates through until the largest element is in the last position of the array. The whole idea of selective sorting is easy to understand: loop through the array to find the smallest element in the loop, and then swap places with the next element on the sorted index.
Code implementation
I’ll write it as a function that passes in an array and the number of elements:
template <typename T>
void selectionSort(T arr[],int n){
for(int i = 0; i < n; i++) { int minIndex = i; // minIndex Holds the index of the smallest value in the inner loopfor (int j = i + 1; j < n; j++) {
if(arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr[i], arr[minIndex]); }}Copy the codeInsertion sort
Insert the basic idea of sort
Bobo teacher make such an example, I think to understand insertion sort is appropriate: like a deck of CARDS, three people to fight the landlord with this deck of CARDS, card stages, you need to you in my hands touch the card in the right position, the CARDS in the hand is good, is orderly, in the later, make its overall still orderly. So let’s simulate that. First of all, there is a card in the fixed hand, marked in red as the sorted card in the hand.
And then the second card, 4, is smaller than 5, so it’s in front of 5, 4 and 5 switch places.
And then the third card is 2,2 is less than 5, so you put it in front of the 5 and behind the 4.
Now, this is not the right place for 2, so I’m going to keep comparing it to the previous element, so 2 is less than 4, so I’m going to put it in front of 4. Now it’s ordered.
Then touch the fourth card, 7,7 is less than 5, found that you don’t have to switch places, just put it in place.
In this way, the cards are compared with the arranged cards in turn, so that they are placed in the appropriate position, until the last card is touched.
Code implementation
template <typename T>
void insertionSort(T arr[],int n){
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (arr[j-1] > arr[j]) {
swap(arr[j - 1],arr[j]);
} else {
break; }}}}Copy the codeNote: in the first layer for loop I = 1, I does not start from zero. Because the first card doesn’t have to be sorted, we start with the second card. So I = 1.
The second layer of the for loop starts with the index I of the element to be sorted. In the sorted interval [0, I), the loop iterates backwards. If the preceding element is found to be larger than it, the two elements swap places. When the previous element is smaller than it is, it finds its proper position, so it doesn’t need to iterate again and ends the loop.
Insertion sort optimization
Swap (arr[j-1],arr[j]); swap(arr[j-1],arr[j]);
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
Copy the codeIf a smaller element is to be inserted in place, it must be swapped many times along the way. This virtually increases the sorting time. Optimization idea is only for assignment operation for exchange of operation, to save a copy of the first sort elements, then traverse elements that have been sequenced, and from the front after compare one by one, if when traversing to the index = j elements, elements of the index than j j – 1 position of the element, element of j – 1 the index position in the future, Moving back and j index position of the element is assigned a value of j – 1 the index position of the element, when the traverse to the elements of the j – 1 the index is smaller than j location on the element or equivalent, is the last move loop back and the position of the free to the right place for sorting, assignment of the values in the position to be sort of value.
Suppose we now sort 1 in an optimized way, with red as the sorted part.
Let’s start by making a copy of the element 1 to be sorted
The element to be sorted is then compared to the sorted element at index = 3 with the value of 7. If the element is larger than the element to be sorted, the value to be sorted is copied directly to the element. 7 is bigger than 1, so 7 moves back, so the value of the element to be sorted is 7, and index = 3 is freed up.
It then compares the sorted elements in sequence. This time, we compare 5 with 1 when index = 2, 5 is larger than 1, 5 is moved back, and we assign 5 to the element at index = 3, so index = 2 is freed up.
If we compare 4 at index = 1 with element 1, 4 is still larger than 1. If we move 4 back and assign 4 to index = 2, then index = 1 will be available.
To continue. If I compare 2 at index = 0 to 1, 2 is still bigger than 1, so I move 2 back, and I assign 2 at index = 1 to make room for index = 0.
There are no more elements to compare before the element. So I’m going to put the element to be sorted at index = 0.
After some twists and turns, element 1 finally finds its proper place. Element 1 is sorted
And then the element at index = 5, the element at index = 6, and then the element at index = 7. Put all the elements in their proper place as described above.
Code implementation
template <typename T>
void insertionSort(T arr[],int n){
for(int i = 1; i < n; i++) { T e = arr[i]; // insert element e int j = I; // j holds the position where element e should be insertedfor (j = i; j > 0; j--) {
if(arr[j-1] > e) { arr[j] = arr[j-1]; } } arr[j] = e; }}Copy the codeBubble sort
Bubble sort implementation idea
So we’re going to start with an unordered array of eight numbers
The core idea of bubble sort is to compare two adjacent elements in pairs and swap their positions according to their size
First of all, compared with 4, 5 is bigger than 4. Our requirement is to reach the permutation from small to small. 4 needs to be in front of 5, so 4 and 5 switch positions.
And then you start comparing 5 to 2, 5 is bigger than 2, switch places
So let’s go ahead and compare 5 to 7, 5 is smaller than 7, and it stays the same
Go on, compare 7 with 1, 7 is greater than 1, switch places
Don’t stop. Seven is bigger than three. Switch places
So if you go further, 7 compared to 8, 7 is less than 8, so it stays the same
And then there’s the last one, 8 is 6, 8 is bigger than 6, switch places
In this round, element 8 is placed to the far right, where red represents the sorted region of ️
Then, repeat the above method and start the next element in pairs. If the first element is larger than the last one, the position is changed. If the second element is smaller, the position is not changed. Find the second largest element and put it to the left of element 8.
And then the
And then the
Given a set of integer array disorder, according to the sort of thinking, the blue areas belong to the area of disorder, also need to compare, but in the picture above the blue part is orderly, it can be used as an optimized aspect, is when the first row of the elements in the area is orderly, sequenced, the end of the sorting, This part of the optimization is not covered in the following code.
The implementation code
template <typename T>
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if(arr[j] > arr[j+1]) { swap(arr[j],arr[j+1]); }}}}Copy the codeThe code is easy to understand, a double-layer loop, each time the outer layer determines a maximum and puts it on the right side of the array, the inner layer looks for that maximum. Elements are compared first, then swapped.
Optimization of bubble sort
Just now, in the stepwise comparison, it appears that the elements in the blue unordered region are already ordered.
But the bubble sort code above will continue to be compared. Each element participates in the outer loop until the end of the loop. So the optimization direction is to end the loop when the elements in the unordered region are already ordered. The optimized code is partially explained in the comments.
void BubbleSort(T arr[],int n){
for (int i = 0; i < n; i++) {
bool isSorted = true; // Use a bool to indicate whether each layer is ordered. The default value is true.for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j],arr[j+1]);
isSorted = false; // If there is a swap element, then it is not ordered, the bool value is false.}}if(isSorted) {// in the inner layer, if the bool has not been changedfalse, then it indicates that there is no element exchange in the inner layer, then the sequence is completed, and the loop is directly ended.break; }}}Copy the codeThis optimization is basically marked with a bool to determine order. If there is no exchange of elements in the inner loop, then the sequence must be ordered, and there is no need for the outer loop.
Next time: Merge sort