(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
A Generic bubble sort
#include <iostream>
using namespace std;
template <class X> void bubble(X *items,int count)
{
X t;
for(int a=1; a<count; a++)
for(int b=count-1; b>=a; b--)
if(items[b-1] > items[b]) {
t = items[b-1];
items[b-1] = items[b];
items[b] = t;
}
}
int main()
{
int iarray[7] = {7, 5, 4, 3, 9, 8, 6};
double darray[5] = {4.3, 2.5, -0.9, 10.2, 3.0};
cout << "Here is unsorted integer array: ";
for(int i=0; i<7; i++)
cout << iarray[i] << " ";
cout << endl;
bubble(iarray, 7);
cout << "Here is sorted integer array: ";
for(int i=0; i<7; i++)
cout << iarray[i] << " ";
cout << endl;
cout << "Here is unsorted double array: ";
for(int i=0; i<5; i++)
cout << darray[i] << " ";
cout << endl;
bubble(darray, 5);
cout << "Here is sorted double array: ";
for(int i=0; i<5; i++)
cout << darray[i] << " ";
cout << endl;
return 0;
}Here is unsorted integer array: 7 5 4 3 9 8 6
Here is sorted integer array: 3 4 5 6 7 8 9
Here is unsorted double array: 4.3 2.5 -0.9 10.2 3
Here is sorted double array: -0.9 2.5 3 4.3 10.2
Generic quick sort
#include<iostream.h>
#include<iomanip.h>
#include<cstdlib>
template<class T>
inline void swap(T& v1,T& v2)
{
T temp=v2;
v2=v1;
v1=temp;
}
template<class T>
void quicksort(T *array,int hi,int lo=0)
{
while(hi>lo)
{
int i=lo;
int j=hi;
do
{
while(array[i]<array[lo]&&i<j)
i++;
while(array[--j]>array[lo])
;
if(i<j)
swap(array[i],array[j]);
}while(i<j);
swap(array[lo],array[j]);
if(j-lo>hi-(j+1)) {
quicksort(array,j-1,lo);
lo=j+1;
}else{
quicksort(array,hi,j+1);
hi=j-1;
}
}
}
int main()
{
int dim = 100;
int *arrs=new int[dim+1];
for(int i=0;i < dim;i++)
arrs[i]=rand();
cout << endl<<"unsorted"<<endl;
for(int i=0;i<dim;i++)
cout<<setw(8)<<arrs[i];
quicksort(arrs,dim);
cout<<endl<<"sorted"<<endl;
for(int i=0;i<dim;i++)
cout<<setw(8)<<arrs[i];
delete arrs;
return 0;
}unsorted
41 18467 6334 26500 19169 15724 11478 29358 26962 24464
5705 28145 23281 16827 9961 491 2995 11942 4827 5436
32391 14604 3902 153 292 12382 17421 18716 19718 19895
5447 21726 14771 11538 1869 19912 25667 26299 17035 9894
28703 23811 31322 30333 17673 4664 15141 7711 28253 6868
25547 27644 32662 32757 20037 12859 8723 9741 27529 778
12316 3035 22190 1842 288 30106 9040 8942 19264 22648
27446 23805 15890 6729 24370 15350 15006 31101 24393 3548
19629 12623 24084 19954 18756 11840 4966 7376 13931 26308
16944 32439 24626 11323 5537 21538 16118 2082 22929 16541
sorted
41 153 288 292 491 778 1842 1869 2082 2995
3035 3548 3902 4664 4827 4966 5436 5447 5537 5705
6334 6729 6868 7376 7711 8723 8942 9040 9741 9894
9961 11323 11478 11538 11840 11942 12316 12382 12623 12859
13931 14604 14771 15006 15141 15350 15724 15890 16118 16541
16827 16944 17035 17421 17673 18467 18716 18756 19169 19264
19629 19718 19895 19912 19954 20037 21538 21726 22190 22648
22929 23281 23805 23811 24084 24370 24393 24464 24626 25547
25667 26299 26308 26500 26962 27446 27529 27644 28145 28253
28703 29358 30106 30333 31101 31322 32391 32439 32662 32757
