Question

How to sort a vector with a single loop in C++

Answer 1

#include <iostream>
#include <vector>
 
// A simple function to print a sequence of values.
// Keeping printing separate makes main() cleaner.
void print_values(const std::vector<int>& values) {
    for (int v : values) {
        std::cout << v << " ";
    }
    std::cout << "\n";
}
 
// Sort the array using a single-loop variant of "gnome sort".
// This algorithm walks forward, but whenever it finds two adjacent
// elements out of order, it swaps them and steps back by one.
// Because the index moves both forward and backward inside the same loop,
// we don't need nested loops.
//
// This approach is expressive, easy to follow, and uses only one loop.
// It is not the fastest algorithm for large datasets, but it is efficient
// enough for small to medium inputs and demonstrates the technique clearly.
void single_loop_sort(std::vector<int>& values) {
    std::size_t i = 0;
    int size = values.size();
 
    // One loop only.
    while (i < size) {
 
        // If we're at the beginning or the current pair is in order,
        // move forward.
        if (i == 0 || values[i] >= values[i - 1]) {
            ++i;
        } else {
            // Otherwise, swap the out-of-order pair.
            std::swap(values[i], values[i - 1]);
 
            // Step back to re-check previous relationships.
            --i;
        }
    }
}
 
int main() {
    std::vector<int> values {42, -5, 12, 0, 89, -18, 33, 7};
 
    std::cout << "Original values:\n";
    print_values(values);
 
    // Perform the single-loop sort
    single_loop_sort(values);
 
    std::cout << "Sorted values:\n";
    print_values(values);
}

 
 
/*
run:
 
Original values:
42 -5 12 0 89 -18 33 7 
Sorted values:
-18 -5 0 7 12 33 42 89 
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <ranges>

/**
 * Sorts a random-access range in-place in non-decreasing order using Gnome Sort.
 *
 * Algorithm Logic (Single Loop):
 * - Starts at the second element (index 1) and moves forward as long as elements
 *   are in ascending order.
 * - When an out-of-order pair is found, swaps the elements and steps backward one position
 *   to ensure the swapped value is correctly sorted relative to preceding elements.
 * - Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
 * - Space Complexity: O(1) auxiliary space.
 *
 * Uses C++20 concepts and standard library functions (`std::swap`, `std::ranges`)
 * to work seamlessly with modern modern containers.
 */
template <std::ranges::random_access_range Range>
    requires std::totally_ordered<std::ranges::range_value_t<Range>>
void single_loop_sort(Range& range) {
    using std::swap;
    const auto size = std::ranges::size(range);
    std::size_t pos = 0;

    while (pos < size) {
        // Advance if at the start or if adjacent pair is in correct order
        if (pos == 0 || range[pos] >= range[pos - 1]) {
            ++pos;
        } else {
            // Swap out-of-order elements and step back to re-check preceding elements
            swap(range[pos], range[pos - 1]);
            --pos;
        }
    }
}

/**
 * Prints all elements in a range separated by spaces.
 */
template <typename Range>
void print_range(const Range& range) {
    for (const auto& elem : range) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::vector<int> numbers = {42, -5, 12, 0, 89, -18, 33, 7};

    std::cout << "Original array:\n";
    print_range(numbers);

    single_loop_sort(numbers);

    std::cout << "\nSorted array:\n";
    print_range(numbers);
}



/*
run:

Original array:
42 -5 12 0 89 -18 33 7 

Sorted array:
-18 -5 0 7 12 33 42 89 

*/

 

70+ SQL courses for beginners and professionals