QuickSort

Бидний урьд өмнө хэрэглэж байсан бөмбөлөгөн эрэмбэлэлт, оруулалттай эрэмбэлэлт, сонголттой эрэмбэлэлтийн аргууд нь олон тооны элемэнтүүдийн эрэмбэлэх үед хугацаа нэлээд шаарддаг байсан. Харин эрэмбэлэлтийн маш үр өгөөжтэй нэгэн аргыг 1962 онд Ч. Хоар санал болгосон. Энэ аргыг QuickSort буюу хурдан эрэмбэлэлтийн арга хэмээн нэрлэдэг.

Энэ аргын гол санаа нь эхлээд анхны эрэмбэлэлт хийгдээгүй массив дотроос нэгэн Х элемэнтийг сонгон авч түүний зүүн талд түүнээс бага буюу тэнцүү элементүүд, баруун талд түүнээс олон элемэн байрлаж байхаар сэлгэн байрлуулна. Энэ алхмын дараа Х элемэнт нь өөрийн байраа олсон байх ба түүний 2 талд эрэмбэлэгдээгүй 2 хэсэг үүссэн байх бөгөөд энэ хоёр хэсэг дээрээ дахин түрүүчийн алхмыг хийх гэх мэтээр бүгд эрэмбэлэгдэх хүртэл үргэлжилнэ.

Харин одоо бүхэл тоон массивын элемэнтүүдийг эрэмбэлэх програмыг рекурс ашиглан бичье.

#include <stdio.h>
int a[100];
int qsort(int m,int l){
  int i=m;
  int j=l;
  int x=a[(m+l)/2];
   do
   {
      while(a[i]<x) i++;
      while(a[j]>x) j--;
      if(i<=j){
       int w=a[i];
       a[i]=a[j];
       a[j]=w;
       i++;
       j--;
      }
   }
   while(i<=j);
   if (m<j)  qsort(m,j);
   if (i<l)  qsort(i,l);

}
main(){
     int n,e;
     scanf("%d",&n);
  for(e=0; e<n; e++)
      scanf("%d",&a[e]);
  qsort(0,n-1);
  for(e=0; e<n; e++)
      printf("%d ",a[e]);
return 0;
}

Харин QuickSort-ыг C/C++ хэлэнд бичиглэл маш багатайгаар алдаа бараг гаргахгүйгээр хэрэглэж боломж байдагийг та бүхэн мэдэх үү?
C/C++ хэлэнд stdlib.h толгой файлд qsort хэмээх функцийг цаанаас нь тодорхойлж өгсөн байдаг ба түүнийг хэрэглэхэд маш хялбар. Энэ функцыг ашиглан бүхэл тоон массивыг эрэмбэлэх жишээг доор үзүүллээ.

#include <stdio.h>
#include <stdlib.h>
int comp(const void*a,const void*b){
  int *x=(int*)a;
  int *y=(int*)b;
  return *x-*y;
}
int main(){
  int n;
  int a[100];
  scanf("%d",&n);
  for(int i=0; i<n; i++)
      scanf("%d",&a[i]);
  qsort(a,n,sizeof(a[0]),comp);
  for(int i=0; i<n; i++)
  printf("%d ",a[i]);
return 0;
}