How to implement quicksort using iterator format?

@muriel.schmidt 

To implement quicksort using iterators, you can follow these steps:

1. Define a function quicksort that takes in a pair of iterators representing the beginning and end of the range to be sorted.
2. In the quicksort function, if the distance between the iterators is less than 2 (i.e., the range contains 0 or 1 elements), return immediately.
3. Choose a pivot element from the range. This can be the middle element, the first element, or a random element.
4. Partition the range into two sub-ranges: elements less than the pivot and elements greater than or equal to the pivot.
5. Recursively call quicksort on the two sub-ranges.
6. Finally, combine the sorted sub-ranges to get the sorted range.

Here is a sample implementation of quicksort using iterators:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <vector>

template <class Iterator>
void quicksort(Iterator begin, Iterator end) {
    if (std::distance(begin, end) < 2) {
        return;
    }

    Iterator pivot = begin;
    Iterator i = begin;
    
    for (Iterator j = begin + 1; j != end; ++j) {
        if (*j < *pivot) {
            i++;
            std::iter_swap(i, j);
        }
    }
    
    std::iter_swap(pivot, i);
    
    quicksort(begin, i);
    quicksort(i + 1, end);
}

int main() {
    std::vector<int> vec = {5, 3, 8, 2, 7, 1, 10, 4};
    
    quicksort(vec.begin(), vec.end());
    
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

In this implementation, the quicksort function takes in iterators representing the range of elements to be sorted. The std::distance function is used to find the distance between two iterators. The std::iter_swap function is used to swap elements in the range. Finally, the main function demonstrates how to use the quicksort function to sort a std::vector of integers.