Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Selection sort

Algorithm analysis

The selection of the selection sort is actually the smallest or largest selection of the sequence at a time, put it first. One way to think about it is, if we are stacking wood, each time we find the largest block to put underneath, and the next time we find the largest block that is left. So we can understand selection sorting.

photo

Code implementation

Void select_sort(int arr[], int len){int I =0,j=0; for(i=0; i<len-1; i++){ int min=i; for(j=i+1; j<len; j++){ if(arr[j]<arr[min]) min=j; } int temp=arr[min]; arr[min]=arr[i]; arr[i]=temp; }}Copy the code

Insertion sort

Algorithm analysis

Insertion sort is the way we sort cards when we play cards. We took a hand, left to right, in disordered order. We look at the first card, it’s a jack, we look at the second card, it’s a ten, we put ten in front of the jack, and on the third card we have a three, we put three in front of the jack and ten. The next card is a wang and we’re just going to leave it there for the moment.

photo

Void insert_sort(int arr[], int len){int I,j; for(i=1; i<len; i++){ int key=arr[i+1]; j=i-1; while(arr[j]>key&&j>=0){ arr[j+1]=arr[j]; j--; } arr[j+1]=key; }}Copy the code

The characteristics and comparison of the two

Selection sort traverses the array for each digit location, whereas insertion sort looks forward for each digit without traversing the entire array. So how do we choose between these two sorting algorithms? If the files we need to sort are very large and stored on a hard disk, then using selective sort means that each sort will have to read all the files on disk, which is very time consuming. So insertion sort is more appropriate at this point.