Geek asks and answers

Why does Bubble Sort require nested loops?

Ok I am going to start a new question. I asked a question yesterday and wanted to know what the problem is in my program. The program is shown below, and you indicated that this next program performs only one sorting pass and needs an external loop. At that time I was fine as well. But then again, when I watched the program, I was embarrassed and I had to ask why we needed an Outer loop for sorting, since only one loop could sort (in my opinion). First look at the program below, after which 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. Take a look at the following program loop:

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

}

, , . [0] [1]. , , IF. 1 (i ++). [1] [2]. , ? , , , IF for? -, . , , . .

+5
4

, 3 . ,

13, 3 ,1

, . 13 3 13 > 3, . .

3, 13, 1

, , = 13 1 13 > 1,

3, 1, 13

, 3 1 !

+13

(-)

. , , - Omega(nlogn). , O(1) (, 1) - 1,2.

5, 4, 3, 2, 1

:

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

, : [ 4, 3, 2, 1, 5], .

( ). , n - , , n, .

(1) ( , ) - .
(2) , .

+10

. n-1 , , . 1

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;

}

, IF , , 9 IFs largets

+2

,

"" . (Bubble sort)

, . , n . ( n = )

+1

More articles:


All Articles