C++ selection sorting algorithm example details

In this paper, the example of C++ selection sorting algorithm for you to share the specific code, for your reference, the specific content is as follows

The basic idea

Select the smallest element from the unordered area every 1 time, and place the order at the end of the ordered area until all the elements are sorted.
Since the selection sort always selects the globally smallest (or largest) element from the unordered region every time, it is suitable to select a partial sorting element from a large number of element speeds. For example, select the smallest of the top 10 elements from 10,000.

Direct selection sort

1. Sorting ideas

Starting with the i pass, the smallest element arr[k] is selected from the current disordered region arr[i... n-1] and swapped with the last element of the ordered region, the first element of the disordered region. After each sequence, 1 element is added to the ordered region, and 1 element is reduced from the disordered region. Moreover, all elements in the ordered region are less than or equal to the elements in the disordered region. After the sequence of n-1, only one element, arr[n-1], is left in the unordered region, which must be the maximum value of the whole sequence, so there is no need to arrange it again.

2. Sorting algorithm

void SelectSort(int *arr, int size)
{
 if (arr == NULL)
  return;

 //1. Find the smallest element in the unordered region and its subscript 
 int i, j;
 for (i = 0; i < size - 1; i++)
 {
  int k = i;
  for (j = i + 1; j < size; j++)
  {
   if (arr[j] < arr[k])
   {
    k = j;
   }

  }
  //2. The smallest element is separated from the disorder 1 Individual element exchange 
  //swap(arr[i], arr[k]);
  if (k != i)
  {
   int tmp = arr[i];
   arr[i] = arr[k];
   arr[k] = tmp;
  }
 }
}

3. Algorithm analysis

Since the minimum value is to be selected, every element in the unordered area will participate in the comparison. Therefore, no matter what the state of the initial data sequence is, the total comparison times are:

C = n n - 1 + 2 + 3 + n... + 2 + 1 = n (n - 1) / 2

Therefore, the time complexity of direct selection sort is O(N^2), and the space complexity is O(1). Direct selection sort is an unstable algorithm. For example, the sorting sequence is {5, 3, 2, 5, 4, 1}. After the first sorting, {1, 3, 4, 5, 4, 5} is obtained. The relative positions of the two 5s have changed.

4. Optimized version

Find out the maximum and minimum values at the same time for each sorting, put the minimum value on the left side of the sequence and the maximum value on the right side of the sequence, and then narrow down the left and right sorting range at the same time.

// Optimization, find out the maximum and minimum values for each sorting 
void SelectSort1(int *arr, int size)
{
 if (arr == NULL)
  return;

 int left = 0;
 int right = size - 1;
 while (left < right)
 {
  for (int i = left; i < right; i++)
  {
   if (arr[i] < arr[left])
    swap(arr[i], arr[left]);
   if (arr[i] > arr[right])
    swap(arr[i], arr[right]);
  }
  left++;
  right--;
 }
}

Heap sort

1. Sorting ideas

Heap sort is a tree selection sort method. In the sorting process, arr[0... n-1] is regarded as the sequential storage structure of a complete two-fork tree, and the largest (or smallest) element is selected in the current disordered area by taking advantage of the internal relationship between parent nodes and child nodes in the complete two-fork tree.
The subscript starts at 0 and the two child nodes of node i can be represented as 2*i+1 and 2*i+2.

2. Sorting algorithm

void AdjustDown(int *arr, int size, int parent)
{
 int child = 2 * parent + 1;

 while (child < size)
 {
  if (child + 1 < size && arr[child] < arr[child + 1])
  {
   child++;
  }

  if (arr[parent] < arr[child])
  {
   swap(arr[parent], arr[child]);
   parent = child;
   child = 2 * parent + 1;
  }
  else
   break;
 }
}

void HeapSort(int *arr, int size)
{
 if (arr == NULL)
  return;

 //1. Build the initial heap (in this case, a large heap) 
 int root;
 for (root = (size / 2)-1; root >= 0; root--)
 {
  AdjustDown(arr, size, root);
 }

 //2. will arr[0] with arr[n-1] Swap and adjust arr[0...n-1] , so that it satisfies the heap, and so on and so on 
 for (root = size-1; root >= 1; root--)
 {
  swap(arr[root], arr[0]);
  AdjustDown(arr, root, 0);
 }
}

3. Algorithm analysis

The time of heapsort is mainly composed of the time of building the heap and repeatedly adjusting the heap. Since the heap can be regarded as a complete two-fork tree structure, the time complexity of heapsort is O(N*lgN) and the space complexity is O(1), and the heapsort algorithm is unstable.