Recursive selection in C++ not fully working

selection sort using recursion in c
recursive selection sort pseudocode
selection sort recursive python
time complexity of recursive selection sort
insertion sort using recursion in c
recursive selection sort linked list c++
non-recursive selection sort
selection sort in c

I'm trying to write a recursive function that sorts a small array by selection. I can get everything to load and run, but the output when the array is {3, 1, 8, 5} keeps outputting as {1, 3, 3, 3}. I think it's got something to do with how the minimum value is assigned, but I'm stuck on exactly where that is. Any suggestions?

#include <iostream>
#include <conio.h>
#include <array>

using namespace std;

int arrLength = 4;
int minimum;
int counter = 0;

int sortedArr[];
int tempArr[];

void sortFunc(int, int);

int valueArr[4] = { 3,1,8,5 };
int tempArr[4] = {};

void main() {

    cout << "Before sorting..." << endl;

    for (int i = 0; i < 4; i++) {
        cout << valueArr[i] << " ";
    }

    cout << endl;

    sortFunc(4, counter);

    cout << "After sorting..." << endl;

    for (int i = 0; i < 4; i++) { //either broken here
        cout << tempArr[i] << " ";
    }

    _getch();
}

void sortFunc(int size, int counter) {
    minimum = valueArr[0];

    for (int i = 1 + (counter); i <  size; i++) { //or here
        if (valueArr[i] < minimum) {
            minimum = valueArr[i];
        }
    }

    tempArr[counter] = minimum;

    if (counter < size) {
        counter++;
        sortFunc(size, counter);
    }
}

I couldn't clearly see how your strategy can be tweaked just a bit to make your function work. I think you need to sort the array in place by swapping elements. For that to work, you need to:

  1. Copy valueArr to tempArr first.
  2. Sort tempArr in place. That leaves valueArr in its original state. I am assuming that was your intention.

In main, use:

// Copy valueArr to tempArr
std::copy(valueArr, valueArr+4, tempArr);

In sortFunc, use:

void sortFunc(int size, int counter) {
   if ( size == counter )
   {
      return;
   }

    int minimum = tempArr[counter];

    for (int i = 1 + (counter); i <  size; i++) {
        if (tempArr[i] < minimum) {
            minimum = tempArr[i];
            std::swap(tempArr[counter], tempArr[i]); 
        }
    }

    sortFunc(size, counter+1);
}

Suggestions for further cleanup.

  1. Don't use any global variables.
  2. Pass all the arguments to sortFunc.
  3. Change the return type of main to int.

Here's a cleaned up version.

#include <iostream>
#include <algorithm>

using namespace std;

void sortFunc(int arr[], int, int);

int main() {

    cout << "Before sorting..." << endl;

    int valueArr[4] = { 3,1,8,5 };
    int tempArr[4] = {};

    for (int i = 0; i < 4; i++) {
        cout << valueArr[i] << " ";
    }

    cout << endl;

    // Copy valueArr to tempArr
    std::copy(valueArr, valueArr+4, tempArr);
    sortFunc(tempArr, 4, 0);

    cout << "After sorting..." << endl;

    for (int i = 0; i < 4; i++) { //either broken here
        cout << tempArr[i] << " ";
    }
    cout << endl;
}

void sortFunc(int arr[], int size, int counter) {
   if ( size == counter )
   {
      return;
   }

    int minimum = arr[counter];

    for (int i = 1 + (counter); i <  size; i++) {
        if (arr[i] < minimum) {
            minimum = arr[i];
            std::swap(arr[counter], arr[i]); 
        }
    }

    sortFunc(arr, size, counter+1);
}

Recursive selection in C++ not fully working - c++ - android, I'm trying to write a recursive function that sorts a small array by selection. I can get everything to load and run, but the output when the array is {3, 1, 8, 5} keeps  I had the wrong string in my mind. I'm still not seeing whats wrong. Could you explain a little farther. Post the exact code that compiles and gives you the problem, along with your results, whether it is working or not. To help you debug, place the following line: cout << str << endl; before the recursive call so you can see each iteration.


I believe that you should not be initializing the minimum value at line

minimum = valueArr[0];

Instead just assign it to large number or use valueArr[counter + 1]

The reason for this strange behavior is likely that the first entry in valueArr is actually smaller than those you encounter later in the array, therefore it won't get properly initialized...

ADD: See INT_MAX or numeric_limits for the "large number"


ADD2: Anyway, looking more closely, your recursion has incorrect concept... if you intend to sort the array, you have to always swap the current element with the one you choose in every iteration. Otherwise you will start loosing elements, as you do. In any case, recursion might not be the best way to tackle sorting... Maybe try two nested cycles

Recursive Selection Sort, The Selection Sort algorithm sorts maintains two parts. Recursive C++ program to sort an array Swapping when index nd minimum index are not same. recursive selection sort.. i built this code exactly like in the theory this will not work together recursive quick sort - stack overflow.


There were some basic logical errors in your code,

void sortFunc(int size, int counter) {
    minimum = 2147483647; // Point 1
    int mytemp;
    for (int i = 0; i <  size; i++) { // Point 3
        if (valueArr[i] < minimum) {
            minimum = valueArr[i];  //Point 2
            mytemp = i;
        }
    }
    valueArr[mytemp] = 2147483647;
    tempArr[counter] = minimum;

    if (counter < size) {
        counter++;
        sortFunc(size, counter);
    }
}

1. The minimum variable should always be the maximum possible value and you need to keep track of the index of the min value in the valueArr

  1. After finding out a minumum value in valueArr, you need to make sure you don't visit the same value again, so keep track of it's index and change it's value necessarily

  2. The loop iterable starts from 1+(counter) in your code, what if the minimum lies before that? That's why you need to start from the beginning.

I hope you got my point. Cheers!

Recursion Practice Problems with Solutions, Recursion is very important concept in computer science and one just cannot neglect Replace each element of array with product of every other element without Reverse a Linked List in C/C++ using Recursion · Recursively check if linked Construct a full binary tree from preorder sequence with leaf node information  Tail recursion is defined as occuring when the recursive call is at the end of the recursive instruction. This is not the case with my factorial solution above. It is useful to notice when ones algorithm uses tail recursion because in such a case, the algorithm can usually be rewritten to use iteration instead.


Besides the useful advice and tips provided in R Sahu's answer, the following function template would work as a recursive STL-like implementation of the selection sort algorithm:

#include <iterator>   // std::next
#include <algorithm>  // std::min_element

template<typename ForwardIt>
void sortFunc(ForwardIt first, ForwardIt last) {
    // base case
    if (first == last || std::next(first) == last)
        return; // empty range or range with a single element

    // recursive case
    auto selected_it = std::min_element(first, last);
    using std::swap;
    swap(*selected_it, *first);
    return selection_sort(++first, last);
}

This way selection sort can be performed on any type that implements operator<, and it is not limited to just int (as in your sortFunc()).

The implementation above allows for tail recursion optimisation to take place, so, don't forget to enable it, if you are going to sort large arrays (or other collections).


You can use the sortFunc function template above with C-style arrays (as in your example):

// copy valueArr to tempArr
std::copy(valueArr, valueArr+4, tempArr);
// sort tempArr
sortFunc(tempArr, tempArr+4);

as well as with any STL container that implements forward iterators:

std::vector<int> vec(valueArr, valueArr+4);
std::list<int> lst(valueArr, valueArr+4);
std::forward_list<int> fwdlst(valueArr, valueArr+4);

sortFunc(vec.begin(), vec.end());
sortFunc(lst.begin(), lst.end());
sortFunc(fwdlst.begin(), fwdlst.end());

Reading 10: Recursion, Since you've taken 6.01, recursion is not completely new to you, and you have seen and For example, subsequences("abc") might return "abc,ab,bc,ac,a,b,c," . At first, we would select “o” to be in the partial subsequence, and recursively extend it with can be called even though factorial(n) hasn't yet finished working. Recursive Selection Sort. The Selection Sort algorithm sorts maintains two parts. Second part that is yet to be sorted. The algorithm works by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the end of sorted part.


Recursion and sorting algorithms, Recursion. I'm going to present pretty much all of the sorting algorithms For anything that is not the smallest case, how do I break it down to make it smaller? That is, assume that factorial_rec(n - 1) will work and give us the right answer; we Effectively, selection sort splits the list into the sorted region at the beginning,  C = A + B will assign the value of A + B to C += Add AND assignment operator. It adds the right operand to the left operand and assign the result to the left operand. C += A is equivalent to C = C + A-= Subtract AND assignment operator. It subtracts the right operand from the left operand and assigns the result to the left operand.


Solved: 3. Selection Sort Can Be Thought Of As A Recursive , A. Write Down The Recursive Version Of Selection Sort In Psuedocode. Use the formal definitions of Big O (not the Limit Rule) to 3. 4n^3 + 4n + 12 lessthanorequalto c(n^2 - 4n + 8) Here c = 4 n_0 = -2 2n^3 - 3n^2 + 17 n = Cn^3 c = 2 n_0 = 17/3 view the full answer Explaining your work is thus essential for full credit. Recursion in C Programming The process of calling a function by itself is called recursion and the function which calls itself is called recursive function. Recursion is used to solve various mathematical problems by dividing it into smaller problems.


Quicksort algorithm overview | Quick sort (article), Like merge sort, quicksort uses divide-and-conquer, and so it's a recursive algorithm. In merge sort, the divide step does hardly anything, and all the real work happens in the Why not the median of three method, which is supposed to do it better? Pivot selection is an important part of quick sort and there are many  Replace the recursive function max with a new recursive function maxInd (in Java, or maxind in C) that will return the integer index of the largest element in the array. (For the new task, we no longer care what the value of the largest element is.) Test the function maxInd with a separate run.