2.1.1. Sort

C++ Standard Library, often used via the <algorithm> header, provides several built-in functions to handle sorting operations efficiently. Here are the primary sorting algorithms available:

• std::sort: This is the most commonly used sorting function. It sorts the elements in a range into ascending order by default, but you can specify a custom comparison function if you want to sort by other criteria. It typically implements a variation of quicksort, introsort (a hybrid of quicksort, heapsort, and insertion sort), or another efficient sorting algorithm, and has a time complexity of O(n log n) on average.

• std::stable_sort: Similar to std::sort, but it maintains the relative order of equivalent elements, ensuring stability in sorting. It typically uses a merge sort algorithm, which is stable but may require additional memory compared to std::sort. Like std::sort, it has a time complexity of O(n log n), but because it’s stable, it might use more memory.

• std::partial_sort: This function sorts the first ‘n’ elements in a range, leaving the rest of the range in an unspecified state. It’s useful when you only need the smallest or largest subset of a range. It generally employs a partial quicksort or heap sort algorithm and has a complexity of O(n log k) where ‘k’ is the number of sorted elements requested.

• std::nth_element: This is more of a partitioning algorithm than a full sorting algorithm. It rearranges the range so that the element at the ‘nth’ position is the element that would be in that position in a sorted sequence, with all smaller elements moved before it and all larger elements moved after it. Its average time complexity is O(n), which is faster than sorting the entire range if you only need to find a few specific elements.

These functions cover most sorting needs with various trade-offs in terms of speed, memory usage, and stability. They are highly optimized and should be preferred over manually implemented sorting algorithms for most practical purposes in C++. In addition to the builtin sorting functions, the followings are some examples of customized sorting.

2.1.1.1. Sorting in linear time and constant space

Counting and radix sort have linear time and space complexity. There are some other in-place algorithms with linear complexity and constant space complexity. Restoring a once-ordered vector, where 1 to N are stored inside and N equals to vector length, is one of them.

#include <gtest/gtest.h>
#include <sein.hpp>

namespace ns_sort_1_n{
// TC: O(N), SC: O(1)
vector<int> _sort(vector<int> nums){
  for(int i=0;i<nums.size();i++)
    while(nums[i] != nums[nums[i]-1])
      swap(nums[i], nums[nums[i]-1]);
  return nums;
}
}
using namespace ns_sort_1_n;
TEST(_sort_1_n, a) {
  VI expected={1,2,3,4,5};
  EXPECT_EQ(_sort({5,2,1,3,4}), expected);
}

Another one is Dutch national flag sort [1] and there are even more out there.

Footnotes

[1]

The Dutch national flag problem is a computational problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order..

2.1.1.2. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

---

We can sort and swap(n[i], n[i+1]), but that is suboptimal.

Code Block 2.1.1 wiggle sort

struct wiggle_sort {
  void run(vector<int>& n) {
    for (int i = 1; i < n.size(); ++i)
      if (i % 2 == 1) {
        if (n[i] < n[i - 1]) swap(n[i], n[i - 1]);
      } else if (i % 2 == 0) {
        if (n[i] > n[i - 1]) swap(n[i], n[i - 1]);
      }
  }
};

2.1.1.3. Strict Wiggle Sort

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:

(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note: You may assume all input has valid answer.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

This problem gives us an unordered array, lets us sort into a wobble array such that nums[0] < nums[1] > nums[2] < nums[3]… and gives us an example. We can sort the array first and then make adjustments. The adjustment method is to find the number in the middle of the array, which is equivalent to dividing the ordered array into two parts from the middle, then take one from the end of the first half, and go to one from the end of the second half, which ensures that the first number is less than the first number. Two numbers, then take the second-to-last number from the first half, and the second-to-last number from the second half, which ensures that the second number is greater than the third number, and the third number is less than the fourth number, so And so on until all are taken

Code Block 2.1.2 strict wiggle sort(suboptimal)

struct wiggle_sort_v2_suboptimal {
  void run(vector<int>& nums) {
    vector<int> tmp = nums;
    int n = nums.size(), k = (n + 1) / 2, j = n;
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < n; ++i) {
      nums[i] = i & 1 ? tmp[--j] : tmp[--k];
    }
  }
};

Code Block 2.1.3 strict wiggle sort(optimal)

struct wiggle_sort_v2 {
#define A(i) nums[(1 + 2 * i) % (n | 1)]
  void run(vector<int>& nums) {
    int n = nums.size(), i = 0, j = 0, k = n - 1;
    nth_element(nums.begin(), nums.begin() + n / 2, nums.end());
    int mid = *(nums.begin() + n / 2);
    while (j <= k) {
      if (A(j) > mid)
        swap(A(i++), A(j++));
      else if (A(j) < mid)
        swap(A(j), A(k--));
      else
        ++j;
    }
  }
};