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

Saturday, January 23, 2010

C/C++ Binary Search function in Standard Library

C/C++ хэлний стандарт сангуудын нэлээд хүчирхэг нэгэн Функц болох bsearch функц stdlib.h/cstdlib толгой файлд тодорхойлогдсон байдаг. Хэрэв өгөгдсөн элемэнт өгөгдсөн эрэмбэлэгдсан массивт байхгүй бол NULL заагчийг буцаадаг.
void * bsearch ( const void * key, const void * base, size_t num, 
size_t size, int ( * comparator ) ( const void *, const void * ) );
key - хайж буй элемэнтийн санах ойд эзлэх хаяг
base - хайлт хийж буй массив
num - массивт хайлт хийх хэмжээ
size - массивийн өгөгдлийн төрлийн санах ойд эзлэх хэмжээ
compareFunction - харьцуулалт хийх функийн нэр. Харьцуулалт хийх функцийг миний өмнө бичсэн qsort() функцийг ашиглахад хэрэглэх зарчимтай ижил.
int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
}

Жишээ код:

Wednesday, January 6, 2010

C/C++ дээр байдаг inline түлхүүр үгийн үүрэг

Сэдэвтэй холбоотой нийтлэл тул блогоосоо копи паст хийв.

Функцийн амин чухал үүргүүдийн нэг нь санах ойг хэмнэх байдаг. Өөрөөр хэлбэл функцийг дуудах бүрийд програмын удирдлага нэг л газар очдог бөгөөд функц дуудагдах тоогоор програмд давтагдан бичигдэхгүй гэсэн үг юм. Функц дуудах командад хүрмэгц удирдлага функцийн эхлэлийн команд дээр харайж очих бөгөөд, харин функц ажиллаад дуусахад удирдлага буцаж дуудсан газраа ирдэг.
Функц хэдийгээр санах ойг хэмнэх сайн талтай ч маш олон дуудагдах тохиолдолд програмын хурдад муу нөлөө үзүүлэх боломжтой. Өөрөөр хэлбэл тэр бүрийд шаардлагатай регистрүүдийг стект хийх, аргументүүдийг мөн хадгалах, удирдлагыг шилжүүлэх, буцах бүрийдээ регистрүүдийг сэргээх, удирдлага буцаах зэрэг үйлдлүүд хийгдэнэ.
Биелэлтийн хурдыг нэмэгдүүлэхийн тулд функцийг дотоод функц болгох боломжтой байдаг. Энэ юу гэсэн үг вэ гэхээр ийм функц нь програмыг хөрвүүлэх буюу компайлдах үед функцыг дуудсан газар бүрт нь функцрүү чиглүүлсэн удирдлага шилжүүлэх командыг биш харин уг функцын командуудыг шууд орлуулан бичдэг. Том хэмжээтэй функцүүдийн хувьд энгийн аргаар зохион байгуулах нь илүү байж болох юм. Харин цөөн тооны коммандуудаас тогтсон функцүүдийг дотоод биш болгон зохион байгуулах нь санах ойн хувьд ч бараг хэмнэлтгүй (алдагдалтай ч байж болно), хурдны хувьд ч алдагдалтай байж магадгүй. Нэг програмд тун олон удаа давтагдан орж байгаа бага хэмжээний бүлэг үйлдлийг функц болголгүй дахин давтан бичих нь програмын хурдыг нэмэх боловч програм дэндүү нүсэр бүтэцтэй ойлгомж муутай болох аюултай. Ийм л тохиолдолд дотоод функцийг ашиглах нь зүйтэй. Дараах жишээнд дотоод функцийг ашиглаж үзүүлсэн байна.
#include <iostream>
using namespace std;
inline float lbsToKg(float pounds)
{
return 0.453592*pounds;
}
int
main(void)
{
float lbs;
cout << "Jingee oruul (funteer) :";
cin >> lbs;
cout << "Tanii jin (kilogramaar) :"
<< lbsToKg(lbs);
}

Дотоод функцийг тодорхойлохын тулд inline гэсэн түлхүүр үгийг функцийн тодорхойлолтод хэрэглэх хэрэгтэй. Харин функцийн урьдчилсан тодорхойлолт биш, жинхэнэ биеийг нь үндсэн програмаас өмнө тодорхойлж өгсөн байх ёстой. Уг функцийн биеийг програм дотор шууд орлуулан ашиглах ёстой учраас ийм шаардлага бий болж байна. Энэ тохиолдолд функцийн урьдчилсан тодорхойлолт шаардагдахгүй.

Monday, January 4, 2010

Quick sort

C/C++ хэлэнд хурдаараа хамгийн дээгүүрт орох quicksort буюу хурдан эрэмбэлэлтийг stdlib.h санд оруулж өгсөн байдаг. Бодлого бодох гээд яарж байхад эрэмбэлэлтийн код бичихгүй, залхуу (бас эрэмбэлэлтийн функц бичиж дадаагүй) хүнд хичнээн амар гээч :)
Гэхдээ шууд идэхэд бэлэн доширак арай биш, эрэмбэлэх гэж байгаа массив маань ямар төрлийн элемэтүүдээс бүрдэхээс шалтгаалж харилцан адилгүй харьцуулах функц бичнэ.
int төрлийн массив эрэмбэлэх бол:

int compare_int(const void *a,const void *b) {
        int *x = (int *) a;
        int *y = (int *) b;
        return *x - *y;
}

Бутархай тоон массив бол:

int compare_double(const void *a,const void *b) {
        double *x = (double *) a;
        double *y = (double *) b;
        if (*x < *y) return -1;
        else if (*x > *y) return 1; 
        return 0;
}

Тэмдэгт мөр буюу char* эрэмбэлэх бол:
#include <string.h>
int compare_str(const void *a,const void *b) {
        return (strcmp((char *)a,(char *)b));
}
гэх маягаар програмыхаа хамгийн дээр нь зарлаад өгчихнө. Харин програм дундаа хурдан эрэмбэлэлтийг ашиглахдаа:

qsort(массивийн нэр,эрэмбэлэх хэмжээ,
        sizeof(массивийн өгөгдлийн төрлийн нэр),харьцуулах функцийн нэр);

Жишээ кодууд:
/*
int массив эрэмбэлэх
*/
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a,const void *b) {
        int *x = (int *) a;
        int *y = (int *) b;
        return *x - *y;
}
int main(){
        int i;
        int a[] = {9, 45, 234, 32, 3424, 345, 78, 85}; 
        qsort(a, 8, sizeof(int), compare_int);
        for(i = 0; i < 8; i++){
                printf("%d\n", a[i]);
        }      
return 0;
}

/*
Тэмдэгт мөр эрэмбэлэх
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare_str(const void *a,const void *b) {
        return (strcmp((char *)a,(char *)b));
}
int main(){
        int i;
        char a[4][20] = {"Sharavsambuu", "Xacaa", "Munkhbaatar", "Gansukh"}; 
        qsort(a, 4, sizeof(a[0]), compare_str);
        for(i = 0; i < 4; i++){
                printf("%s\n", a[i]);
        }      
return 0;
}