Реализации алгоритмов/Сортировка/Вставками
(перенаправлено с «Примеры реализации сортировки вставками»)
isort :: (Ord e) => [e] -> [e]
isort [] = []
isort (x : xs) = insert x $ isort xs
where
insert x [] = [x]
insert x (y : ys)
| x <= y = x : y : ys
| True = y : insert x ys
int pass, j, hold;
for (pass = 0; pass < SIZE-1; pass++){
for (j = pass+1; j < SIZE; j++){
if (n[pass]>n[j]){
hold = n[j];
n[j] = n[pass];
n[pass] = hold;
}
}
}
typedef struct List {
struct List* next;
struct List* prev;
uint32_t id;
} list_t;
void list_insert_prev(list_t* head, list_t* tail) {
tail->prev = head->prev;
tail->next = head;
head->prev = tail;
if (tail->prev) tail->prev->next = tail;
}
list_t* list_cut(list_t* head) {
list_t* cut = head;
if (cut->next) head->next->prev = head->prev;
if (cut->prev) head->prev->next = head->next;
return cut;
}
void list_insertion_sort(list_t* head) {
while (head->next) {
if (head->next->id < head->id) {
list_t* cut = list_cut(head->next);
while ((head->prev) && (cut->id < head->prev->id)) {
head = head->prev;
}
list_insert_prev(head, cut);
} else {
head = head->next;
}
}
}
#include <algorithm>
template <typename Iterator>
void insertion_sort(Iterator first, Iterator last)
{
if (!(first < last))
return;
for (Iterator i = first + 1; i != last; ++i)
for (Iterator j = i; j != first && *j < *(j - 1); --j)
std::iter_swap(j - 1, j);
}
Произведены следующие оптимизации:
- нахождение минимального элемента и помещение его в первую позицию (это требуется для правильного функционирования второго пункта);
- выход из внутреннего цикла, когда элемент находится на требуемой позиции;
- замена операции обмена (swap) операцией присваивания.
template <typename Item>
void exch(Item &A, Item &B)
{
Item t = A; A = B; B = t;
}
template <typename Item>
void compexch(Item &A, Item &B)
{
if (B < A) exch(A, B);
}
template <typename Item>
void insertion_sort(Item a[], int L, int R)
{
for(int i = R; i > L; i--)
compexch(a[i - 1], a[i]);
for (int 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;
}
}
public void InsertionSort(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
int cur = array[i];
int j = i;
while (j > 0 && cur < array[j - 1])
{
array[j] = array[j - 1];
j--;
}
array[j] = cur;
}
}
С++11
править#include <algorithm>
#include <cstddef>
template<typename T>
void insertion_sort(T array[], std::size_t size)
{
for (std::size_t sorted_size = 1; sorted_size < size; sorted_size++)
{
if (array[sorted_size] < array[sorted_size - 1])
{
T tmp = std::move(array[sorted_size]);
std::size_t idx = sorted_size;
for (; idx != 0 && tmp < array[idx - 1]; idx--)
{
array[idx] = std::move(array[idx - 1]);
}
array[idx] = tmp;
}
}
}//
public void InsertionSort(int[] array)
{
for (int 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;
}
}
// метод не работает (его сломали до меня).
public static void insertIntoSort(int[] arr)
{
int temp, j;
for(int i = 0; i < arr.length - 1; i++)
{
if (arr[i] > arr[i + 1])
{
temp = arr[i + 1];
arr[i + 1] = arr[i];
for (j = i; j >0 && temp < arr[j - 1]; j--)
arr[j] = temp;
}
}
}
public static void insertionSort2(int[] m, int a, int b)
{
int i, j, t;
for (i = a; i < b; i++)
{
t = m[i];
for (j = i - 1; j >= a - 1 && m[j] > t; j--) m[j + 1] = m[j];
m[j + 1] = t;
}
}
(function() {
var oSort= function() {
var that = {};
//собственно сама функция сортировки
that.insertionSort = function(a) {
var i,j,x,
}
return a;
};
that.getCountOfElements = function(a) {
var i = 0,
elem;
for (elem in a) {
i++
}
return i;
};
return that;
}();
console.log(oSort.insertionSort([9, 13, 7, 12, 10, 14, 8, 11, 6]));
//[6, 7, 8, 9, 10, 11, 12, 13, 14]
})();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
k=input()
a=list(map(int,input().split()))
n=len(a)-1
k=0
for i in range(len(a)):
for j in range(len(a)-1-i):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
o=True
k+=1
if not o : break
print(*a)
for(1..$N-1){
my$tmp=$out[$_];
for($j=$_-1;$j>=0;$j--){
$out[$j+1]=$out[$j];
last if($out[$j]lt$tmp);
}
$out[$j+1]=$tmp;
}
const N = 255;
type TArray = array [1..N] of integer;
procedure InsertSort(var x: TArray);
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;
type TArray<T> = array of T;
procedure TSomeObject.InsertSort<T>(var arr: TArray<T>);
var
i, j: integer;
buf:T;
begin
for i := Low(arr)+1 to High(arr) do
begin
buf := arr[i];
j := i - 1;
while (j >= Low(arr) ) and (arr[j] > buf) do
begin
arr[j + 1] := arr[j];
Dec(j);
end;
arr[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;
}
return $a; // return
}
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
Входной массив Y[1],...,Y[N]
FOR I=2 TO N
K=Y[I]
J=I-1
WHILE J>0 AND Y[J]>K
Y[J+1]=Y[J]
J=J-1
WEND
Y[J+1]=K
NEXT I
type sort_lst is table of integer;
----------------------Сортировка вставками-----------------------------------------------
Function Insertion_sort(in_list IN sort_lst) return sort_lst
IS
l_list sort_lst := sort_lst();
h pls_integer; j pls_integer;
begin
l_list := in_list;
for i in l_list.first..l_list.last-1 loop
j:=i;
while j>=1 and l_list(j)>l_list(j+1) loop
h:= l_list(j);
l_list(j):=l_list(j+1);
l_list(j+1):=h;
j:=j-1;
end loop;
end loop;
return l_list;
end Insertion_sort;