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
[бичигдэж байна...]