Optimized Bubble Sort

[Carolpp]

can anyone help me to optimize this bubble sort program?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

int main()
{
long *A;
A = new long[100000000];
long i,j,temp,sizeofmyarray;
time_t t5, t6 ;

cout << "Please enter your array size: " << endl;
cin >> sizeofmyarray;

for(i=0; i< sizeofmyarray; i++)
{
A[i] = rand(); // Fill aray using random numbers
}
cout << " Bubble Sort Algorithm......";
cout << endl;
t5 = clock();


for(i=0;i<=(sizeofmyarray-2);i++)
{
for(j=0;j<(sizeofmyarray-2-i);j++)
if (A[j+1] < A[j])
{
temp = A[j+1];
A[j+1] = A[j];
A[j] = temp;
}
}
t6 = clock();
cout << "Time is: " << t6-t5;

cout << endl;
cout << " ";
cout << endl;
delete A;
system("pause");
return 0;
}

[Michaela Elise]

In here is the optimized bubble sort.

Think about it, every iteration of bubblesort places the sorted item in the leftmost/rightmost place. So why bother checking that again? Well, don't. It's all in the for loop

//Michaela Ervin - Sorting functions

#ifndef H_SORTFUNCS
#define H_SORTFUNCS

template <class dType>
void swapitem(dType& one, dType& two)
{
	dType d;
	d = one;
	one = two;
	two = d;
}

//Works with Arrays and Vectors
template <class dType>
void bubblesort(dType &temp, int n)
{
	bool sorted = false;
	int i = 0, j = 1;
	
	while (!sorted)
	{
		sorted = true;
		for (i = 0; i < n - j; i++)
		{
			if (temp[i] > temp[i + 1])
			{
				swapitem(temp[i], temp[i + 1]);
				sorted = false;
			}
		}
		j++;
	}
}

//Works with Arrays and Vectors
template <class dType>
void selectsort(dType &temp, int n)
{
	int j = 0, k = 0, small;

	if (n > 1)
		for (k = 0; k < n - 1; k++)
		{
			small = k;
			for (j = k + 1; j < n; j++)
				if (temp[j] < temp[small]) small = j;
			if (k != small)	swapitem(temp[k], temp[small]);
		}
}

//Works with Arrays - Change datatype of save to work with vectors
//Array must have one open slot on the end
template <class dType>
void insertionsort(dType &temp, int n)
{
	int j = 0, k = 0;
	dType save;

	for (k = n - 1; k >= 0; k--)
	{
		j = k + 1;
		save = temp[k];
		temp[n] = save;
		while (save > temp[j])
		{
			temp[j - 1] = temp[j];
			j++;
		}
		temp[j - 1] = save;
	}
}

//Works with Arrays and Vectors
template <class dType>
void quicksort(dType &temp, int left, int right) {

	int i = left, j = right;
	int pivot = temp[(left + right) / 2];
	while (i <= j) 
	{
		while (temp[i] < pivot)i++;
		while (temp[j] > pivot)j--;
        if (i <= j) 
		{
			swapitem(temp[i], temp[j]);
			i++;
			j--;
		}
	}
	if (left < j)quicksort(temp, left, j);
	if (i < right)quicksort(temp, i, right);
}

//Works with Arrays and Vectors
template <class dType>
void shellsort(dType &temp, int n)
{
	bool swap = false;
	int i, gap;

	gap = n;

	while (gap >= 1)
	{
		if (swap == false)
			gap = gap / 2;
		swap = false;
		for (i = 0; i < (n - gap); i++)
		{
			if (temp[i] > temp[i + gap])
			{
				swapitem(temp[i], temp[i + gap]);
				swap = true;
			}
		}
	}
}
#endif 

[zoran404]

I seriocely don't get the need to use sooooo much alocated memory, I mean that is almost 100 MB of RAM space.
You should have wrote

cin >> sizeofmyarray;
A = new long[sizeofmyarray];

And alocated array is deleted by delete[] A; - notice [] after delete

And your time variables are of tupe time_t (which is returned by function time()), while function clock() returns clock_t, which is much different in size.

And I think using loops like this mey help

for(i=sizeofmyarray-1;i>1;i--)
{
for(j=0;j<=i;j++)

Also you do "j+1" 3 times if the if statement returns true 1 time if it dosen't, so in worst case it would be way better to have 2 variables, j and j1, where j1 would always be equal to j+1, what would save a lot of time if the array is wery big.