Реализации алгоритмов/Сортировка/Выбором: различия между версиями
Содержимое удалено Содержимое добавлено
DannyS712 (обсуждение | вклад) м <source> -> <syntaxhighlight> (phab:T237267) |
|||
Строка 1: | Строка 1: | ||
{{wikipedia|Сортировка выбором}} |
{{wikipedia|Сортировка выбором}} |
||
== [[w:Си (язык программирования)|C]] == |
== [[w:Си (язык программирования)|C]] == |
||
< |
<syntaxhighlight lang="c"> |
||
for (int i = 0; i < size - 1; i++) |
for (int i = 0; i < size - 1; i++) |
||
{ |
{ |
||
Строка 19: | Строка 19: | ||
array[min_i] = temp; |
array[min_i] = temp; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:C++|C++]] == |
== [[w:C++|C++]] == |
||
< |
<syntaxhighlight lang="cpp"> |
||
template <typename T, typename C = less< typename T::value_type> > |
template <typename T, typename C = less< typename T::value_type> > |
||
void select_sort( T f, T l, C c = C() ) |
void select_sort( T f, T l, C c = C() ) |
||
Строка 41: | Строка 41: | ||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:C Sharp|C#]] == |
== [[w:C Sharp|C#]] == |
||
< |
<syntaxhighlight lang="cpp"> |
||
public void SelectionSort(int[] arr) |
public void SelectionSort(int[] arr) |
||
{ |
{ |
||
Строка 70: | Строка 70: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Паскаль (язык программирования)|Паскаль]] == |
== [[w:Паскаль (язык программирования)|Паскаль]] == |
||
< |
<syntaxhighlight lang="pascal"> |
||
for i := 1 to n - 1 do begin |
for i := 1 to n - 1 do begin |
||
min := i; |
min := i; |
||
Строка 85: | Строка 85: | ||
end; |
end; |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Компонентный Паскаль|Компонентный Паскаль]] == |
== [[w:Компонентный Паскаль|Компонентный Паскаль]] == |
||
Строка 105: | Строка 105: | ||
== [[w:D (язык программирования)|D]] == |
== [[w:D (язык программирования)|D]] == |
||
< |
<syntaxhighlight lang="d"> |
||
void selectionSort(int[] array) { |
void selectionSort(int[] array) { |
||
int length = array.length; |
int length = array.length; |
||
Строка 121: | Строка 121: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:VBA|VBA]] == |
== [[w:VBA|VBA]] == |
||
< |
<syntaxhighlight lang="vb"> |
||
Sub Sort(Mus() As Long) |
Sub Sort(Mus() As Long) |
||
Dim n As Long, i As Long, j As Long, min As Long |
Dim n As Long, i As Long, j As Long, min As Long |
||
Строка 137: | Строка 137: | ||
Next |
Next |
||
End Sub |
End Sub |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Java|Java]] == |
== [[w:Java|Java]] == |
||
Итерационный алгоритм: |
Итерационный алгоритм: |
||
< |
<syntaxhighlight lang='java'> |
||
public static void selectionSort (int[] numbers){ |
public static void selectionSort (int[] numbers){ |
||
int min, temp; |
int min, temp; |
||
Строка 158: | Строка 158: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсивный алгоритм: |
Рекурсивный алгоритм: |
||
< |
<syntaxhighlight lang='java'> |
||
public static int findMin(int[] array, int index){ |
public static int findMin(int[] array, int index){ |
||
int min = index - 1; |
int min = index - 1; |
||
Строка 186: | Строка 186: | ||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Ruby|Ruby]] == |
== [[w:Ruby|Ruby]] == |
||
< |
<syntaxhighlight lang="ruby"> |
||
a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10] |
a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10] |
||
Строка 209: | Строка 209: | ||
# output => 1 3 3 5 8 10 11 12 17 20 |
# output => 1 3 3 5 8 10 11 12 17 20 |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Python|Python]] == |
== [[w:Python|Python]] == |
||
неустойчивая: |
неустойчивая: |
||
< |
<syntaxhighlight lang='python'> |
||
def swap(arr, i, j): |
def swap(arr, i, j): |
||
arr[i], arr[j] = arr[j], arr[i] |
arr[i], arr[j] = arr[j], arr[i] |
||
Строка 227: | Строка 227: | ||
swap(arr, i - 1, max) |
swap(arr, i - 1, max) |
||
i -= 1 |
i -= 1 |
||
</syntaxhighlight> |
|||
</source> |
|||
устойчивая: |
устойчивая: |
||
< |
<syntaxhighlight lang='python'> |
||
def select_sort_stable(arr): |
def select_sort_stable(arr): |
||
if len(arr) == 0: return |
if len(arr) == 0: return |
||
Строка 242: | Строка 242: | ||
arr[l] = arr[l - 1] |
arr[l] = arr[l - 1] |
||
arr[j] = value |
arr[j] = value |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Ada|Ada]] == |
== [[w:Ada|Ada]] == |
||
< |
<syntaxhighlight lang="ada"> |
||
type arr is array(1..n) of integer; |
type arr is array(1..n) of integer; |
||
i,j,t:integer; |
i,j,t:integer; |
||
Строка 263: | Строка 263: | ||
end loop; |
end loop; |
||
end sort; |
end sort; |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:PHP|PHP]] == |
== [[w:PHP|PHP]] == |
||
< |
<syntaxhighlight lang="php"> |
||
$size = count($arr); |
$size = count($arr); |
||
Строка 285: | Строка 285: | ||
$arr[$min] = $temp; |
$arr[$min] = $temp; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[:w:TurboBasic 1.1|TurboBasic 1.1]]== |
==[[:w:TurboBasic 1.1|TurboBasic 1.1]]== |
||
<big>< |
<big><syntaxhighlight lang="qbasic"> |
||
CLS |
CLS |
||
RANDOMIZE TIMER |
RANDOMIZE TIMER |
||
Строка 347: | Строка 347: | ||
PRINT "ELAPSED TIME=";T1 |
PRINT "ELAPSED TIME=";T1 |
||
PRINT FRE(-1) |
PRINT FRE(-1) |
||
�</ |
�</syntaxhighlight><big> |
||
== [[w:PL/SQL|PL/SQL]] == |
== [[w:PL/SQL|PL/SQL]] == |
||
< |
<syntaxhighlight lang="plsql"> |
||
type sort_list is table of integer index by binary_integer; |
type sort_list is table of integer index by binary_integer; |
||
----------------------------------------------------------- |
----------------------------------------------------------- |
||
Строка 379: | Строка 379: | ||
end SORT_CHOISE; |
end SORT_CHOISE; |
||
</syntaxhighlight> |
|||
</source> |
|||
== Ссылки == |
== Ссылки == |
Текущая версия от 15:57, 16 апреля 2020
C[править]
for (int i = 0; i < size - 1; i++)
{
/* устанавливаем начальное значение минимального индекса */
int min_i = i;
/* находим индекс минимального элемента */
for (int j = i + 1; j < size; j++)
{
if (array[j] < array[min_i])
{
min_i = j;
}
}
/* меняем значения местами */
int temp = array[i];
array[i] = array[min_i];
array[min_i] = temp;
}
C++[править]
template <typename T, typename C = less< typename T::value_type> >
void select_sort( T f, T l, C c = C() )
{
if (f!= l) {
while (f != l - 1) {
T min = f;
for (T i = f + 1; i != l; i++) {
if (c(*i, *min)) {
typename T::value_type tmp = *min;
*min = *i;
*i = tmp;
}
}
f++;
}
}
}
C#[править]
public void SelectionSort(int[] arr)
{
int min, temp;
int length = arr.Length;
for (int i = 0; i < length - 1; i++)
{
min = i;
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
Паскаль[править]
for i := 1 to n - 1 do begin
min := i;
for j := i + 1 to n do
if a[min] > a[j] then
min := j;
if min<>i then begin
t := a[i];
a[i] := a[min];
a[min] := t;
end;
end;
Компонентный Паскаль[править]
PROCEDURE SelectionSort (VAR a: ARRAY OF REAL); VAR i, min: INTEGER; t: REAL; BEGIN FOR i := 0 TO LEN(a) - 2 DO min := i; FOR j := i + 1 TO LEN(a) - 1 DO IF a[min] > a[j] THEN min := j END END; t := a[i]; a[i] := a[min]; a[min] := t END END SelectionSort;
D[править]
void selectionSort(int[] array) {
int length = array.length;
for (int i = 0; i < length - 1; ++i) {
int min = array[i];
int nmin = i;
for (int j = i + 1; j < length; ++j) {
if (array[j] < min) {
min = array[j];
nmin = j;
}
}
array[nmin] = array[i];
array[i] = min;
}
}
VBA[править]
Sub Sort(Mus() As Long)
Dim n As Long, i As Long, j As Long, min As Long
n = UBound(Mus)
For i = LBound(Mus) To n - 1
min = i
For j = i + 1 To n
If Mus(min) > Mus(j) Then min = j
Next
Swap Mus(i), Mus(min)
Next
End Sub
Java[править]
Итерационный алгоритм:
public static void selectionSort (int[] numbers){
int min, temp;
for (int index = 0; index < numbers.length-1; index++){
min = index;
for (int scan = index+1; scan < numbers.length; scan++){
if (numbers[scan] < numbers[min])
min = scan;
}
// Swap the values
temp = numbers[min];
numbers[min] = numbers[index];
numbers[index] = temp;
}
}
Рекурсивный алгоритм:
public static int findMin(int[] array, int index){
int min = index - 1;
if(index < array.length - 1) min = findMin(array, index + 1);
if(array[index] < array[min]) min = index;
return min;
}
public static void selectionSort(int[] array){
selectionSort(array, 0);
}
public static void selectionSort(int[] array, int left){
if (left < array.length - 1) {
swap(array, left, findMin(array, left));
selectionSort(array, left+1);
}
}
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
Ruby[править]
a = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
for i in 0..a.length - 1
min = i
for j in i + 1..a.length - 1
min = j if a[min] > a[j]
end
a[i], a[min] = a[min], a[i]
end
puts "#{a.join(" ")}"
# output => 1 3 3 5 8 10 11 12 17 20
Python[править]
неустойчивая:
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def select_sort(arr):
i = len(arr)
while i > 1:
max = 0
for j in range(i):
if arr[j] > arr[max]:
max = j
swap(arr, i - 1, max)
i -= 1
устойчивая:
def select_sort_stable(arr):
if len(arr) == 0: return
for j in range(len(arr)):
min = j
for i in range(j + 1, len(arr)):
if arr[i] < arr[min]: min = i
if min != j:
value = arr[min]
for l in range(min, j - 1, -1):
arr[l] = arr[l - 1]
arr[j] = value
Ada[править]
type arr is array(1..n) of integer;
i,j,t:integer;
min:integer;
mas1:arr;
begin
for i in 1..n-1 loop
min:=i;
for j in i+1..n loop
if mas1(min)>mas1(j) then
min:=j;
end if;
end loop;
t:=mas1(i);
mas1(i):=mas1(min);
mas1(min):=t;
end loop;
end sort;
PHP[править]
$size = count($arr);
for ($i = 0; $i < $size-1; $i++)
{
$min = $i;
for ($j = $i + 1; $j < $size; $j++)
{
if ($arr[$j] < $arr[$min])
{
$min = $j;
}
}
$temp = $arr[$i];
$arr[$i] = $arr[$min];
$arr[$min] = $temp;
}
TurboBasic 1.1[править]
CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
FOR X = 1 TO N
Y[X] = X
PRINT Y[X];
NEXT X:PRINT
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
PRINT " SLUCHAINYE CHISLA"
FOR X = 1 TO N
YD=Y[X]
XS=INT(RND*N)+1
PRINT XS;
Y[X]=Y[XS]
Y[XS]=YD
NEXT X:PRINT
PRINT " PEREMESHANNYJ MASSIV"
FOR X=1 TO N
PRINT Y[X];
NEXT X:PRINT
'ALGORITM "SORTIROVKA VYBOROM" O(N^2)
L=1
R=N
MTIMER
FOR J=1 TO R-1 STEP 1
MIN=J
FOR I=J+1 TO R STEP 1
IF Y[I] < Y[MIN] THEN MIN=I
NEXT I
IF MIN<>J THEN SWAP Y[J],Y[MIN]
LOCATE 7,1 REM
FOR I=1 TO N:PRINT Y[I];:NEXT I:PRINT REM ANIMATION BLOCK
DELAY 1 REM
NEXT J
T1=MTIMER
PRINT " OTSORTIROVANNYJ MASSIV"
FOR X=1 TO N
'PRINT "Y[X]=";Y[X]
PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1
PRINT FRE(-1)
�
PL/SQL[править]
type sort_list is table of integer index by binary_integer;
-----------------------------------------------------------
function SORT_CHOISE return sort_list
IS
list sort_list;
l_min pls_integer;
l_dummy pls_integer;
begin
for n in 1..100 loop
list(n):=dbms_random.random; -- инициализация массива случайными числами
end loop;
for i in list.first..list.last loop
l_min:=i;
for j in (i + 1)..list.last loop
if (list(j) < list(l_min)) then
l_min := j;
end if;
end loop;
l_dummy:=list(i);
list(i):=list(l_min);
list(l_min) := l_dummy;
end loop;
return list;
end SORT_CHOISE;