Sorting

Sorting means arranging elements in a specific order, usually from smallest to largest, or alphabetically if they are strings.

Sorting makes data easier to search, compare, and process efficiently.
Many algorithms, like binary search, only work if the data is sorted.

Selection sort

The idea

Selection sort repeatedly finds the smallest element from the unsorted part of the array and moves it to the beginning.

Step by step: 1. Find the smallest element in the array. 2. Swap it with the first element. 3. Find the next smallest and swap it with the second element. 4. Keep going until the array is sorted.

Example

Suppose we have:

[5, 8, 3, 4, 2]

We will find the smallest element, which is \(2\). Then, we swap it with the first element in the array, which is \(5\). The array now looks like this:

[2, 8, 3, 4, 5]

Now we want to set the second smallest element to the second position in the array. We find the smallest element among \([8,3,4,5]\), which is \(3\), and we swap it with the second element in the array, which is \(8\). After this, we have:

[2, 3, 8, 4, 5]

Next, we find the third smallest element, as the smallest element among \([8,4,5]\), which is \(4\). We swap it with the third element in the array, which is \(8\) again:

[2, 3, 4, 8, 5]

For the last step, we want to find the fourth smallest element, as the smallest element among \([5, 8]\), which is \(5\). We now need to swap it with the fourth element in the array, which turns out also to be \(5\). Swapping an element with itself doesn’t change the array, so finally the array is sorted:

[2, 3, 4, 5, 8]

Code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {5, 8, 3, 4, 2};
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }

    for (int x : arr) 
        cout << x << ' ';
    cout << '\n';
}

Output:

2 3 4 5 8

Selection sort is easy to understand, but not very efficient.

Time complexity

There are two nested loops (one inside another).
So it takes about \(n \cdot n\) steps → \(O(n^2)\) time.

Using the built-in sort function

In real programs and competitive programming, we rarely write sort manually.
C++ provides a very fast sorting function in the standard library.

Sorting a vector

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {5, 8, 3, 4, 2};
    sort(arr.begin(), arr.end());

    for (int x : arr) 
        cout << x << ' ';
    cout << '\n';
}

Output:

2 3 4 5 8

That one line sort(arr.begin(), arr.end()); sorts the entire vector in ascending order.

Sorting an array

You can also use the same sort function with regular arrays.
You just need to give the starting and ending pointers.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n = 5;

    int arr[] = {5, 8, 3, 4, 2}; 

    sort(arr, arr + n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << ' ';
    cout << '\n';
}

Output:

2 3 4 5 8

sort(arr, arr + n); means: sort starting from arr (first element) up to arr + n (just past the last one).

Sorting in descending order

If you want to sort from largest to smallest, you can use a custom comparison:

For vectors:

sort(arr.begin(), arr.end(), greater<int>());

Another way to do so for vectors is to call sort on reverse iterators. This sorts the array in ascending order and then reverses it:

sort(arr.rbegin(), arr.rend());

For C-arrays:

sort(arr, arr + n, greater<int>());

Output:

8 5 4 3 2

Sorting other types

The same function works for strings, doubles, or any comparable type:

vector<string> names = {"Bob", "Alice", "Charlie"};
sort(names.begin(), names.end());

Output:

Alice Bob Charlie

Sorting with custom comparator

We already mentioned that you can sort an array in descending order by adding a third parameter to the built-in sort function. This parameter is called the custom comparator. A comparator is a function that takes two elements, a and b, and returns true if a should come before b in the sorted array. This comes in handy when you want to sort your own data structure or sort an existing type with a different way of comparing elements.

For example, let’s say that we don’t want to sort strings lexicographically, but by their length. In this case, we would write our own comparator:

bool comparator_by_length(string a, string b){
    int len_a = a.length();
    int len_b = b.length();

    if (len_a < len_b)
        return 1;
    else
        return 0;
}

Then, we would call the sort function the same as before, and add the custom comparator in the call parameters:

vector<string> names = {"Bob", "Alice", "Charlie"};
sort(names.begin(), names.end(), comparator_by_length);

Output:

Bob Alice Charlie

Important note: Your comparator must behave like a real “less than” function: - No contradictions - No cycles like a < b, b < c, but also c < a

If the comparator is inconsistent, sort will behave unpredictably.

Complexity

The library sort function uses an optimized algorithm. Its time complexity is \(O(n \log n)\), which is much faster than \(O(n^2)\) for large inputs.

For example:

If \(n = 1,000\), selection sort does about \(1,000,000\) operations.
If \(n = 1,000\), library sort does about \(10,000\) operations — around \(100\) times faster.