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

Исходник на языке Си быстрой сортировки массива.

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

Сложность алгоритма (количество операций), где n — длина массива:

  • в лучшем случае — O(n);
  • в худшем случае — O(n2);
  • в среднем случае — O(n·log(n)).

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

Листинг файла quick_sort.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define STR_FILE_IN_NAME "input.txt"
#define STR_FILE_OUT_NAME "output.txt"
int MkOutFile(FILE *f_in, FILE *f_out);
void Swap(double &ldA, double &ldB);
void QuickSort(double *dArray, unsigned long int iLeft, unsigned long int iRight);
bool bAll=false;

int main(int argc, char* argv[])
{
   char sFInName[256]=STR_FILE_IN_NAME, sFOutName[256]=STR_FILE_OUT_NAME, *pNothingDo;
   FILE *f_in, *f_out;
   char cRead;
   if(argc>1){
      if((argv[1][0]=='-')&&(argv[1][1]=='l')&&(argv[1][2]=='\0')){
         bAll=true;
      } else {
         pNothingDo=strcpy(sFInName,argv[1]);
         if(argc>2) pNothingDo=strcpy(sFOutName,argv[2]);
      }
   }
   //----------------begin all---
   if(bAll){
      printf("Input name of Input File:");
      scanf("%s",sFInName);
      printf("Input name of Output File:");
      scanf("%s",sFOutName);
   }
   //----------------end all-----
   f_in=fopen(sFInName,"r");
   f_out=fopen(sFOutName,"w");
   if (!f_in){
      printf("Error: can't open file with name %s\n", sFInName);
      if(bAll) scanf("%c", &cRead);
      return -1;
   }
   if (!f_out){
      printf("Error: can't open file with name %s\n", sFOutName);
      if(bAll) scanf("%c", &cRead);
      return -1;
   }
   if(MkOutFile(f_in, f_out)>=0){
      printf("Program was finished successfully!\n");
   } else {
      printf("Program was finished unsuccessfully!\n");
   }
   fclose(f_in);
   fclose(f_out);
   //----------------begin all---
   if(bAll){
      double dRead;
      f_in=fopen(sFInName,"r");
      f_out=fopen(sFOutName,"r");
      printf("Input File:\n");
      while(fscanf(f_in, "%lg", &dRead)==1){
         printf("%lg ",dRead);
      }
      printf("\n");
      printf("Output File:\n");
      while(fscanf(f_out, "%lg", &dRead)==1){
         printf("%lg ",dRead);
      }
      printf("\n");
      fclose(f_in);
      fclose(f_out);
   }
   if(bAll) scanf("%c", &cRead);
   //----------------end all-----
   return 0;
}

int MkOutFile(FILE *f_in, FILE *f_out)
{
   unsigned long int iSize, iMaxOtr, iOtr;
   double dMaxNumber;
   double *dLeftArray, *dRightArray;
   if(fscanf(f_in, "%ld", &iSize)!=1) return -1;
   if(iSize<=0) return -1;
   dLeftArray = new double[iSize];
   dRightArray = new double[iSize];
   unsigned long int i=0, iLeft, iRight;
   while (i<iSize) {
      if(fscanf(f_in, "%lg", &dLeftArray[i])!=1) return -1;
      if(fscanf(f_in, "%lg", &dRightArray[i])!=1) return -1;
      i++;
   }
   QuickSort(dLeftArray,0,iSize-1);
   QuickSort(dRightArray,0,iSize-1);
   i=0;
   dMaxNumber=0.0;
   iMaxOtr=0;
   iOtr=0;
   iLeft=0;
   iRight=0;
   while((iLeft<iSize)&&(iRight<iSize)) {
      if(dLeftArray[iLeft]<=dRightArray[iRight]){
         iOtr++;
         iLeft++;
      } else {
         iOtr--;
         iRight++;
      }
      if(iOtr>iMaxOtr) {
         iMaxOtr=iOtr;
         dMaxNumber=dLeftArray[iLeft-1];
      }
   }
   fprintf(f_out,"%lg ", dMaxNumber);
   fprintf(f_out,"%ld", iMaxOtr);
   delete [] dLeftArray;
   delete [] dRightArray;
   return 1;
}
void Swap(double &ldA, double &ldB)
{
   double dC;
   dC=ldA;
   ldA=ldB;
   ldB=dC;
}
void QuickSort(double *dArray, unsigned long int iLeft, unsigned long int iRight)
{
   unsigned long int iY, iJ;
   double dX;
   iY=iLeft-1;
   iJ=iRight+1;
   dX=dArray[iLeft];
   do {
      do {
         iJ--;
      } while(dArray[iJ]>dX);
      do {
         iY++;
      } while(dArray[iY]<dX);
      if (iY<iJ) {
         Swap(dArray[iY],dArray[iJ]);
      }
   } while(iY<iJ);
   if (iJ+1<iRight) QuickSort(dArray, iJ+1, iRight);
   if (iLeft<iJ) QuickSort(dArray, iLeft, iJ);
}
Ссылки и литература
  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