How to implement bubble sort?

Question

I have to write a program that takes in 10 integers then displays them. Then displays them in reverse order. Lastly displays them in ascending order. Here is what I have so far. I am stuck on the last part (sorting); everything else works fine.

#include <iostream>

using namespace std;

int main(){
    
    int a[10];
    for (int i = 0; i < 10; i++) 
    {
        cout << "Enter a number\n ";
        cin >> a[i];
    }
    
    cout << "Array Reversed\n";
    for (int i = 9; i >= 0; i--)
    {
        cout << a[i] << " ";
    }
    
    cout << "Numbers from lowest to highest\n";
    for (int i = a[i]; i != 0; i = i/10 )
    {
        i % 10;
        cout << i << " ";
    }
    
}

This needs to have some kind of sort actually happening. Start by writing a `sort` function of some kind that takes an array and size pair of arguments, or better, a `std::vector` as you should do in C++. — tadman, Sep 17 '20 at 21:46
Is the goal here to *write a Bubble Sort function* or to just have them sorted? — tadman, Sep 17 '20 at 21:47
@cigien I guess this is a part of a homework assignment, thus, using `std::sort` isn't a valid solution. — Kerek, Sep 17 '20 at 21:49
@Kerek Maybe so, but OP hasn't indicated that. I's rather they know about `sort` first. If they can't use it, that's fine too. — cigien, Sep 17 '20 at 21:51
@tadman yes I was going for bubble sort but unfortunately, I am having to teach myself c++ luckily with some java knowledge and I am burnt out trying to research everything with the little I can find. I have been stuck on this for the past hour. My professor doesn't give us any notes, textbooks or lecture videos to help teach us — cyber_cloud, Sep 17 '20 at 21:52
The harsh truth is that most C++ courses, by virtue of their "professors", are absolute junk and are just something you need to survive without ending up too damaged. C++ is a fantastic yet extremely unforgiving language, it's not something you can intuitively figure out, so you'll need a good [reference book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to refer to when you need answers to questions like this. — tadman, Sep 17 '20 at 21:53
@Kerek yes in the assinment it says to try something like bubble sorting. I have watched a bunch of videos and looked up some examples and can't seem to tie it into this code — cyber_cloud, Sep 17 '20 at 21:54
Whenever you're faced with an algorithm problem check Wikipedia for a reference first. Like here [Bubble Sort](https://en.wikipedia.org/wiki/Bubble_sort) is explained with pseudo-code, something you can use as a start for your C++ version. — tadman, Sep 17 '20 at 21:54
@cyber_cloud *I am having to teach myself c++ luckily with some java knowledge* -- Pretend that Java does not exist when learning C++. If you use Java as a model in learning or writing C++, all you'll end up with are buggy programs, inefficient programs, or programs that look weird to a C++ programmer. — PaulMcKenzie, Sep 17 '20 at 21:57
The difference between an *ascending* sort and a *descending* sort is the comparison function between two elements. If your code for *ascending* sort works, copy it and then change the comparison operator. — Thomas Matthews, Sep 17 '20 at 21:58
@Thomas: I'm not sure a descending sort is needed here. The assignment calls for entry order, reverse entry order, and ascending order. — paxdiablo, Sep 17 '20 at 22:03
@PaulMcKenzie *or programs that look weird to a C++ programmer.* This may not matter. Odds are tragically high that the professor isn't a C++ programmer. — user4581301, Sep 17 '20 at 22:26

paxdiablo · Answer 1 · 2020-09-18T07:22:01.753

Assuming you need a bubble sort, the general idea is (pseudo-code):

# The array to sort.

arr = [3, 1, 4, 1, 5, 9]

# Initially assume sorting needs a pass.

hasSwapped = true
while hasSwapped:
    # If nothing swapped in this pass, we're done.

    hasSwapped = false

    # Check each element except last.

    for idx = 0 to arr.sz - 2 inclusive:
        # If bigger than next element, swap, flag another pass needed.

        if arr[idx] > arr[idx + 1]:
            temp = arr[idx]
            arr[idx] = arr[idx + 1]
            arr[idx + 1] = temp
            hasSwapped = true

You should hopefully be able to understand the intent from the comments but the basic idea is:

A single pass will check all elements and, if one is greater than the one after it, it will swap them.
You have to do at least one pass.
If a pass completes without a swap, the data is now sorted. Otherwise, more passes are needed.

Your job is now to convert that to the language of your choice.

I'll include an implementation below, with the function itself in C (though it will also work in C++, as evidenced by the surrounding test harness).

However, you would be unwise to assume educators don't perform plagiarism checks on assignments they give. In other words, don't use this code as-is, you'll almost certainly be caught out. Its intent is just to show you a possible implementation that you can compare your own code to:

#include <iostream>
using namespace std;

void bubbleSort(int *arr, size_t sz) {
    int hasSwapped = 1;
    while (hasSwapped) {
        hasSwapped = 0;
        for (size_t idx = 0; idx < sz - 1; ++idx) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx];
                arr[idx] = arr[idx + 1];
                arr[idx + 1] = temp;
                hasSwapped = 1;
            }
        }
    }
}

int main() {
    int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9 };

    for (size_t i = 0; i < sizeof(arr) / sizeof(*arr); ++i)
        cout << arr[i] << ' ';
    cout << '\n';

    bubbleSort(arr, sizeof(arr) / sizeof(*arr));

    for (size_t i = 0; i < sizeof(arr) / sizeof(*arr); ++i)
        cout << arr[i] << ' ';
    cout << '\n';

    return 0;
}

The output is, as expected:

3 1 4 1 5 9 2 6 5 3 5 9
1 1 2 3 3 4 5 5 5 6 9 9

How to implement bubble sort?

1 Answers1