(May 7, 2020 09:35 AM)Tafelpoot Wrote:  What exactly do you mean by recursion?
Merge sort can be easily used, but idk if that adheres to your requirement.
Please elaborate.

(May 8, 2020 01:36 AM)4Txe4y33C9zvNhMj Wrote:  Probably not the most efficient way of doing it.

(May 8, 2020 01:46 PM)Tafelpoot Wrote:  I have chosen to do a lesser known sorting alorithm called interpolation sort.
It was quite a challenge since there is little information available, most available sources talk about the interpolation search instead of sort.

Code

#include <iostream>
#include <math.h>
#include <vector>
int call_counter = 0;
void interpolation_sort(std::vector<int>& unsorted_number) {
++call_counter;
// 0 and 1 element require no sort
if (unsorted_number.size() < 2) return;

// no bucket size stack needed because recursion
int cur_size = unsorted_number.size();
std::vector<std::vector<int>> bucket(cur_size);

int start = 0;
int min = unsorted_number[start];
int max = min;

// start + 1, min and max are already [index=0] so no need to check
for (int index = start + 1; index < cur_size; ++index)
{
if (unsorted_number[index] < min) min = unsorted_number[index];
else if (unsorted_number[index] > max) max = unsorted_number[index];
}

// e.g. 10, 10, 10, 10 or 3, 3
if (min == max) return;

// Looping with pointer prob. faster
for (int index = start; index < cur_size; ++index)
{
// Cast to double to prevent int div, ignore C26541 because wrapping can't happen
int bucket_index_interpolation =
(double)(unsorted_number[index] - min) / (max - min) * (cur_size - 1);
bucket[bucket_index_interpolation].push_back(unsorted_number[index]);
}

for (int bucket_index = 0; bucket_index < cur_size; ++bucket_index)
{
if (bucket[bucket_index].empty()) continue;

interpolation_sort(bucket[bucket_index]);

for (int bucket_value = 0; bucket_value < bucket[bucket_index].size(); ++bucket_value)
{
unsorted_number[start++] = bucket[bucket_index][bucket_value];
}
//bucket[bucket_index].clear();
}
}

int main() {
std::vector<int> unsorted_numbers = { 2, 9, 5, 10, 10, 10, 10, 10, 10, 10, 10, 99, 58, 17, 86, 105, 34, 63, 42, 71 };

interpolation_sort(unsorted_numbers);

std::cout << "amount of calls: " << call_counter << std::endl;
for (int i = 0; i < unsorted_numbers.size(); ++i)
std::cout << unsorted_numbers[i] << ' ';
}

While doing this sort I read up on bucket sort and thought of a (new) way to do bucket sort.
Can't seem to find a similar solution to what I thought of, I will try to implement it tommorow and post the solution here.

(May 20, 2020 06:33 PM)VureX Wrote:  i dont what to do just started trying to learn

(May 8, 2020 04:53 AM)saltycracker Wrote:  If you are reaching for recursion in C or C++ then I can guarantee that its not the most efficient solution. The standard doesn't even include tail call optimization so you can't guarantee anything without inspecting the code your implementation produced.