Реализации алгоритмов/Сортировка/Выбором
(перенаправлено с «Примеры реализации сортировки выбором»)
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;
}
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++;
}
}
}
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;
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;
}
}
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
Итерационный алгоритм:
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;
}
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
неустойчивая:
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
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;
$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;
}
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)
�
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;