Алгоритмы пузырьковой сортировки Опции

[Account]

Итак, все знают что есть такой вид сортировки, как пузырьковая. Меня интересует какие еще есть алгоритмы в этом виде сортировки кроме: последовательного и чет-нечетной перестановки? И если есть информация о них поделиться ей, если не жалко.

[Account]

IUnknown, велосипед не придумывал выдернул код представленный с первой твоей ссылки))), но он оказался медленнее представленного тобой по последней ссылке.Походу по первой не совсем верный алгоритм.

Вот прога целиком

#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;
        }
    }
}

еще надо будет добавить чет-нечет
Дальше дело за малым, прогон на проверку каждого алгоритма.

Сообщение отредактировано: Account - 23.06.2011 22:51