Реализации алгоритмов/Сортировка/Выбором: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 43: Строка 43:
public void SelectionSort(int[] arr)
public void SelectionSort(int[] arr)
{
{
int length = arr.Length;
int min, temp;
for (int i = 0; i < length - 1; ++i)
int length = array.Length;

{
int minInd = i;
for (int i = 0; i < length - 1; i++)
int minVal = arr[minInd];
for (int j = i + 1; j < length - 1; ++j)
{
if (minVal > arr[j])
{
{
minInd = j;
min = i;

minVal = arr[minInd];
for (int j = i + 1; j < length; j++)
{
if (array[j] < array[min])
{
min = j;
}
}

temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
// if (minVal != arr[i]) // при устойчивой сортировке
// {
arr[minInd] = arr[i];
arr[i] = minVal;
// }
}
}
</source></big>
</source></big>

Версия от 16:32, 15 апреля 2013

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 = array.Length;

            for (int i = 0; i < length - 1; i++)
            {
                min = i;

                for (int j = i + 1; j < length; j++)
                {
                    if (array[j] < array[min])
                    {
                        min = j;
                    }
                }

                temp = array[i];
                array[i] = array[min];
                array[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 xrange(i):
            if arr[j] > arr[max]:
                max = j
        swap(arr, i - 1, max)
        i -= 1

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; $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)