sort algorithms mix

This is a discussion on sort algorithms mix within the C++ Programming forums, part of the General Programming Boards category; I'm writing Sort class with implementation of sort algorithms quick sort and bubble_sort I'm trying to mix sort algorithms to ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    sort algorithms mix

    I'm writing Sort class with implementation of sort algorithms quick sort and bubble_sort
    I'm trying to mix sort algorithms to reduce number of recursion and still maintain performance.
    My problem is that I don't know what criteria to choose.
    What do you think about this:
    Code:
    #include <iostream>
    using namespace std;
    template <class T>
    void Show(T arr[],int len,char *s)
    {
    	cout<< s;
    	for(int i=0;i<len;i++)
    		cout<<arr[i]<<" ";
    	cout<<endl;
    }
    
    int bubble=0,quick=0;
    template <class T>
    class Sort
    {
    	T *array;
    	int length;
    	void load_list(T []);
    public:
    	Sort(int siz):length(siz)
    	{ 
    		array=new T[length];
    	}
    	~Sort(){delete [] array;array=NULL;}
    	void bubble_sort(T []);
    	void quick_sort(T[],int,int,bool=true);
    	void swap(T&,T&);
    	void show_list(const char *);
    };
    template <class T>
    void Sort<T>::load_list(T list[])
    {
    	for(int i=0;i<length;i++)
    	{
    		array[i]=list[i];
    	}
    }
    template <class T>
    void Sort<T>::bubble_sort(T list[])
    {
    	int flag_swap=1;bubble++;
    	load_list(list);
    	Show(array,length,"U toku Bubble!");
    	for(int i=0;i<(length-1) && flag_swap;i++)
    	{
    		flag_swap=0;
    		for(int j=0;j<(length-(i+1));j++)
    			if(array[j]>array[j+1])
    			{
    				swap(array[j],array[j+1]);
    				flag_swap=1;
    			}	
    	}
    
    }
    
    template <class T>
    void Sort<T>::quick_sort(T list[],int first,int last,bool t)
    {
    	if(t)
    	{	
    		load_list(list);
    		t=false;
    	}
    	if(first<last-5)//this is supposed to reduce recursion
    			//if one of the two subarrays 
    //have less then 6 elements
    			//probably there is clever solution to this
    			//I would appreciate your help
    	{
    		int pivot=array[first];
    		int i=first;
    		int j=last;quick++;
    		Show(array,length,"U toku quick");
    		while(i<j)
    		{
    			while(array[i]<=pivot && i<last)
    				i++;
    			while(array[j]>=pivot && j>first)
    				j--;
    			if(i<j)
    				swap(array[i],array[j]);
    
    		}
    		swap(array[j],array[first]);
    		quick_sort(list,first,j-1,t);
    		quick_sort(list,j+1,last,t);
    
    	}
    	else
    		bubble_sort(array);
    }
    template <class T>
    void Sort<T>::show_list(const char *s)
    {
    	cout<<s<<endl;
    	for(int i=0;i<length;i++)
    		cout<<array[i]<<" ";
    	cout<<endl;
    
    }
    template <class T>
    void Sort<T>::swap(T& x,T& y)
    {
    	T tmp;
    	tmp=x;
    	x=y;
    	y=tmp;
    }
    
    int main()
    {
    	
    	Sort<int> b(20);
    	int array[20]={87,4,2,78,4,2,6,1,56,98,24,56,78,12,1,2,4,5,81,76};
    	
    	b.quick_sort(array,0,19);
    	b.show_list("Sorted:");
    	cout<<"quick sort "<<quick<<endl;
    	cout<<"buuble sort "<<bubble<<endl;
    
    	return 0;
    }
    One of the advantages of bubble sort is good performnace when dealing with almost sorted
    lists or arrays. So how can I set condition to choose between bubble and quick sort?
    Thanks

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >One of the advantages of bubble sort is good performnace when dealing with almost sorted lists or arrays.
    Yes, but insertion sort has the same feature and is considerably faster than bubble sort (except in exceedingly rare cases) despite also being a quadratic algorithm.

    >So how can I set condition to choose between bubble and quick sort?
    Find the cutoff amount of data where quicksort begins to outperform bubble sort. This will typically be a small amount, say less than 5000 small items and less than 1000 large items.
    My best code is written with the delete key.

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    That's ok for general case.
    I'm interesting for this concrete example .
    Is condition test
    if(first<last-5)//this is supposed to reduce recursion

    good way of reducing recursion.
    when testing this example
    I have for example quick,quickquick,bubble,quick,quick,bubble,bubble. ..
    so sometimes one is called, and sometime other.
    Do you have any other suggestion then if(first<last-5)//

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    If your only goal is to reduce recursive calls while still maintaining performance, write a non-recursive quicksort. It certainly minimizes recursive calls, and will usually perform better than a recursive implementation. Mixing bubble sort and quicksort will be a performance hit because bubble sort sucks so much.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. mix mode and processing the mix mode
    By stanlvw in forum Windows Programming
    Replies: 3
    Last Post: 07-24-2008, 02:50 PM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 05:03 AM
  3. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 05:03 AM
  4. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 12:27 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21