C++ Sorting Array Recursion

Question

I am creating a small program that is supposed to sort integers in an array in ascending order, but I am extremely stuck on the algorithm that I am supposed to use. I cannot iterate through the array, I must instead use a recursion function. I am allowed to have an auxiliary function that can find the smallest index in the array, which I have done successfully, but I am having the hardest time figuring out how to use that function to sort my array in the recursion function. Here is the code that I have so far, I understand that my sortIntegers function is way off.

int main()
{
    int numbers[] = {8, 2, 5, 1, 3};
    sortingIntegers(numbers, 5);
    return 0;
}

void sortingIntegers(int *list, int size) {
    if (size == 1) {
        for (int i = 0; i < size; i++) {
            cout << list[i] << ", ";
        }
    } else {
        for (int z = 0; z < size; z++) {
            if (list[size - 1] == smallestIndex(list)) {
                for (int y = 0; y < size; y++) {
                    swap(list[z], list[y]);
                }
            }
        }
        sortingIntegers(list, size - 1);
    }

}

int smallestIndex(int *array) {
    int smallest = array[0];
    for (int i = 1; i < sizeof(array); i++) {
        if (array[i] < smallest) {
            smallest = array[i];
        }
    }
    return smallest;
}

Do you need to implement some specific sorting algorithm using recursion? — DixonD
– DixonD, Commented Feb 10, 2015 at 7:25
@DixonD, I do not need to use any specific sorting algorithm except that it must utilize a recursion function to sort. — andayn
– andayn, Commented Feb 10, 2015 at 7:34
@andayn In this case, both Quick Sort and Merge Sort can be easily implemented via recursion. — DixonD
– DixonD, Commented Feb 10, 2015 at 8:31
Your smallestIndex function does not return the location of the smallest element, it returns the vale of the smallest element. — user1196549
– user1196549, Commented Feb 10, 2015 at 8:51

prajmus · Accepted Answer · 2015-02-10 07:47:55Z

2

int main()
{
    int numbers[] = {8, 2, 5, 1, 0};
    sortingIntegers(numbers, 0, 5);
    for (int i=0;i<5;i++)
        cout << numbers[i] << ' ';
    return 0;
}

void sortingIntegers(int *list, int left, int size) {
    if (left == size)
        return;
    int smallest = smallestIndex(list, left, size);
    int c = list[smallest];
    list[smallest] = list[left];
    list[left] = c;
    sortingIntegers(list, left+1 ,size);
}

int smallestIndex(int *array, int left, int size) {
    int smallest = array[left];
    int smIndex = left;
    for (int i = left+1; i < size; i++) {
        if (array[i] < smallest) {
            smallest = array[i];
            smIndex = i;
        }
    }
    return smIndex;
}

That's my solution based on yours. First of all sizeof(array) returns the size of pointer. Second I return the index of the smallest item, not it's value, then I swap it with the first element in list. And then I call the sorting for the list starting with another element (the left parameter), because I know that the list up to left-1 is already sorted.

answered Feb 10, 2015 at 7:47

prajmus

3,2693 gold badges33 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

andayn Over a year ago

Ahh thank you very much, I was wondering how I could find which element in the array was the smallest so I could pass it onto the sortingIntegers function and the answer was so obvious but I couldn't see it. Thanks again.

score 0 · Accepted Answer · 2015-02-10 09:30:35Z

A fully recursive solution:

To sort an array, find the smallest element and swap it to the first position. Then sort the rest of the array, until there is a single element left.

To find the smallest element in an array, take the smallest of -the first element and -the smallest element in the rest of the array, until there is a single element left.

int SmallestIndex(int Array[], int From, int To)
{
  if (From == To-1)
    return From; // Single element left

  // Index of the smallest in the rest
  int Index= SmallestIndex(Array, From + 1, To);

  // Index of the smallest
  return Array[From] < Array[Index] ? From : Index;
}

void Sort(int Array[], int From, int To)
{
  if (From == To-1)
    return; // Single element left

  // Locate the smallest element
  int Index= SmallestIndex(Array, From, To);

  // Swap it to the first place
  int Swap= Array[Index]; Array[Index]= Array[From]; Array[From]= Swap;

  // Sort the rest
  Sort(Array, From + 1, To);
}

Call Sort with (Array, 0, N).

Soumadip Dey · Accepted Answer · 2021-06-17 18:45:33Z

-1

You can use this snippet to sort an array using recursion. It's not difficult you need to think like this way if your array length is N recursion sort N - 1 length array and you have to sort only one element that is N or you can say the last element. I give you an example it will help you suppose you have to sort this array = [50, 40, 10, 30, 20] if recursion gives you array = [10,30,40,50,20] this array you just need to place 20 in a correct position to sort the array.

private static void sort(int[] array, int length) {
            if (length == 1) return;
            sort(array, length - 1);
    
            var lastIndex = length - 1;
            for (int index = lastIndex; index > 0; index --){
                if (array[index] < array[index - 1]){
                    int temp = array[index];
                    array[index] = array[index - 1];
                    array[index - 1] = temp;
                }
            }
    
        }

edited Jun 17, 2021 at 18:45

answered Jun 17, 2021 at 18:34

Soumadip Dey

776 bronze badges

2 Comments

Deduplicator Over a year ago

Are you sure that's C++? ;-)

Soumadip Dey Over a year ago

I wrote this code in java it's not implemented using c++ you can easily convert this logic using any programming language.

Collectives™ on Stack Overflow

C++ Sorting Array Recursion

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related