Сортировка вставками (простыми включениями)

Сортировка вставками (Шаблон: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>

Литература

• Шаблон:Книга