Why Bubble Sort needs nested loops?

Question

I am going to start the new question. I posed the question yesterday and wanted to know what's the problem in my program. The program is given below and you people pointed out that this following program does only one pass of the sorting and needs an outer loop as well. At that time I was good like OK. But again when I looked the program I got confused and need to ask Why we need Outer loop as well for the sort since only a single loop can do the sorting(In my opinion). First see program below then I present my logic at the end of the program.

#include <iostream.h>
#include <conio.h>

using namespace std;

main()
{

    int number[10];
    int temp = 0;
    int i = 0;

    cout << "Please enter any ten numbers to sort one by one: "
         << "\n";

    for (i = 0; i < 10; i++)
    {
        cin >> number[i];
    }

    i = 0;

    for (i = 0; i < 9; i++)
    {

        if (number[i] > number[i + 1])
        {
            temp = number[i + 1];
            number[i + 1] = number[i];
            number[i] = temp;
        }
    }
    i = 0;
    cout << "The sorted numbers are given below:"
         << "\n";

    for (i = 0; i < 10; i++)
    {
        cout << number[i] << "\n";
    }

    getch();
}

I think the ONLY loop with the bubble condition should do the sorting. Look at the following loop of the program:

for (i=0;i<9;i++)
if(number[i]>number[i+1])
{
    temp=number[i+1];
    number[i+1]=number[i];
    number[i]=temp;

}

Now I explain what I am thinking what this loop "should" do. It will first compare number[0] with number[1]. If the condition is satisfied it will do what is in IF statement's body. Then i will be incremented by 1(i++). Then on next iteration the values compared will be number[1] with number[2]. Then why it does not happen and the loop exits after only pass? In other words may be I'm trying to ask IF statement does not repeat itself in for loop? In my opinion it does. I'm very thankful for help and views, my question might be of small level but that is how I will progress.

Answer 1

Let me give you an example let's only take 3 numbers. So you input

13, 3 ,1 

Now you start sorting how you did it. so it compares 13 and 3 13 > 3 so switch both of them. now we have.

3, 13, 1

Now it'll compare as you said the next pair = 13 and 1 13 > 1 so the new order would be

3, 1, 13

now your loop is finished and you missed to compare 3 and 1 Actually the first loop only sorts the greatest number!

Answer 2

since only a single loop can do the sorting(In my opinion)

This is not correct. Without getting to details, a constant number of loops is not enough to sort, since sorting is Omega(nlogn) problem. Meaning, an O(1) (constant, including 1) number of loops is not enough for it - for any algorithm^1,2.

Consider the input

5, 4, 3, 2, 1 

a single loop of bubble sort will do:

4, 5, 3, 2, 1
4, 3, 5, 2, 1 
4, 3, 2, 5, 1
4, 3, 2, 1, 5

So the algorithm will end up with the array: [ 4, 3, 2, 1, 5], which is NOT sorted.

After one loop of bubble sort, you are only guaranteed to have the last element in place (which indeed happens in the example). The second iteration will make sure the 2 last elements are in place, and the nth iteration will make sure the array is indeed sorted, resulting in n loops, which is achieved via a nested loop.

---

(1) The outer loop is sometimes hidden as a recursive call (quick sort is an example where it happens) - but there is still a loop.
(2) Comparisons based algorithms, to be exact.

Answer 3

For bubble sorting a pass simply moves the largest element to the end of array. So you need n-1 passes to get a sorted array, thats why you need other loop. Now for your code 1 pass means

if(number[0]>number[0+1])
{
    temp=number[0+1];
    number[0+1]=number[0];
    number[0]=temp;

}
if(number[1]>number[1+1])
{
    temp=number[1+1];
    number[1+1]=number[1];
    number[1]=temp;

}
.....6 more times
if(number[8]>number[8+1])
{
    temp=number[8+1];
    number[8+1]=number[8];
    number[8]=temp;

}

so as you can see IF statement repeats itself, its just that after all 9 IFs the largets element moves to the end of array