03.com.ua- свободная медицинская энциклопедия. Каждый зарегистрированый участник может редактировать статьи
Сортировка вставками (простыми включениями)
Сортировка вставками (Шаблон:Lang-en) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
- прост в реализации
- эффективен на небольших наборах данных
- эффективен на наборах данных, которые уже частично отсортированы
- это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
- может сортировать список по мере его получения
На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.
Содержание
Примеры реализации
C
<source lang="c">
typedef int array_type; /* или typedef char array_type;*/ void insertSort(array_type a[], int length) { int i, j; array_type value; for (i = 1; i < length; i++) { value = a[i]; for (j = i-1; (j >= 0) && (a[j] > value); j--) { a[j+1] = a[j]; } a[j+1] = value; } }
</source>
C++
<source lang="cpp">
void insertSort(int a[],int length_a) { int i,j,value; for(i = 1; i < length_a; i++) { value = a[i]; for (j = i-1; (j >= 0) && (a[j] > value); j--){ a[j+1] = a[j]; } a[j+1] = value; } }
</source>
PASCAL
<source lang="pascal">
For i:=2 to Сount do Begin Tmp:=Arr[i]; j:=i-1; While (Arr[j]>Tmp) and (j>0) do Begin Arr[j+1]:=Arr[j]; j:=j-1; End; Arr[j+1]:=Tmp; End;
</source>
Компонентный Паскаль
<source lang="pascal"> PROCEDURE InsertionSort (VAR a: ARRAY OF REAL);
VAR i, j: INTEGER; t: REAL;
BEGIN
FOR i := 1 TO LEN(a) - 1 DO t := a[i]; j := i - 1; WHILE (j >= 0) & (a[j] > t) DO a[j + 1] := a[j]; DEC(j) END; a[j + 1] := t END
END InsertionSort; </source>
Scheme
<source lang="scheme">
(define (insert-sort list-sort num) (define (insert-sort-iter iter) (cond ((> iter num ) list-sort) ( (set! temp (take-list list-sort iter num)) (while-j (- iter 1)) (insert-sort-iter (+ iter 1)) ) ) ) (define (while-j j-index) (cond ((and (>= j-index 1) (> (take-list list-sort j-index num) temp)) (set! list-sort (set-list-index! list-sort (take-list list-sort j-index num) (+ j-index 1) num)) (while-j (- j-index 1) )) ((set! list-sort (set-list-index! list-sort temp (+ j-index 1) num))) ) ) (define temp ()) (insert-sort-iter 1) ) ; (define (set-list-index! list-src number index count) (define new-list ()) (define (set-list-index-iter! iter) (cond ((= iter (+ 1 count)) new-list) ((= iter index) (set! new-list (append new-list (list number))) (set-list-index-iter! (+ iter 1)) ) ((= iter count) (set! new-list (append new-list (list (take-list list-src iter count)))) (set-list-index-iter! (+ iter 1)) ) ( (set! new-list (append new-list (list (take-list list-src iter count)))) (set-list-index-iter! (+ iter 1)) ) ) ) (set-list-index-iter! 1)) ; (define (take-list list-sort index count) (define (take-list-iter list-sort-iter iter) (cond ((= iter count) (car list-sort-iter)) ((= iter index) (car list-sort-iter)) ((take-list-iter (cdr list-sort-iter) (+ iter 1) )) ) ) (take-list-iter list-sort 1) ) (define test-list (list 7.02 -3.8 3 -4.8 5.1 7.01)) ;(take-list test-list 5 6) ;(set-list-index! test-list 7 1 4) (insert-sort test-list 6)
</source>
Литература
ar:ترتيب بالإدراج da:Indsættelsessortering de:Insertionsort en:Insertion sort es:Ordenamiento por inserción et:Vahelepanemisega sortimine fi:Lisäyslajittelu fr:Tri par insertion he:מיון הכנסה is:Innsetningarröðun it:Insertion sort ja:挿入ソート ko:삽입 정렬 lt:Įterpimo rikiavimo algoritmas nl:Insertion sort no:Sortering ved innsetting pl:Sortowanie przez wstawianie pt:Insertion sort uk:Сортування включенням vi:Sắp xếp chèn zh:插入排序