Реализации алгоритмов/Сортировка/Вставками: различия между версиями
Содержимое удалено Содержимое добавлено
→Паскаль: оформление |
→PHP: оформление |
||
Строка 185: | Строка 185: | ||
==[[w:PHP|PHP]]== |
==[[w:PHP|PHP]]== |
||
<source lang="php"> |
<big><source lang="php"> |
||
function insertion_sort(&$a) { |
function insertion_sort(&$a) { |
||
// для каждого $a[$i] начиная со второго элемента... |
// для каждого $a[$i] начиная со второго элемента... |
||
Строка 199: | Строка 199: | ||
} |
} |
||
} |
} |
||
</source> |
</source></big> |
||
==[[w:Ruby|Ruby]]== |
==[[w:Ruby|Ruby]]== |
Версия от 19:10, 17 мая 2012
Haskell
insert :: Ord a ⇒ a → [a] → [a]
insert x [] = [x]
insert x (y : ys)
| x ≤ y = x : y : ys
| otherwise = y : insert x ys
isort :: Ord a ⇒ [a] → [a]
isort [ ] = [ ]
isort (x : xs) = insert x (isort xs)
Си
int i, j, temp;
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 );
}
C++(оптимизирован)
Было произведено три пункта оптимизации:
- нахождение минимального элемента и помещение его в первую позицию(это требуется для правильного функционирования второго пункта)
- выход из внутреннего цикла, когда элемент находится на требуемой позиции
- замена операции обмена(swap) операцией присваивания.
template <class Item>
void exch(Item &A, Item &B)
{
Item t = A; A = B; B = t;
}
template <class Item>
void compexch (Item &A, Item &B)
{
if (B < A) exch(A, B) ;
}
template <class Item>
void insertion_sort(Item a[], int L, int R)
{
int i;
for(i = R; i > L; i--) compexch(a[i-1], a[i]);
for (i = L + 2; i <= R; i++)
{
int j = i;
Item cur = a[j];
while (a[j - 1] > cur)
{
a[j] = a[j - 1];
j--;
}
a[j] = cur;
}
}
C# (с возвратом результата)
public int[] InsertionSort(int[] array)
{
int i;
int[] result = new int[array.Length];
for (i = 0; i < array.Length; i++)
{
int j = i;
while ((j > 0) && (result[j-1] > array[i]))
{
result[j] = result[j - 1];
j--;
}
result[j] = array[i];
}
return result;
}
C# (без дополнительной памяти)
public void InsertionSort(ref int[] array)
{
int i;
for (i = 1; i < array.Length; i++)
{
int j;
int buf = array[i];
for (j = i - 1; j >= 0; j--)
{
if (array[j] < buf)
break;
array[j + 1] = array[j];
}
array[j + 1] = buf;
}
}
Java
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;
}
}
VBA
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)
j = j - 1
If j < l Then Exit Do
Loop
Mus(j + 1) = 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
Паскаль
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;
PHP
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;
}
}
Ruby
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