Перейти к содержанию

Реализации алгоритмов/Сортировка/Выбором

Материал из Викиучебника — открытых книг для открытого мира
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;

Ссылки

[править]