Easily master the basic programming algorithms (Part 3)

[[121972]]

Basic Programming Algorithms (I)

Basic Programming Algorithms (II)

Basic Programming Algorithms (III)

Selection Sort

Conditions of use: Collections of comparable sizes.

Algorithm idea: Each time, select the smallest (or largest) element from the data elements to be sorted, and put it at the end of the sorted sequence until all the data elements to be sorted are sorted.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17}

 //Simple selection sort  
 void SimpleSelect( int b[10])
 {
 int temp;
 int i;
 for (i=0;i<9;i++)
 {
 for ( int j=i+1;j<9;j++)
 {
 if (b[i]>b[j])
 {
 temp=b[i];
 b[i]=b[j];
 b[j]=temp;
 }
 }
 }
 cout<< "the sort is:" ;
 for ( int i=0;i<10;i++)
 {
 cout<<b[i]<< " " ;
 }
 cout<<endl;
 }

Performance analysis: time complexity is O(n^2)

Heap Sort

Conditions of use: Collections of comparable sizes.

Algorithm idea: In fact, heap sort is an evolution of simple selection sort. It mainly reduces the number of comparisons. What is a heap? If the sequence is regarded as a complete binary tree, the values ​​of all non-terminal nodes in the complete binary tree are not greater than (or not less than) the values ​​of its left and right child nodes, which can be called a heap. From the properties of the heap, we can know that the top of the heap is a maximum keyword (or minimum keyword). After outputting the top of the heap, the remaining elements are built into a heap again, and then the top is output. Repeated execution in this way can get an ordered sequence, and this process is the achievement of heap sort.

Heap sorting is mainly divided into two steps:

(1) Build a heap from an unordered sequence.

(2) Output the top element and form a new heap.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17}

 //Heap sort  
 void HeapSort( int b[10])
 {
 void HeapAdjuest( int b[10], int min, int max);
 void Sawp( int *a, int *b);
 int i;
 //Because the binary tree is completed, the heap conversion starts from the last non-leaf node  
 for (i=9/2;i>=0;i--)
 {
 HeapAdjuest(b,i,9);
 }
 //Take out the top data of the heap and sort it again  
 for (i=9;i>0;i--)
 {
 Sawp(&b[i],&b[0]);
 HeapAdjuest(b,0,i-1);
 }
 } 
 
 //Heap adjustment (large top heap)  
 //min data needs to adjust the starting position in the array  
 //max data needs to adjust the end position in the data  
 void HeapAdjuest( int b[10], int min, int max)
 {
 if (max<=min) return ;
 int temp;
 temp=b[min];
 int j; 
     
 // Extend its child node loop  
 for (j=2*min;j<=max;j*=2)
 {
 //Select its older child  
 if (j<max&&b[j]<b[j+1])
 {
 j++;
 } 
         
 //Children whose top is larger than the top of the heap will not be processed  
 if (temp>b[j])
 {
 break ;
 } 
         
 //Replace the larger number with the smaller one  
 b[min]=b[j];
 min=j;
 }
 b[min]=temp;
 } 
 
 //Swap function  
 void Sawp( int *a, int *b)
 {
 int temp;
 temp=*a;
 *a=*b;
 *b=temp;
 }

Performance analysis: Time complexity Time complexity O(nlogn)

Merge Algorithm

Also known as 2-way merge algorithm

Conditions of use: Collections of comparable sizes.

Algorithm idea: Assuming that the initial sequence contains n records, it can be regarded as n ordered subsequences, each subsequence has a length of 1, and then merged two by two to obtain [n/2] subsequences with a length of 2 or 1 (the length is 1 here, maybe the sequence length is an odd number, then the last sequence is left alone, so the length is 1); then merge two by two, and repeat this process until an ordered sequence of length n is obtained.

Example programming: int b[10]={77,1,65,13,81,93,10,5,23,17}

 //Merge sort  
 void MergeSort( int b[10], int d[10], int min, int max)
 {
 //Use and store the sequence obtained from the middle area  
 int c[10];
 void Merge( int c[10], int d[10], int min, int mid, int max);
 if (min==max)d[min]=b[min];
 else  
 {
 // Divide into two areas  
 int mid=(min+max)/2;
 //Merge and sort this area  
        MergeSort(b,c,min,mid);
 //Merge and sort this area  
        MergeSort(b,c,mid+1,max);
 //Merge the two regions  
        Merge(c,d,min,mid,max);
 }
 } 
 
 //Merge the ordered sequences d[min-mid] and d[mid+1-max] into the ordered sequence c[min-max]  
 void Merge( int c[10], int d[10], int min, int mid, int max)
 {
 int i,j,k;
 for (i=j=min,k=mid+1;j<=mid&&k<=max;i++)
 {
 if (c[j]>c[k])
 {
 d[i]=c[k];
 k++;
 }
 else  
 {
 d[i]=c[j];
 j++;
 }
 }
 if (j<=mid)
 {
 for (;j<=mid;j++,i++)
 {
 d[i]=c[j];
 }
 }
 if (k<=max)
 {
 for (;k<=max;k++,i++)
 {
 d[i]=c[k];
 }
 }
 }

Performance analysis: time complexity O(nlogn)

Summarize

So with so many sorting algorithms, when should we use which algorithm?

Because different sorting methods are suitable for different applications and requirements, choose the appropriate sorting method considering the following factors:

• The number of records to be sorted n

• Requirements for its stability

• Storage Structure

• Time and auxiliary space complexity

(1) If n is relatively small (for example, n <= 50), direct insertion sort or simple selection sort can be used.

(2) If the initial state of the sequence is basically ordered, you can choose direct insertion sort or bubble sort.

(3) If n is relatively large, an algorithm with a time complexity of O(nlogn) can be used: quick sort, heap sort, merge sort.

Quick sort is considered to be the best method for internal sorting based on comparison. When the sorted keywords are randomly distributed, quick sort has the shortest average time. Unstable

Heap sort requires less auxiliary space than quick sort, and will not encounter the worst case scenario that quick sort may encounter. But it is still relatively unstable

Merge sort is relatively stable, but it is generally not recommended to use. It has poor practicality and may occupy a large amount of auxiliary space.