-
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
-
>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.
-
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)//
-
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.