Хурдан эрэмбэлэлт (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() Хурдан эрэмбэлэлтийн функц байдаг. Дэлгэрэнгүйг эндээс үзнэ үү!