0 
#include <iostream>
#include <cstdlib>

using std:: cin;
using std:: cout;
using std:: endl;

const int N=10;

void readarray(int array[], int N);
int bubble_sort (int array[], int size, int round,
                 int place);

int main ()
{
    int array[N];
    readarray( array, N );

    int round, place;
    cout << bubble_sort(array, N, place, round);


    return EXIT_SUCCESS;
}


void readarray(int array[], int N)
{
    int i=0;
    if (i < N)
    {
        cin >> array[i];
        readarray(array+1, N-1);
    }
}


int bubble_sort (int array[], int size, int round,
                int place)
{
    round =0;
    place =0;

  if (round < N-1) // this goes over the array again making sure it has 
                   // sorted from lowest to highest
  {
     if (place < N - round -1) // this sorts the array only 2 cells at a 
                               // time
         if (array[0] > array[1])
         {
            int temp = array[1];
            array[1]=array[0];
            array[0]=temp;
            return (array+1, size-1, place+1, round);
         }
   return (array+1, size-1, place, round+1);
   }
}

I know how to do a bubble sort using two for loops and I want to do it using recursion. Using loops you require two for loops and I figured for recursion it might also need two recursive functions/calls. This is what I have so far. The problem is that its outputting only one number, which is either 1 or 0. I'm not sure if my returns are correct.

Improve this question
5
  • You forgot the function name after return to make it call itself recursively. Also, you need a "base case" return statement (with no recursive call), probably at the very end of your function, if your function does return a non-void value (but why does it?). Commented Jan 23, 2016 at 20:10
  • 1
    Why? It's a terrible algorithm anyway; why make it worse? If you want an inefficient O(N^2) sort, insertion sort and selection sort are at least simple and easy to understand. If you just want to sort things, use std::sort. Commented Jan 23, 2016 at 20:10
  • @AlanStokes i want to practice recursive functions and bubble sort seems like a good practice. So any help would be appreciated. Commented Jan 23, 2016 at 20:18
  • @leemes What would the "base case" be? Commented Jan 23, 2016 at 20:29
  • @AncientDragon Since your function has a return type of int, you would need to return some integer value... But I guess you did a mistake here and didn't meant to return a value at all. Then, you would just return; which you don't need to write at all. Commented Jan 23, 2016 at 23:45

2 Answers 2

Reset to default
1

In c++11, you can do this:

#include <iostream>
#include <vector>


void swap(std::vector<int &numbers, size_t i, size_t j)
{
    int t = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = t;
}

bool bubble_once(std::vector<int> &numbers, size_t at)
{
    if (at >= numbers.size() - 1)
        return false;
    bool bubbled = numbers[at] > numbers[at+1];
    if (bubbled)
        swap(numbers, at, at+1);
    return bubbled or bubble_once(numbers, at + 1);
}

void bubble_sort(std::vector<int> &numbers)
{
    if ( bubble_once(numbers, 0) )
        bubble_sort(numbers);
}

int main() {
    std::vector<int> numbers = {1,4,3,6,2,3,7,8,3};
    bubble_sort(numbers);

    for (size_t i=0; i != numbers.size(); ++i)
        std::cout << numbers[i] << ' ';
}

In general you can replace each loop by a recursive function which:

  1. check the guard -> if fail return.
  2. else execute body
  3. recursively call function, typically with an incremented counter or something.

However, to prevent a(n actual) stack overflow, avoiding recursion where loops are equally adequate is good practice. Moreover, a loop has a very canonical form and hence is easy to read for many programmers, whereas recursion can be done in many, and hence is harder to read, test and verify. Oh, and recursion is typically slower as it needs to create a new stackframe (citation needed, not too sure).

EDIT

Using a plain array:

#include <iostream>
#include <vector>

#define N 10

void swap(int *numbers, size_t i, size_t j)
{
    int t = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = t;
}

bool bubble_once(int *numbers, size_t at)
{
    if (at >= N - 1)
        return false;
    bool bubbled = numbers[at] > numbers[at+1];
    if (bubbled)
        swap(numbers, at, at+1);
    return bubbled or bubble_once(numbers, at + 1);
}

void bubble_sort(int *numbers)
{
    if ( bubble_once(numbers, 0) )
        bubble_sort(numbers);
}

int main() {
    int numbers[N] = {1,4,3,6,2,3,7,8,3,5};
    bubble_sort(numbers);

    for (size_t i=0; i != N; ++i)
        std::cout << numbers[i] << ' ';
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks, not really familiar with std::vectors, if there is an alternative way it would be very much appreciated.
You can swap std::vector<int> with int[N] and number.size() with N if you prefer.
Just to make sure, the size_t stands for the size of the vector?, and if so can I replace it with something else. (Not really comfortable using vectors yet). Thanks a lot!
no, size_t is a type like int (in particular, it is an unsigned integer). size_t as in size type.
I find or to be way more readable than ||, especially since you can read or and you can't really read || ;)
1

Please read this post

function pass(i,j,n,arr)
{
  if(arr[i]>arr(j))
    swap(arr[i],arr[j]);

  if(j==n)
  {
    j=0;
    i=i+1;
  }
  if(i==n+1)
    return arr;

  return pass(i,j+1,n,arr);
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.