Why is this recursive selection sort not working

May 30, 2022

I tried to run the code but it just gets stuck. NO error no warning nothing.Is there a better way to write a recursive selection sort?

#include <iostream>

using namespace std;

void scan(int *arr, int size){
    for(int i = 0; i < size; i++){
        cin >> arr[i];
    }
}

void print(int *arr, int size){
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

void swap(int *p1, int *p2){
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

void insertion(int *arr, int size){
    if(size <= 1)return;
    int i, max = size - 1;
    for(int i = 0; i < size; i++){
        if(arr[i]  > arr[max])max = i;
    }
    swap(&arr[max], &arr[i]);
    insertion(arr, size - 1);
}

int main(){
    int *arr;
    int size;
    cout << "Enter the size of the array - ";
    cin >> size;
    arr = (int*)malloc(size*sizeof(int));
    cout << "Enter the elements of the array - ";
    scan(arr, size);
    print(arr, size);
    insertion(arr, size);
    print(arr, size);
}

I feel like there is something wrong with the base case of the recursion. How do you generally solve these types of problems.

>Solution :

There was 1 small problem in your code. When you call the swap function in the insertion function you have to call it with &arr[max] and &arr[size-1], you can also use i-1, as the value of i is size here.

Code Attached for insertion function

void insertion(int *arr, int size){
    if(size <= 1)return;
    int i, maxIndex = 0;
    for(i = 0; i < size; i++){
        if(arr[i] > arr[maxIndex]) maxIndex = i;
    }

    swap(&arr[maxIndex], &arr[size-1]);
    insertion(arr, size - 1);
}

The way to debug are many, you can learn to use the gnu debugger which is gdb or use print statements to find out where your code is going wrong.