Bubble Sort

0

By Sean Burgess Pedersen on Dec 16th, 2010 8:31 am

This is yet another bubble sort.

int main(){
    int arr[] = {8, 3, 5, 1, 2, 9, 0, 2, 4, 6};
    bubble_sort(arr, 10);
    for (register int i = 0; i < 10; i++)
        std::cout << arr[i] << std::endl;
}

void bubble_sort(int *array, int len) {
    bool done;
    int* array_begin = array;
    int* array_end = array_begin;
    for (register int i = 0; i < len; i++) array_end++;
    while (!done) {
        done = true;
        for (register int* i = array_begin; i != array_end; i++) {
            int* j = i;
            j++;
            if (*i > *j) {
                    int temp = *i;
                    *i = *j;
                    *j = temp;
                done = false;
            }
        }
    }
}

1 Year Ago

0

This one is recursive.

static void bubble_sort(int* arr, const int len,
                        const bool done = true, const int i = 0)
{
    if (i == len) {
        if (done) return;
        return bubble_sort(arr, len);
    }
    if (arr[i] > arr[i+1]) {
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
        return bubble_sort(arr, len, false, i+1);
    } else return bubble_sort(arr, len, done, i+1);
}

seanbp

Junior Poster

129 posts since Jul 2010

Reputation Points: 20

Solved Threads: 15

1 Year Ago

0

int* array_end = array_begin;
for (register int i = 0; i < len; i++) array_end++;

This is a pointlessly roundabout (and slow) way of writing

int* array_end = array_begin + len;

More generally, what is the point in posting a bubble sort that works only on arrays of integers? The C++ standard library already contains a much faster sorting algorithm that works on any data structure that has an associated random-access iterator, and on any element type with a corresponding strict weak ordering.

arkoenig

Master Poster

703 posts since Jun 2010

Reputation Points: 359

Solved Threads: 109

1 Year Ago

0

Thank you.
It wasn't posted to be better than or equal to what's readily available. I want to get some feedback on my code to facilitate improvement.
- Sean

seanbp

Junior Poster

129 posts since Jul 2010

Reputation Points: 20

Solved Threads: 15

1 Year Ago

Show Comments

1

Using "register" is virtually pointless these days because those good folks that write compilers already have tons of optimizations that are working in your favor. I'm sure that someone who has a more intimate relationship with compilers can flesh that out a bit for you.

If you've never explored templates at all, this might be a good example to implement (I think that's what arkoenig was getting at, but I don't want to speak for him). I believe the STL uses a quicksort, so if you have a debugger that lets you step into the library code, you can take a look at it in action.

jonsca

Quantitative Phrenologist

Team Colleague

5,621 posts since Sep 2009

Reputation Points: 1,165

Solved Threads: 581

1 Year Ago

Show Comments

1

>> I want to get some feedback on my code to facilitate improvement.

Drop the array_begin and array_end pointer stuff. Use the [] operator instead on the passed in array. As pointed out, forget about register keyword. BubbleSort is slow already so drop the early exit boolean stuff and just simplify it all. That way you have at least something thats readable and just as slow-ish.

firstPerson

Senior Poster

3,923 posts since Dec 2008

Reputation Points: 841

Solved Threads: 608

1 Year Ago

0

Awesome advice. Thank you.

seanbp

Junior Poster

129 posts since Jul 2010

Reputation Points: 20

Solved Threads: 15

Bubble Sort

This article has been dead for over three months