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

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

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

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

Содержание

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

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)
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home