Is this recursive implementation of bubble sort inefficient, and how could it be improved if possible?

user_15593050 0
Viewed 78

Yesterday I came across a recursive implementation of bubble sort, which looks elegant at first glance:

template <class T> void bubblesort_recursive(T data[], const int n){
    if(n==1) return;
    else{
        bubblesort_recursive(data+1, n-1);
        if(data[1]<data[0]) swap(data[1],data[0]);
        bubblesort_recursive(data+1, n-1);
    }
}

However, I soon realized that it calls the recursive case twice and the time recursive relation for its time complexity seems to be following T(n)=2T(n-1)+c, which leads to exponential time complexity. However, bubble sort usually leads to n^2 time complexity. Is my analysis somewhere wrong or is this just an inefficient implementation of bubble sort? If it was the latter one, how could it be improved?

sorting algorithm c++
1 Answers

which leads to exponential time complexity.

True.

However, bubble sort usually leads to n^2 time complexity.

True.

how could it be improved?

If you are looking for a recursive implementation of bubble sort that has O(²) complexity, then we need to distinguish two processes:

  1. One sweep of bubbling
  2. Repeating this with shorter sections of the array

Both can be implemented in a recursive way, but they will be distinct recursions:

template <class T> void bubble_recursive(T data[], const int n) {
    if (n == 1) return;
    if (data[1] < data[0]) swap(data[1], data[0]);
    bubble_recursive(data + 1, n - 1);
}

template <class T> void bubblesort_recursive(T data[], const int n) {
    if (n == 1) return;
    bubble_recursive(data, n);
    bubblesort_recursive(data, n-1);
}

You can also add the early exit feature that some bubble sort implementations have: when a single sweep for bubbling shows that no swap had to be performed, then we know the array is sorted, and can stop doing more iterations on shorter sections:

template <class T> bool bubble_recursive(T data[], const int n) {
    if (n == 1) return false;
    bool must_swap = data[1] < data[0]; 
    if (must_swap) swap(data[1], data[0]);
    return bubble_recursive(data + 1, n - 1) || must_swap;
}

template <class T> void bubblesort_recursive(T data[], const int n) {
    if (bubble_recursive(data, n))
        bubblesort_recursive(data, n - 1);
}
user_54598390
Related