Optimized Bubble Sort

[jhacob40]

Can someone help me to modify this bubblesort?


#include <iostream>
#include<conio.h>
using namespace std;
int main()
{
int size,x,y;

cout << "How many intergers you want to bubble sort?" << endl << "Ans:";
cin >> size;

int sort[size];

for(x = 0; x < size; x++)
{
cout << "Enter the [" << x+1 <<"] Integer: ";
cin >> sort[x];
}


for(x = 0; x < (size-1); x++)
{
for(y = (x+1); y < size; y++)
{
int temp;

if(sort[x] > sort[y])
{
temp = sort[x];
sort[x] = sort[y];
sort[y] = temp;
}
}
}

cout << "\n Your Input in Bubble Sort \n";
cout << "\n Display Bubble Sorting \n";
cout << " [ ";
for(x = 0; x < size; x++)
{
if(x < size - 1)
{
cout << sort[x] << " , " ;
}else
{
cout << sort[x] << " ]";
}
}

cin.get();
return 0;
}

[Thomas1965]

First you should get your input right.
You can't declare an array like this:

cout << "How many intergers you want to bubble sort?" << endl << "Ans:";
cin >> size;

int sort[size];

http://www.cplusplus.com/doc/tutorial/dynamic/

[dhayden]

I don't think there's much you can do to optimize this bubble sort. The only thing I can think of is to check whether you swap anything in the inner loop. If nothing gets swapped then you can exit.

The best optimization would be to choose a better algorithm.

[artganseforth]

I'm not sure, but one way might be this:

Presumend you want to sort MAX items, at first you need one standard-counter:
for(int i1=0; i1<MAX; i1++)

Now the fastest way to find the insertation-index i2 for element i1 is something like the following (not tested - only theory):

int ofs = (int)((MAX-i1))/2;
int i2=i1+ofs;
while (ofs < 1) {
  ofs=(int)ofs/2;
  if (element[i2]<element[i1]) i2=i2-ofs; else i2=i2+ofs;
}

Regards,
F.

[dhayden]

Artganseforth, that's a good idea, but it isn't bubble sort. You're describing insertion sort.

[ne555]

the best way to optimise bubble sort is to drop it and use another algorithm.