Оруулах эрэмбэлэлт бол маш энгийн эрэмбэлэлт. Бид ихэвчлэн амьдралдаа энэ эрэмбэлэлтийг хэрэглэж байдаг. Үндсэн санаа нь бол жагсаалтаас нэг элементийг нь аваад эрэмбэлэгдсэн жагсаалт руу зөв байрлуулахад оршдог. Уг эрэмбэлэлтийн давуу талууд гэвэл:
- Хялбархан, ойлгомжтой
- Жижиг жагсаалтыг хурдан эрэмбэлдэг
- Нэмэлт санах ой шаардлагагүй
- Бараг эрэмбэтэй жагсаалтад илүү үр дүнтэй
- Жагсаалтын хэмжээнээс үл хамааран эрэмбэлж эхэлдэг гэх мэт
Үндсэн санааг нь дээр дурдсан. Псевдо код нь:
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; while(j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j--;
} 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) байна.
