void combsort( double *pData, int DataSize )
{ double tmp;

  int jump = DataSize;
  bool swapped = true;

  while (jump > 0 || swapped)
  {
    if (jump > 0)
      jump = (jump / 1.25);
    swapped = false;
    for (int i = 0; i + jump < DataSize-1; i++)
      if(pData[i] > pData[i + 1]) {
        tmp          = pData[i];
        pData[i]     = pData[i + 1];
        pData[i + 1] = tmp;swapped = true;}

  }
} 

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;
void RandomDataInitialization(double *&pData, int& DataSize) ;
void ProcessInitialization(double *&pData, int& DataSize) ;
void ProcessTermination(double *pData);
void DummyDataInitialization(double*& pData, int& DataSize);
void Shaker(double *pData, int DataSize);
void combsort( double *pData, int DataSize );
void PrintData(double *pData, int DataSize);
const double RandomDataMultiplier = 1000.0;

int main(int argc, char *argv[]) {
  double *pData = 0;
  int DataSize = 0;

  time_t start, finish;
  double duration = 0.0;

  printf("Serial bubble sort program\n");

  // Process initialization // В этой функции можно менять вид заполнения  массива
  ProcessInitialization(pData, DataSize);

  //printf("Data before sorting\n"); 
  //PrintData(pData, DataSize); // Для проверки исходных данных

  // Serial bubble sort // Виды сортировки, обычная пузырьковая, расческой, Шейкера активация на выбор
  start = clock();
  SerialBubble(pData, DataSize);
  //combsort(pData, DataSize);
  //Shaker(pData, DataSize);
  finish = clock();

  //printf("Data after sorting\n");
  //PrintData(pData, DataSize); //Для проверки результата 

  duration = (finish - start) / double(CLOCKS_PER_SEC);
  printf("Time of execution: %f\n", duration);

  // Process termination
  ProcessTermination(pData);

  return 0;
}

// Function for allocating the memory and setting the initial values
void ProcessInitialization(double *&pData, int& DataSize) {
  do {
    printf("Enter the size of data to be sorted: ");
    scanf("%d", &DataSize);
    if(DataSize <= 0)
      printf("Data size should be greater than zero\n");
  }
  while(DataSize <= 0);

  printf("Sorting %d data items\n", DataSize);

  pData = new double[DataSize];

  // Simple setting the data
  //DummyDataInitialization(pData, DataSize);

  // Setting the data by the random generator
  RandomDataInitialization(pData, DataSize);
}

// Function for computational process termination
void ProcessTermination(double *pData) {
  delete []pData;
}

// Function for simple setting the initial data
void DummyDataInitialization(double*& pData, int& DataSize) {
  for(int i = 0; i < DataSize; i++)
    pData[i] = DataSize - i;
}

// Function for initializing the data by the random generator
void RandomDataInitialization(double *&pData, int& DataSize) {
  srand( (unsigned)time(0) );

  for(int i = 0; i < DataSize; i++)
    pData[i] = double(rand()) / RAND_MAX * RandomDataMultiplier;
}

// Serial bubble sort algorithm
void SerialBubble(double *pData, int DataSize) {
  double Tmp;

  for(int i = 1; i < DataSize; i++)
    for(int j = 0; j < DataSize - i; j++)
      if(pData[j] > pData[j + 1]) {
        Tmp          = pData[j];
        pData[j]     = pData[j + 1];
        pData[j + 1] = Tmp;
      }
}

void PrintData(double *pData, int DataSize) {
  for(int i = 0; i < DataSize; i++)
    printf("%7.4f ", pData[i]);
  printf("\n");
}

void Shaker(double *pData, int DataSize){
  double t;
  bool exchange;

  do {
    exchange = false;
    for(int i=DataSize-1; i > 0; --i) {
      if(pData[i-1] > pData[i]) {
        t = pData[i-1];
        pData[i-1] = pData[i];
        pData[i] = t;
        exchange = true;
      }
    }
    for(int i=1; i < DataSize; ++i) {
      if(pData[i-1] > pData[i]) {
        t = pData[i-1];
        pData[i-1] = pData[i];
        pData[i] = t;
        exchange = true;
      }
    }
  } while(exchange);

}

void combsort(double *pData, int DataSize) {
    float shrink_factor = 1.247330950103979;
    int gap = DataSize, swapped = 1, i; double swap;

    while ((gap > 1) || swapped) {
        if (gap > 1)
           gap = gap / shrink_factor;

        swapped = 0;
        i = 0;

        while ((gap + i) < DataSize) {
            if (pData[i] - pData[i + gap] > 0) {
                swap = pData[i];
                pData[i] = pData[i + gap];
                pData[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

/* This is the CompareSplit function */ 
 74  CompareSplit(int nlocal, int *elmnts, int *relmnts, int *wspace, 
 75               int keepsmall) 
 76  { 
 77    int i, j, k; 
 78 
 79    for (i=0; i<nlocal; i++) 
 80      wspace[i] = elmnts[i]; /* Copy the elmnts array into the wspace array */ 
 81 
 82    if (keepsmall) { /* Keep the nlocal smaller elements */ 
 83      for (i=j=k=0; k<nlocal; k++) { 
 84        if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j])) //<------Не въеду что то, как в словах это правильно озвучить
 85          elmnts[k] = wspace[i++]; 
 86        else 
 87          elmnts[k] = relmnts[j++]; 
 88      } 
 89    } 
 90    else { /* Keep the nlocal larger elements */ 
 91      for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) { 
 92        if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j])) //<--------------Естественно здесь тоже
 93          elmnts[k] = wspace[i--]; 
 94        else 
 95          elmnts[k] = relmnts[j--]; 
 96      } 
 97    } 
 98  } 

     if (keepsmall) { /* Keep the nlocal smaller elements */ 

          // Этот кусок упорядочивает в массив elmnts минимальные значения из elmnts и
          // relmnts (которые получены от соседнего процесса) по возрастанию
          // (сколько поместится в elmnts) Скажем, если было:
          // elmnts = (27  39  54  74  90)
          // relmnts = (22  38  50  65  69)
          // то после выполнения нижеследующего куска кода
          // elmnts = (22  27  38  39  50)

          for (i=j=k=0; k<nlocal; k++) { 
               if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j])) 
                    elmnts[k] = wspace[i++]; 
               else 
                    elmnts[k] = relmnts[j++]; 
          }
     } 
     else { /* Keep the nlocal larger elements */ 
          // Соответственно, этот кусок делает то же самое, но сохраняет nlocal максимальных
          // элементов из совокупности elmnts и relmnts. Т.е., если
          // elmnts = (16  18  47  62  70)
          // relmnts = ( 1  13  23  29  92), то в результате
          // elmnts = (29  47  62  70  92)
          // в упорядоченном виде
          for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) { 
               if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j]))
                    elmnts[k] = wspace[i--]; 
               else 
                    elmnts[k] = relmnts[j--]; 
          } 
     }

Цитата(IUnknown @ 27.06.2011 14:38)

     if (keepsmall) { /* Keep the nlocal smaller elements */ 

          // Этот кусок упорядочивает в массив elmnts минимальные значения из elmnts и
          // relmnts (которые получены от соседнего процесса) по возрастанию
          // (сколько поместится в elmnts) Скажем, если было:
          // elmnts = (27  39  54  74  90)
          // relmnts = (22  38  50  65  69)
          // то после выполнения нижеследующего куска кода
          // elmnts = (22  27  38  39  50)

          for (i=j=k=0; k<nlocal; k++) { 
               if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j])) 
                    elmnts[k] = wspace[i++]; 
               else 
                    elmnts[k] = relmnts[j++]; 
          }
     } 
     else { /* Keep the nlocal larger elements */ 
          // Соответственно, этот кусок делает то же самое, но сохраняет nlocal максимальных
          // элементов из совокупности elmnts и relmnts. Т.е., если
          // elmnts = (16  18  47  62  70)
          // relmnts = ( 1  13  23  29  92), то в результате
          // elmnts = (29  47  62  70  92)
          // в упорядоченном виде
          for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) { 
               if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j]))
                    elmnts[k] = wspace[i--]; 
               else 
                    elmnts[k] = relmnts[j--]; 
          } 
     }

wspace[i--]//<---совокупность и elmnts и relmnts

   Array_Size : constant Integer := Total_Elements / Processes_Count;

   type Int_Array is array (Natural range <>) of Integer;
   subtype Sub_Array is Int_Array(0 .. Array_Size - 1);

   -- ...

   task body Sorter is
      A : Int_Array(0 .. 2 * Array_Size - 1);
   begin
      accept Data (velmnts : Sub_Array; vrelmnts : Sub_Array) do
         A(0 .. Array_Size - 1) := velmnts;  -- Особенно интересует это ...
         A(Array_Size .. 2 * Array_Size - 1) := vrelmnts;  -- вот это ...
      end Data;

      if Keep_Small then  --  Это дискриминант задачи ...
         Sort(A);
      else
         Rev_Sort(A);
      end if;

      accept Request (Arr : out Sub_Array) do
         Arr := A(0 .. Array_Size - 1);  -- ... и вот это ...
      end Request;
   end Sorter;

qsort(elmnts, nlocal, sizeof(int), IncOrder); 

for (i=0; i<npes-1; i++) { 
 58	  if (i%2 == 1) /* Odd phase */ 
 59		MPI_Sendrecv(elmnts, nlocal, MPI_INT, oddrank, 1, relmnts, 
 60			nlocal, MPI_INT, oddrank, 1, MPI_COMM_WORLD, &status); 
 61	  else /* Even phase */ 
 62		MPI_Sendrecv(elmnts, nlocal, MPI_INT, evenrank, 1, relmnts, 
 63			nlocal, MPI_INT, evenrank, 1, MPI_COMM_WORLD, &status);