Home > Blockchain >  selection sort using recursion
selection sort using recursion

Time:12-13

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

CodePudding user response:

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];

CodePudding user response:

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 );
    }
}
  • Related