#include <algorithm>#include <cassert>#include <cstdint>#include <iostream>#include <vector>
Implementation of the Selection sort implementation using recursion.
The selection sort algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on the sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
ImplementationFindMinIndex This function finds the minimum element of the array(list) recursively by simply comparing the minimum element of array reduced size by 1 and compares it to the last element of the array to find the minimum of the whole array.
SelectionSortRecursive Just like selection sort, it divides the list into two parts (i.e.: sorted and unsorted) and finds the minimum of the unsorted array. By calling the FindMinIndex function, it swaps the minimum element with the first element of the list, and then solves recursively for the remaining unsorted list.
Definition in file selection_sort_recursive.cpp.
Self-test implementations.
Definition at line 95 of file selection_sort_recursive.cpp.
95 {
96
97
98 std::vector<uint64_t> array1 = {0, 1, 1, 2};
99 std::cout << "1st test... ";
101 assert(std::is_sorted(std::begin(array1), std::end(array1)));
102 std::cout << "passed" << std::endl;
103
104
105 std::vector<uint64_t> array2 = {1, 0, 0, 1, 1, 0, 2, 1};
106 std::cout << "2nd test... ";
108 assert(std::is_sorted(std::begin(array2), std::end(array2)));
109 std::cout << "passed" << std::endl;
110
111
112 std::vector<uint64_t> array3 = {1, 1, 0, 0, 1, 2, 2, 0, 2, 1};
113 std::cout << "3rd test... ";
115 assert(std::is_sorted(std::begin(array3), std::end(array3)));
116 std::cout << "passed" << std::endl;
117
118
119 std::vector<uint64_t> array4 = {2, 2, 2, 0, 0, 1, 1};
120 std::cout << "4th test... ";
122 assert(std::is_sorted(std::begin(array4), std::end(array4)));
123 std::cout << "passed" << std::endl;
124}
void selectionSortRecursive(std::vector< T > &in_arr, uint64_t current_position=0)
The main function implements Selection sort.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4