Cайт Алексея и Александра Друцы — программирование, ИТ, математика
Турнирная сортировка (сортировка кучей / пирамидальная сортировка)

Исходник на языке Си турнирной сортировки (сортировка кучей / пирамидальная сортировка) массива.

Идея сортировки заключается в построении сортирующего дерева (пирамиды), далее из дерева выбирается наибольший элемент, который затем кладётся в конец массива.

Для любого варианта заполнения массива сложность алгоритма (количество операций) составляет O(n·log(n)), где n — длина массива.

Алгоритм сортировки реализован в виде отдельной функции, сортирующей массив чисел, переданный через её аргумент. Это позволяет переиспользовать наш исходный код без каких-либо изменений. В приведенном ниже коде программы показан пример использования функции турнирной (пирамидальной) сортировки массива HeapSort.

Листинг файла heap_sort.c
#include "stdio.h"
#include "stdlib.h"

int ReadArray(double **, int *);
int WriteArray(double *, int *);

int Left(int);
int Right(int);
int HeapIfy(double *, int, int);
int BuildHeap(double *, int, int *);
int HeapSort(double *, int);

int main()
{
   double *Array;
   int ArraySize=0;
   if(ReadArray(&Array, &ArraySize)>0) return 2;
   HeapSort(Array, ArraySize);
   if(WriteArray(Array, &ArraySize)>0) return 3;
   return 1;
}

int ReadArray(double **Array, int *ArraySize)
{
   FILE * fin=NULL;   
   fin=fopen("in.txt", "r");      
   if(!fin)
   {
      printf("Can't open in.txt\n");
      return 1;
   }
   if(fscanf(fin, "%d", ArraySize)!=1)
   {
      printf("Can't read integer from file\n");
      return 2;
   }   
   (*Array)=(double*)malloc(sizeof(double)*(*ArraySize));
   for(int i=0; i<*ArraySize; i++)
   {
      if (fscanf(fin, "%lg", &((*Array)[i]))!=1)
      {
         printf("Can't read array Element with number %d from file\n", i);
         return 3+i;
      }
   }
   return 0;
}

int WriteArray(double *Array, int *ArraySize)
{
   FILE * fout=NULL;
   fout=fopen("out.txt", "w");
   if(!fout)
   {
      printf("Can't open out.txt\n");
      return 1;
   }
   fprintf(fout, "%d ", *ArraySize);   
   for(int i=0; i<*ArraySize; i++)
   {
      fprintf(fout, "%lg ", Array[i]);      
   }
   return 0;
}

int Left(int iCurIndex)
{
   return iCurIndex<<1;
}

int Right(int iCurIndex)
{
   return (iCurIndex<<1)|1;
}

int HeapIfy(double *Array, int iCurIndex, int iHeapSize)
{
   int iAdditV1, iAdditV2, iLargest;
   double iTmpV;
   iAdditV1=Left(iCurIndex);
   iAdditV2=Right(iCurIndex);
   if((iAdditV1<=iHeapSize)&&(Array[iAdditV1-1]>Array[iCurIndex-1]))
   {
      iLargest=iAdditV1;
   }else
   {
      iLargest=iCurIndex;
   }
   if((iAdditV2<=iHeapSize)&&(Array[iAdditV2-1]>Array[iLargest-1]))
   {
      iLargest=iAdditV2;
   }
   if(iLargest!=iCurIndex)
   {
      iTmpV=Array[iCurIndex-1];
      Array[iCurIndex-1]=Array[iLargest-1];
      Array[iLargest-1]=iTmpV;
      HeapIfy(Array, iLargest, iHeapSize);
   }
   return 0;
}

int BuildHeap(double *Array, int ArraySize, int *iHeapSize)
{
   (*iHeapSize)=ArraySize;
   for(int i=(ArraySize)/2; i>0; i--)
   {
      HeapIfy(Array, i, (*iHeapSize));
   }
   return 0;
}

int HeapSort(double *Array, int ArraySize)
{
   int iHeapSize;
   double iTmpV;
   BuildHeap(Array, ArraySize, &iHeapSize);
   for(int i=ArraySize; i>0; i-=1)
   {
      iTmpV=Array[0];
      Array[0]=Array[i-1];
      Array[i-1]=iTmpV;
      iHeapSize--;
      HeapIfy(Array, 1, iHeapSize);
   }
   return 0;
}
Ссылки и литература
  1. Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, "Алгоритмы: построение и анализ";
  2. Анимация процесса сортировки массива различными алгоритмами;
  3. Пирамидальная сортировка на Википедии.
Цитаты

"К-мерная музыка - это слишком плоско"
- Жители k+1-ого измерения

At least now I'm sure you're not Pinochio, because if you were, your nose would've crashed into your monitor by now.
- TPB

The problem here seems to be that the material is unreleased? If that is the case, you can easily fix the problem by releasing it. We'll be more than glad to help you distribute it - free of charge! - to our users.
- TPB

 
© Alexey & Alexander Drutsa, 2009–2011