This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Selection sort

Simple selection sort

The basic idea

  • Each run selects the object with the smallest key in the following N-i +1 as the ith record of the ordered sequence

Algorithm implementation

void SelectSort(SqList &L){
	// Make a simple selection sort of the record sequence R[1.. L. long]
	for(i = 1; i <= L.length; i++){
		// Select the ith smallest record and exchange in place
		k = i;
		for(j = i + 1; j <= L.length; ++j)
			if(L.r[j].key < L.r[k].key) k = j;
		if(k ! = i)Swap(L.r[i], L.r[k]);  / / exchange}}Copy the code

Algorithm analysis

  • Time complexity:O(n^2)
    • Number of moves:
      • Best case: 0
      • Worst case: 3 times n minus 1.
  • Space complexity: O(1)
  • Stability: stability

Tree selection sort

The basic idea

  • The key codes of n objects are obtained and compared in pairs to get the winner of n/2 comparisons (the one with the smaller key code), which is retained as the result of the first step comparison.
  • The n/2 objects are then compared to the key pairwise… And so on until an object with the smallest key is selected.

Algorithm analysis

  • If the depth of a complete binary tree with n leaves is log2n +1, then log2n comparisons are required for each trip of sorting, and the sorting time complexity is O(nlog2n).
  • Requires more secondary storage space (n-1), superfluous comparison with the maximum, etc.

Improvement: Simple selection sort does not take advantage of the results of the last selection, which is an important reason for the full speed. If this can be improved, it will increase the speed of sorting.

Heap sort

  • Heap: Store the data elements to be sorted in an array R [1… n]. Think of R as a full binary tree, with each node representing a record. The left child of the node r[I] is r[2i], and the right child is r[2i+1].
  • If r[I].key<=r[2i].key and r[I].key<=r[2i+1].key, the complete binary tree is called a heap. (Small root heap)
  • If r[I].key>=r[2i].key and r[I].key>=r[2i+1].key, the complete binary tree is called a heap. (large root heap)

The basic idea

  • Builds an unordered sequence into a heap
  • The minimum (large) value of the output heap top
  • If the remaining n-1 elements are adjusted into a heap, the sub-minimum value of n elements can be obtained
  • Repeat to get an ordered sequence

An unordered sequence builds the heap

How do I output the top element of the heapAdjust theTo make it a new pile?

  • Output the top element of the heap and replace it with the last element in the heap
  • Compare the root node with the left and right sub-root nodes and exchange with the smaller one
  • Repeat until you get to the leaf and get a new heap

Algorithm implementation

void HeapAdjust(HeapType &H, int s, int m){
	// All keywords recorded in known H.r [s..m] except H.r [s]
    // To satisfy the characteristics of the heap, this function adjusts H.r [s] from top to bottom
    // The keyword to make H.r [s..m] also become a big top heap.
    rc = H.r[s];  // hold H.r [s]
    for(j = 2 * s; j <= m; j *= 2) {// the initial value of j refers to the left child
    	// A top-down selection process;
    	if(j < m && H.r[j].key < H.r[j + 1].key) ++j;
    	// Compare the left and right subroots first
        // Let j indicate the location of the record with a large keyword
        if ( rc.key >= H.r[j].key )  break; 
        // Compare "root" with "sub-root".
        // If ">=" is true, the insert of RC has been found
        // Enter position s, no further adjustment is needed
        H.r[s] = H.r[j];   s = j;    
        // If the record is moved up, you need to continue adjusting down

    }
    H.r[s] = rc;  // Insert the previous heap top record into position s
}

void HeapSort ( HeapType &H ) {
	// Heap sort the order table H
	for(i = H.length / 2; i > 0; --i)
		HeapAdjust(H, i, H.length);  // Build a big top pile
	for(i = H.length; i > 1; --i){
		Swap(H.r[1], H.r[i])           
		// Record the top of the heap and the current unsorted subsequence
		// The last record in H.r[1.. I] is exchanged
		HeapAdjust(H, 1, i- 1);  // Reset H.r[1...i-1] to a large top heap}}Copy the code

Algorithm analysis

  • Time efficiency: O(nlog2n)
  • Space efficiency: O (1)
  • Stability: instability

If n is large