Friday, February 5, 2010

QuickSort буюу хурдан эрэмбэлэлтийн алгоритм

Энэ алгоритмыг хоёр янзаар бичиж болно.  Нэг нь рекурсив функцтайгаар нөгөөх нь стек өгөгдлийн бүтцийг ашиглаж рекурсгүй хийх боломжтой.
Рекурсив функцийг ашигласан код
template <class Type>
int partition(Type a[],int l,int r)
{
     Type v = a[r];
     int i = l-1, j = r;
     for(;;)
     {
          while(a[++i]
          while(j>1&&a[--j]>v);
          if (i>=j) break;
          swap(a,i,j);
     }
     swap(a,i,r);
     return i;
}
void quickSort(Type a[],int l,int r)
{
     if (l
     {
          int i = partition(a,l,r);
          quickSort(a,l,i-1);
          quickSort(a,i+1,r);
     }
}

Рекурсгүй хувилбар нь
template <class Type>
void quickSort(Type a[],int l,int r)
{
     int i;
     Stack<int> st;
     for(;;)
     {
          while(r>l)
          {
               int i = partition(a,l,r);
               if (i-1>r-i)
               {
                    st.push(l); st.push(i-1);
                    l = i+1;
               }
               else
               {
                    st.push(i+1); st.push(r);
                    r = i-1;
               }
          }
          if (st.empty()) break;
          st.pop(r); st.pop(l);
     }
}

hg
[бичигдэж байна...]

4 comments:

Мөнхбаатар said...

Жаахан түвэгтэй алгоритм шүү :D

C дээр өмнөх бичлэгүүд дээр дурдагдсан stdlib.h сангийн qsort,
C++ дээр algorithm сангийн sort -г ашиглачихдаг :D

Гүнчин-Ишийн Шаравсамбуу said...

Тийм шүү :)
Гэхдээ цаана нь юу болоод байгааг гадарлавал зүгээр байх гэж бодоод :)

Prince said...

ene algoritm iig yaj ajilaad bgaag neg tailbarlaad ugchixgui biz? :D

Prince said...

rekurstei rekursgui yalgaag jo heleed uguuch?