selection sort using recursion

Question

void swap(int a[], int x, int y)
{

    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}
void sort(int arr[], int x)
{
    static int count = 0;
    if (x == 1)
    {
        return;
    }
    int min = 100;    //  random value
    int index;
    for (int i = 0; i < x; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            index = i;
        }
    }
    swap(arr, count, index);
    count++;
    sort(arr + 1, x - 1);
}
int main()
{
    int x;
    cin >> x;
    int A[x];
    for (int i = 0; i < x; i++)
    {
        cin >> A[i];
    }
    sort(A, x);
    for (int i = 0; i < x; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}

this code is of selection sort using recursion. It is printing garbage values. what's the mistake in this. i am not sure but i guess because of using the static variable in the sort function(). it is printing garbage values

FYI, [variable length arrays](https://stackoverflow.com/q/1887097/11082165) like `int A[x];` are not legal in standard C++. Using a construct like that is only possible with non-standard compiler extensions to the C++ language. Also, re: initializing `min` to `-1` with the comment _"random value because given arrays have positive elements"_, when will `(positive element) < min` be true? — Brian61354270, Dec 12 '21 at 20:02
With the static variable it's unable to call the function twice. Why not declaring `sort(int arr[], int first, int last)`? — 273K, Dec 12 '21 at 20:06
Just remove count and any its usage. You already did arr + 1 and count makes swap min with arr + 1 + count that leads half of attempts to access outside the array. — 273K, Dec 12 '21 at 20:12
"random value" comment reminded me something from badcode website or something similar .. `const int rnd = 13; // a random value obtained by throwing a d20 dice` — Swift - Friday Pie, Dec 12 '21 at 21:07
Don’t use recursion where no recursion is needed (e.g. in this case). That would have avoided most of the problems. Also, never use `static` local variables unless you (a) know very precisely what you are doing or (b) hate recursion and hate multi-threading, both at the same time. — Andrej Podzimek, Dec 12 '21 at 21:30

273K · Accepted Answer · 2021-12-12T20:23:29.930

0

Replace swap(arr, count, index); with

swap(arr, 0, index);

and remove static int count = 0;.

Replace sort(A, x); in the main with

sort(A, x - 1);

and change the condition if (x == 1) to if (x == 0).

I suggest to rename index to last.

Replace min = 100; with

min = arr[0];

edited Dec 12 '21 at 20:23

answered Dec 12 '21 at 20:18

273K

29,503
10
41
64

Vlad from Moscow · Answer 2 · 2021-12-12T20:35:26.407

For starters variable length arrays like this

int x;
cin >> x;
int A[x];

is not a standard C++ feature.

Nevertheless the function can invoke undefined behavior when for example is called with the second parameter equal to 0.

Also there is no sense to declare the static variable.

The function will not sort an array elements of which have values greater than 100.

The variable index must be initialized to 0 before the for loop.

Also there is already the standard function std::swap that swaps two objects.

The function can be defined the following way

#include <algorithm>

void selection_sort( int a[], size_t n )
{
    if ( not ( n < 2 ) )
    {
        auto it = std::min_element( a, a + n );

        if ( it != a ) std::iter_swap( a, it );

        selection_sort( a + 1, n - 1 );
    }
}

If you do not know yet standard algorithms then the functions can look the following way

void swap( int &a, int &b )
{
    int rmp = a;
    a = b;
    b = tmp;
}

void selection_sort( int a[], size_t n )
{
    if ( not ( n < 2 ) )
    {
        size_t index = 0;

        for ( size_t i = 1; i < n; i++ )
        {
            if ( a[i] < a[index] ) index = i;
        }

        if ( index != 0 ) swap( a[0], a[index] );  

        selection_sort( a + 1, n - 1 );
    }
}

score 0 · Answer 3 · answered Jul 09 '22 at 11:12

One of the easy ways of doing the selection sort using recursion is as follows:

#include<iostream>
using namespace std;

void selectionSort(int *arr, int size,int minIndex){
    //base case
    if(size ==0 || size ==1 || minIndex == size){
        return;
    }

    //processing
    for(int i=minIndex+1;i<size;i++){
        if(arr[i]<arr[minIndex]){
            swap(arr[minIndex], arr[i]);
        }
    }
    //recursive call
    selectionSort(arr,size,minIndex+1);
}


int main(){

   int arr[7]={7,6,5,4,3,2,1};
    int size = 7;
    int minIndex = 0;
    selectionSort(arr,size,minIndex);
    for(int i=0;i<7;i++){
        cout<<arr[i]<<" ";
    }
}

We are creating a minIndex at the starting of the array and comparing it with the values in the remaining array, to get the minimum value of the whole array on the left-most side. At each recursive call, we will increment the place of minIndex for further comparison. Hope this helps.

Burhan Shaheen · Answer 4 · 2023-01-17T09:16:19.340

0

a=[6,5,4,3,2,1,0,-1]

length=a.length

cur=0

n=cur+1

function fun(n)

{

    if(cur==length-1)
    {
        return a
    }
    else if(a[cur]>a[n])
    {
        temp=a[cur]
        a[cur]=a[n]
        a[n]=temp
        if(n==length-1)
        {
            n=cur
            cur++
        }
        // console.log(a)
        // console.log(cur)
        return fun(n+1)
    }
    else
    {
         if(n==length-1)
        {
            n=cur
            cur++
        }
         return fun(n+1)
    }
   
}

let t=[]

t=[...fun(n)]

console.log(t)

edited Jan 17 '23 at 09:16

answered Jan 14 '23 at 12:51

Burhan Shaheen

1
2

1

Please try to add some supporting information to your post that explains what your code does. There appears to be issues with formatting in your answer as well, take a look at https://stackoverflow.com/editing-help – jv-k Jan 16 '23 at 15:32

selection sort using recursion

4 Answers4