// $Id: sort.h,v 1.1.1.1 2000/11/02 08:47:17 fritzi Exp $

// This file is part of the DEAL Library
// DEAL is Copyright(1995) by
// Roland Becker, Guido Kanschat, Franz-Theo Suttmeier


#ifndef __sort_h
#define __sort_h

//////////
template<class T>
inline void swap(T* a, T* b)
{
  T x = *a;
  *a = *b;
  *b = x;
}

//////////
template<class T>
inline void simple_sort(long n, T* field)
{
  long i,j;
  for (i=1;i<n;i++)
  {
    for (j=i+1;j<=n;j++)
    {
      if (field[j] < field[i])
      {
	swap(field+i,field+j);
      }
    }
  }
}

template<class T>
inline void heapsort_sift(T* a, long l, long r)
{
  long i = l;
  long j = 2*i;
  T    x = a[i];

  while (j<=r)
  {
    if (j<r) 
    {
      if (a[j] < a[j+1]) j++;
    }
    if (!(x < a[j])) break;
    a[i] = a[j];
    i = j;
    j = 2*i;
  }
  a[i] = x;
}


//////////
template<class T>
inline void heapsort(int n, T* field)
{
  field--;

  long l =(n/2)+1;
  long r = n;

  while (l>1)
  {
    l--;
    heapsort_sift(field,l,r);
  }
  while (r>1)
  {
    swap(field+l,field+r);
    r--;
    heapsort_sift(field,l,r);
  }
}

//////////
template<class T>
inline void quicksort(long r, T* a, long l = 1)
{
  long i = l;
  long j = r;
  T*   x = &a[(l+r)/2];
  do
  {
    while (a[i] < *x) i++;
    while (*x < a[j]) j--;
    if (i<=j)
    {
      swap(a+i,a+j);
      i++;
      j--;
    }
  }
  while (i<=j);
  if (l<j) quicksort(j,a,l);
  if (i<r) quicksort(r,a,i);
}

#endif