C++ Bubble sort dynamically allocated array

Question

I wrote a bubble sorting algorithm which sorts a dynamically allocated array using string comparison.

Here is my code:

void AddressBook::bubble_sort_address_book(){
    bool swapped = true;
    while(swapped){
        swapped = false;
        for(int i = 0; i < noOfEmployees; i++){
            if(employees[i].combined_name() > employees[i+1].combined_name()){
                Employee temp_employee = employees[i+1];
                employees[i+1] = employees[i];
                employees[i] = temp_employee;
            }
        }
    }
}

My problem is pretty obvious, yet I can not seem to figure out how to solve it: The code sometimes fails on the line (in an undefined manner) :

Employee temp_employee = employees[i+1]

Its pretty obvious because if i is equal to the end of the array, accessing memory with i+1 results in undefined behaviour. However, if I stop the for loop with noOfEmployees-1, this does not happen but the first element is never sorted (obviously).

How can I implement bubble sort properly? It seems as such a trivial task. Am I missing something?

i < noOfEmployees really must be i < noOfEmployees-1. And the first element gets sorted this way. — Paul Ogilvie
– Paul Ogilvie, Commented Oct 21, 2017 at 13:53
but the first elements always remains unsorted this way, at least in my code — Balázs Vincze
– Balázs Vincze, Commented Oct 21, 2017 at 13:54
There is also std::sort, which would also be more efficient than the bubble sort you're using. — Rakete1111
– Rakete1111, Commented Oct 21, 2017 at 13:56
Following the exchange, add swapped = true; as you just swapped. — Paul Ogilvie
– Paul Ogilvie, Commented Oct 21, 2017 at 13:56
Yes, but we are not allowed to use anything except for std::string, not even std::vector! (It's a university assignment) — Balázs Vincze
– Balázs Vincze, Commented Oct 21, 2017 at 13:57

Paul Ogilvie · Accepted Answer · 2017-10-21 14:14:11Z

1

The following simplified version in pure C works fine:

int employees[10]= {3,1,7,6,9,7,1,0,2,6};
int noOfEmployees= 10;

void bubble_sort_address_book(void){
    bool swapped = true;
    int i;
    while(swapped){
        swapped = false;
        for(i = 0; i < noOfEmployees-1; i++){
            if(employees[i] > employees[i+1]){
                int temp_employee = employees[i+1];
                employees[i+1] = employees[i];
                employees[i] = temp_employee;
                swapped= true;
            }
        }
    }
}
int main()
{
    int i;
    bubble_sort_address_book();
    for (i=0; i<noOfEmployees; i++) {
        printf("emp %d= %d\n", i, employees[i]);
    }
    return 0;
}

As you request, the function of variable swapped is to indicate that following a complete pass through the array no swap occurred and so it indicates the array is now sorted.

edited Oct 21, 2017 at 14:14

answered Oct 21, 2017 at 14:08

Paul Ogilvie

25.3k4 gold badges25 silver badges43 bronze badges

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

Comments

Caleth · Accepted Answer · 2018-06-25 11:29:41Z

You can use an explicit bound on the outer loop.

You should also split things out into smaller functions.

bool operator <(Employee const & lhs, Employee const & rhs) {
    return lhs.combined_name() < rhs.combined_name();
}

// a.k.a. std::swap
void swap(Employee & lhs, Employee & rhs) {
    Employee temp(static_cast<Employee&&>(lhs)); // a.k.a. std::move
    lhs = static_cast<Employee&&>(rhs);
    rhs = static_cast<Employee&&>(temp);
}

void bubble_sort_impl(Employee * begin, Employee * end) {
    for (; end != begin; --end) {
        for (Employee * it = begin; it+1 != end; ++it) {
            if (*(it+1) < *it) {
                swap(*it, *(it+1));
            }
        }
    }
}

// do we really need "bubble_" or "_address_book" in this name?
void AddressBook::bubble_sort_address_book() {
    bubble_sort_impl(employees, employees + noOfEmployees);
}

Andre Ahmed · Accepted Answer · 2017-10-21 14:21:48Z

another solution:

#include <iostream>
#include <vector>


using namespace std;

int employees[10] = { 3,1,7,6,9,7,1,0,2,6 };


void bubble_sort_address_book(void) {
    bool swapped = true;
    int i;
    int noOfEmployees = 10;
    while (swapped) {
        swapped = false;
        for (i = 1; i <= noOfEmployees ; i++) {
            if (employees[i] > employees[i - 1]) {
                int temp_employee = employees[i - 1];
                employees[i - 1] = employees[i];
                employees[i] = temp_employee;
                swapped = true;
            }
        }
    }
}
int main()
{
    int i;
    int noOfEmployees = 10;
    bubble_sort_address_book();
    for (i = 0; i<noOfEmployees; i++) {
        printf("emp %d= %d\n", i, employees[i]);
    }
    return 0;
}

Collectives™ on Stack Overflow

C++ Bubble sort dynamically allocated array

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related