Сортировка методом вставок

Материал из Википедии — свободной энциклопедии

Сортировка методом вставок (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации
эффективен на небольших наборах данных
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения

На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.

Содержание

1 Примеры реализации

[править] Примеры реализации

[править] 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;
     }
 }

[править] 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;

[править] 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)