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;
}

4 comments:

Гансүх said...

Сайхан функц шүү :)

GansukhB said...

Өө, амьдаа :) коммэнт үлдээсэнд баярлалаа :)

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

хэхэ GansikhB-г коммент үлдээсэн байх гэж бодсон :)
сайхан нийтлэл болжээ. Түлхүүр үгнүүдийг яаж highlight-тай болгосон бэ? Тус бүрээр нь өнгө оноосон уу?

GansukhB said...

Шараваа энд highlight-тай html үүсэдэг гоё онлайн tool байна лээ :)