Tools/Math/Permutation.cpp

Go to the documentation of this file.

/**
* @file Math/Permutation.cpp
* Implemets class Permutation
*
* @author <A href=mailto:sebastian.schmidt@udo.edu>Sebastian Schmidt</A>
*/

#include "Permutation.h"

bool Permutation::perm(int data[], const int& length) {
  int i = length;
  int max = -1;
  int posMax = -1;
  bool found = false;
  do {
    if ((max > data[--i]) && (posMax != -1)) {
      found = true;
    } else {
      max = data[i];
      posMax = i;
    }
  } while ((!found) && (i > 0));
  if (!found) {
    return false;
  }
  int posMin = posMax;
  int min = max;;
  for(int a=i+1; a<length; a++) {
    if ((data[a] < min) && (data[a] > data[i])) {
      posMin = a;
      min = data[a];
    }
  }
  data[posMin] = data[i];
  data[i] = min;
  sort(data, i+1, length-1);
  return true;
}

void Permutation::sort(int data[], const int& start, const int& end) {
  if (start == end) {
    return;
  }
  int pivot = data[(start+end)/2];
  int left = start;
  int right = end;
  do {
    while (data[left] < pivot) {
      left++;
    }
    while (data[right] > pivot) {
      right--;
    }
    if (left < right) {
      int tmp = data[left];
      data[left] = data[right];
      data[right] = tmp;
    }
    if (left <= right) {
      left++;
      right--;
    }
  } while (left <= right);
  if (start < right) {
    sort(data, start, right);
  }
  if (end > left) {
    sort(data, left, end);
  }
}

/*
* Change log :
*
* $Log: Permutation.cpp,v $
* Revision 1.1.1.1  2004/05/22 17:37:13  cvsadm
* created new repository GT2004_WM
*
* Revision 1.1  2003/10/07 10:13:24  cvsadm
* Created GT2004 (M.J.)
*
* Revision 1.1.1.1  2003/07/02 09:40:28  cvsadm
* created new repository for the competitions in Padova from the 
* tamara CVS (Tuesday 2:00 pm)
*
* removed unused solutions
*
* Revision 1.2  2003/03/12 14:47:58  schmidt
* Removed a warning.
*
* Revision 1.1  2003/02/27 10:07:00  schmidt
* Added three variants of a SensorFusionPlayersLocator.
*
*
*
*/

---