Thread: Sort library

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    24

    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.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    24
    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).

  4. #4
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    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.
    Last edited by siavoshkc; 08-22-2006 at 03:44 PM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    Last edited by anon; 08-22-2006 at 03:57 PM.

  6. #6
    Registered User
    Join Date
    Dec 2005
    Posts
    24
    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.

  7. #7
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    Turning on optimization for final release is regular.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Difficulty choosing graphics library
    By jdiperla in forum Game Programming
    Replies: 11
    Last Post: 02-27-2008, 06:35 PM
  2. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  3. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM
  4. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  5. Sorting an array of structures with sort()
    By rmullen3 in forum C++ Programming
    Replies: 3
    Last Post: 01-03-2003, 03:02 PM