Хурдан эрэмбэлэлт (Quick Sort) - C VS Lisp

Хурдан Эрэмбэлэлтийг 1960 онд Чарльз Энтони Ричард Хоар Москвагийн Их Сургуульд оюутан байхдаа Үндэсний Физикийн Лабораторийн төсөл дээр ажиллаж, тэр үедээ энэхүү эрэмбэлэлтийг хөгжүүлсэн байна. Хурдан Эрэмбэлэлт хамгийн өргөн хэрэглэгддэг эрэмбэлэлт юм.

Хугацаа нь:

• Сайн тохиолдолд O(n log n)
• Дундаж тохиолдолд  O(n log n)
• Муу тохиолдолд O(n^2)

Алгоритм нь:

1. Гол элемент (pivot)-ээ жагсаалтаас сонгоно.
2. Жагсаалтаас гол элементээс их болон бага элементүүдийн хоёр жагсаалт үүсгэнэ.
3. Үүссэн жагсаалт бүр рекурсээр дахин их, бага гэж задарна.
4. Задарсан жагсаалтууд дараах дарааллаар нэгтгэгдэнэ: Бага элементтэй жагсаалт, гол элемент, их элементтэй жагсаалт

Си дээр:

void quicksort(int a[], int first, int last)
{
    //Гол элементээ эхний элементээр авлаа
    int pivot = first;
    int i = first;
    int j = last;
    int temp;
    if (i > j)
        return;
    for(;;)
    {
        while(a[++i] <= a[pivot] && i < last);
        while(a[j] > a[pivot]) j--;
      
        if(i > j)
            break;
       //Гол элементээс бага мөртлөө их талд нь

      //Гол элементээс их мөртлөө бага талд нь байгаа

      //Хоёр элементүүдийн байрыг сольж байна
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //Гол элементээ завсарт нь хавчуулж байна
    temp = a[pivot];
    a[pivot] = a[j];
    a[j] = temp;
    //Их, бага хоёр жагсаалтаа тус тусад нь эрэмбэлнэ
    quicksort(a, first, j - 1);
    quicksort(a, j + 1, last);
}

Лисп дээр:

(defun q-sort (list &optional (f #'<))
 ; Жагсаалт ганц элементтэй бол жагсаалтыг буцаана
  (if (null (cdr list)) list

 ; q-sort-оор эрэмбэлэгдсэн гол элементээс их биш 

; элементүүдтэй жагсаалтыг
    (append (q-sort (remove-if-not #'(lambda (x) (funcall f x (car list))) (cdr list)) f)
; Гол элемент болон
            (list (car list))

; q-sort-оор эрэмбэлэгдсэн гол элементээс их 

; элементүүдтэй жагсаалттай нэгтгэнэ
            (q-sort (remove-if #'(lambda (x) (funcall f x (car list))) (cdr list)) f))))


Жич: Гол элементийг жагсаалтын эхний эхний элементээр сонгож авсан болно.

Гол элемент сонгох дээр Принстоний Их Сургуулийн профессор доктор Роберт Седжвикийн санал болгож байгаагаар жагсаалтын голын индекс дэх  элементийг сонгох юм уу аль эсвэл эхний элемент, голын элемент, сүүлийн элемент гурвын медианаар сонгох нь үр дүнтэй.

Зөвлөмж

Голын индексийг авахдаа (first + last) / 2 гэж авч болох ч first болон last нь хоёулаа их тоо байвал нийлбэр нь орон хэтрэх аюултай тул үүнээс зайлахын тулд first + (last - first) / 2 гэж авах нь зүйтэй.  

Мөнхүү Роберт Седжвикийн санал болгосноор алгоритмыг сайжруулах тал дээр жагсаалтыг хуваасаар хангалттай бага элементтэй болоход Оруулах Эрэмбэлэлтээр эрэмбэлбэл илүү үр дүнтэй гэж үзжээ. Учир нь хэдхэн элементийг эрэмбэлэхийн тулд функц дуудах нь зардалтай юм.

Си хэлний санд qsort() Хурдан эрэмбэлэлтийн функц байдаг. Дэлгэрэнгүйг эндээс үзнэ үү!

Оруулах эрэмбэлэлт (Insertion Sort) [Lisp VS C]

Оруулах эрэмбэлэлт бол маш энгийн эрэмбэлэлт. Бид ихэвчлэн амьдралдаа энэ эрэмбэлэлтийг хэрэглэж байдаг. Үндсэн санаа нь бол жагсаалтаас нэг элементийг нь аваад эрэмбэлэгдсэн жагсаалт руу зөв байрлуулахад оршдог. Уг эрэмбэлэлтийн давуу талууд гэвэл:

1. Хялбархан, ойлгомжтой
2. Жижиг жагсаалтыг хурдан эрэмбэлдэг
3. Нэмэлт санах ой шаардлагагүй
4. Бараг эрэмбэтэй жагсаалтад илүү үр дүнтэй
5. Жагсаалтын хэмжээнээс үл хамааран эрэмбэлж эхэлдэг гэх мэт

Үндсэн санааг нь дээр дурдсан. Псевдо код нь:

 for i ←1 to i <= length(A)-1
     key ← A[ i ]
     > A[ i ] is added in the sorted sequence A[0, .. i-1]
     j ← i - 1
     while j >= 0 and A [ j ] > key
         A[ j +1 ] ← A[ j ]
         j ← j -1
     A [j +1] ← key

 Хугацааны хувьд:

                 Сайн тохиолдолд (Бараг эрэмбэлэгдсэн): Ө(n) 

                 Дундаж тохиолдолд: O(n^2)

           Муу тохиолдолд : О(n^2)

Си хэл дээр:

#include <stdio.h>
//Массиваа хэвлэнэ
void print_array(int a[], int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("%d ", a[i]);
    putchar('\n');
}

void insertion_sort(int a[], int n)
{
    int i, j;
    int key;
    for(i = 1; i < n; i++)
    {
        key = a[i];
        j = i - 1;
        //key-ээс их элементүүдийг урагшлуулж
        while(j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        //Үүссэн хоосон зайд key орно
        a[j + 1] = key;
        //Массивыг хэвлэж байна
        print_array(a, n);
    }
}

int main()
{
    int a[8] = {6, 5, 3, 1, 8, 7, 2, 4};

    print_array(a, 8);
    insertion_sort(a, 8);

    return 0;
} 

Гаралт нь:

6 5 3 1 8 7 2 4 
5 6 3 1 8 7 2 4 
3 5 6 1 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 7 8 2 4 
1 2 3 5 6 7 8 4 
1 2 3 4 5 6 7 8 

Lisp дээр:

Гаралт нь:

Өсөхөөр эрэмбэлэгдэж буй

(6) 
(5 6) 
(3 5 6) 
(1 3 5 6) 
(1 3 5 6 8) 
(1 3 5 6 7 8) 
(1 2 3 5 6 7 8) 
(1 2 3 4 5 6 7 8) 

Буурахаар эрэмбэлэгдэж буй

(6) 
(6 5) 
(6 5 3) 
(6 5 3 1) 
(8 6 5 3 1) 
(8 7 6 5 3 1) 
(8 7 6 5 3 2 1) 
(8 7 6 5 4 3 2 1) 

Лисп дээр өөрийнх нь эрэмбэлэх SORT гэсэн МАКРО байдаг. Энэ эрэмбэлэх МАКРО нь

Оруулах Эрэмбэлэлт дээр үндэслэсэн байдаг. Жишээ програм:

(setq list '(6 5 3 1 8 7 2 4))
(write-line "Lisp-ийн өөрийнх нь эрэмбэлэх функц ашиглаж байна")
(print list)

;Өсөхөөр эрэмбэлээд хэвлэж байна
(print (sort list #'<))

;Буурахаар эрэмбэлээд хэвлэж байна
(print (sort list #'>)) 

Гаралт нь:

Lisp-ийн өөрийнх нь эрэмбэлэх функц ашиглаж байна

(6 5 3 1 8 7 2 4) 
(1 2 3 4 5 6 7 8) 
(8 7 6 5 4 3 2 1)  

Дараагийн эрэмбэлэлт Хурдан Эрэмбэлэлт(Quick Sort) байна.
 

Сонгох Эрэмбэлэлт (Selection Sort) - C vs Lisp

Сонгох эрэмбэлэлт. Энэ эрэмбэлэлтийг Си болон Лисп хэл дээр үзье. Сонгох эрэмбэлэлтийн мөн чанар нь бол жагсаалтаас хамгийн бага элементийг сонгож жагсаалтын эхний элементтэй солиход оршдог. Хамгийн бага элементийг олохын тулд жагсаалтыг бүх элементийг шалгадаг болохоор жагсаалтын хэмжээ их үед тохиромжгүй эрэмбэлэлтийн арга юм. Харин жижиг жагсаалтыг (20, 30 элементтэй) бол хурдан эрэмбэлдэг. Бидний өмнө үздэг Хөвөх Эрэмбэлэлт-ээс арай хурдан.

Хугацааны хувьд бол O(n²).

Си дээрх код:

Гаралт нь:

Одоо Лисп дээр үзье. Лисп дээр маш хялбархан бичиж болно.

Одоо гаралтыг нь харъя:

Дараагийн эрэмбэлэлтээр Оруулах Эрэмбэлэлт (Insertion Sort) үзнээ. Явандаа бүх эрэмбэлэлтээ үзсэний дараа ерөнхий харьцуулалт хийх санаа байна. За тэгээд сонирхож байгаа хүмүүс үзэл бодлоо чөлөөтэй хуваалцаарай!

Хөвөх эрэмбэлэлт (Bubble Sort) Х Лисп хэл Х Си хэл

За Лисп хэлийг оролдож үзэж байна. Тэгээд энэ хөвөх эрэмбэлэлтийг Лисп дээр хийж үзэхээр шийдлээ. Хөвөх эрэмбэлэлт бол хамгийн энгийн эрэмбэлэлт. Үндсэн санаа нь бол хөөс хөвөх зарчимтай адил. Усан дотор хөнгөхөнүүд нь дээш хөөрч, хүнд нь доошилдогтой адил жагсаалтын бага элементүүд аажмаар дээшилдэг. Үндсэн хийж байгаа үйлдэл нь зэрэгцээ элементүүдийг шалгаад байрыг нь солих замаар явна.

Хөвөх эрэмбэлэлт нь туулай яст мэлхийн төрлийн эрэмбэлэлт. Энэ төрлийн эрэмбэлэлт нь нэг төрлийн элементүүд нь хурдан байрандаа орж үлдсэн нь удаан байрандаа ордог. Хөвөх эрэмбэлэлт дээр бол багаас их рүү эрэмбэлж байгаа тохиолдолд их элементүүд нь хурдан байрандаа орж бага элементүүд нь удаан байрандаа ордог. Өөрөөр хэлбэл их элементүүдийг зөв байранд нь оруулахад чиглэгдсэн гэсэн үг. Доор хөдөлгөөнт жишээ үзүүлсэн байна.

 

Псевдо код нь:

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

Нэг иймэрхүү байх нь. За тэгвэл Си хэл дээрх ингэж бичлээ. 

Гаралт нь:

 За тэгвэл одоо Лисп хэл дээр бичиж үзье. 

Гаралт нь:

Лисп хэлний бичиглэлийг харж байгаа байх. Си-гээс хоёр дахин бага бичлэгтэй байгаа 

биз. Дараа нь Сонголтын Эрэмбэлэлтийн тухай оруулнаа.