Метод прямого включения

Метод прямого включения

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

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

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

Содержание

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

 isort :: Ord a ⇒ [a] → [a]
 isort [ ] = [ ]
 isort (x : xs) = insert x (isort xs)

C

int i, j;
for (i = 1; i < size; i++) {
	temp = array[i];
	for (j = i - 1; j >= 0; j--) {
		if (array[j] < temp) {
			break;
		}
		array[j+1] = array[j];
	}
	array[j+1] = temp;
}

C++

  #include <algorithm>
 
  template< typename Iterator >
  void insertion_sort(  Iterator first, Iterator last )
  {
      for( Iterator i = first + 1; i < last; ++i )
          for( Iterator j = i; first < j && *j < *(j - 1); --j )
              std::iter_swap( j - 1, j );
  }


	 public static void insertionSort (int[] m, int a, int b) {
		  int t;
		  int i, j;
		  for ( i=a; i < b; i++) {
		    t = m[i];
		    for ( j=i-1; j>=a && m[j] > t; j--)
		    	m[j+1] = m[j];
		    m[j+1] = t;
		  }
		}


Sub Sort(Mus() As Long)
    Dim l As Long, r As Long, i As Long, j As Long, buf As Long
    l = LBound(Mus)
    r = UBound(Mus)
 
    For i = (l + 1) To r
        buf = Mus(i)
        j = i - 1
        Do While (Mus(j) > buf)
            Mus(j + 1) = Mus(j)
            If j = l Then Exit Do
            j = j - 1
        Loop
        Mus(j) = buf
    Next
End Sub

Python

def fast_insertion_sort(l):
 for i in xrange(1,len(l)):
  j=i-1
  value=l.pop(i)
  while (j>=0) and (l[j]>value):
   j-=1
  l.insert(j+1,value)
 return l

Pascal

const N=255;
type array_type=array [1..N] of integer; 
 
procedure InsertSort(var x:array_type);
var
  i, j, buf:integer;
begin
  for i:=2 to N do
  begin
    buf:=x[i];
    j:=i-1;
    while (j>=1) and (x[j]>buf) do
    begin
      x[j+1]:=x[j];
      j:=j-1;
    end;
    x[j+1]:=buf;
  end;
end;


function insertion_sort(&$a) {
  // для каждого $a[$i] начиная со второго элемента...
  for ($i = 1; $i < count($a); $i++) {
    $x = $a[$i];
    for ($j = $i - 1; $j >= 0 && $a[$j] > $x; $j--) {
      /* сдвигаем элементы вправо, пока выполяется условие
         $a[$j] > $a[$i] */
      $a[$j + 1] = $a[$j];
    }
    // на оставшееся после сдига место, ставим $a[$i]
    $a[$j + 1] = $x;
  }
}


arr = [9, 13, 7, 12, 10, 14, 8, 11, 6]
for i in 1..arr.length - 1
  x = arr[i]
  for j in 0..i - 1
    if arr[i] < arr[j]
        i.downto(j + 1) do |k|
          arr[k] = arr[k - 1]
        end
      arr[j] = x
      break
    end
  end
end
puts "#{arr.join(" ")}"
# output => 6 7 8 9 10 11 12 13 14

Литература


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Метод прямого включения" в других словарях:


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»