Оруулах эрэмбэлэлт (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) байна.