Sort library

Hi, I was thinking of making a library of different types of sorts(as I had discovered that I could make my own libraries),but I ran into a problem with the
bubble sort. If I write bubble sort directly in the code, it runs in about 1.59secs
but if it is written as a function it runs in 1.98secs. Could someone help me keep the runtime down? (How does the qsort() keep runtime down?)

This is my code:

Code:

#include<algorithm>
#include<cstdio>
#include<iostream>

#ifndef SORT_H
#define SORT_H
void bsort(int L,int *ptr)
{
    bool changed=0;
    int D_C=L-1;
    	for(int x=0; x<L; x++)
    	{
    		for(int y=0; y<D_C; y++)
    		{
    			if(ptr[y]>ptr[y+1])
    			{
    				int temp = ptr[y+1];
    				ptr[y+1] = ptr[y];
    				ptr[y] = temp;
    				changed=1;
    			}
    		}
    		if(!changed) break;
    		D_C--;
    	}
}
#endif

Thank you.

Bubble-sort is not very effective and it's very slow with large arrays. If it's that slow you can't make it much faster.

However, here your loops are not quite optimum. Think about it, first time through the inner loop the largest element gets "pushed" to the end of the array. Second time - second largest etc. This way the end of the array gets sorted before and it means y really must not go to the end of the array each time (you could decrease the end condition by one each time through the outer loop).

Another optimisation would be to check if any swaps actually occurred and break out earlier if the array is already sorted. This way, bubble-sort could even beat quicksort on an already sorted array

I think I my is optimized. It loops while the there is change (if(!changed) break and it doesn't check already sorted elements (D_C--). I'm more concerned with why converting the bubble sort into a function makes the runtime so much longer. If it were impremented directly on an array (of 10000elements produced by rand()), it works 1.25 times faster. Why does it go so slow? Can I change this? (Yes I want to use bubble sort. I know other sorts but some problems are easier using bubble sort).

Function calling has overhead, you can make your functions inline to overcome this problem.

Standard library functions are highly optimized and some parts of them has been written in assembly.

[edit]
Make sure you turn on all compiler optimizations before testing functions time.

I'm sorry, I didn't read your code too carefully. You are absolutely right.

As to the speed difference, I don't know. The function is working practically directly on the array too? Are you sure you tested with exactly the same set of data? Did you test multiple times (may-be your computer was busy doing something else at the same time)?

Anyway, qsort is much quicker basically because it does a whole lot less comparisons and a whole lot less swaps.

In bubble-sort, let's suppose the first member is the largest: it takes size-1 swaps to get it to the right place. In qsort, it is swapped into the second half of the array (approximately the right place ) in just one swap (iteration).

--------------------

I recently implemented merge sort, if you are interested. The good thing about it is that most work is done by STL inplace_merge algorithm

Code:

//a - array to be sorted
//begin - index of first element of the range
//end - one past end of the range
template <typename T>
void MergeSort(T* a, int begin, int end)
{
    int middle = (begin+end)/2;
    if (begin+1 < middle) MergeSort(a, begin, middle);
    if (middle+1 < end) MergeSort(a, middle, end);
    std::inplace_merge(a+begin, a+middle, a+end); //#include <algorithm>
}

[edit] One thing you could do: you got to set changed to false each time through the outer loop. And may-be you could initialize changed to true, and replace the outer for loop with while (changed) to avoid an additional check for if (!changed).

Wow I didn't know that you could optimize your compiler! My program runs in 0.55secs now! Do you know if training sites like acm and usaco do this as well? Thanks a bunch.

Turning on optimization for final release is regular.

>I know other sorts but some problems are easier using bubble sort
What problems? The ones I know of where bubble sort is a good choice are either impractical or improbable.