C++ Tutorial/template/generic sort

Материал из C\C++ эксперт
Перейти к: навигация, поиск

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