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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
→‎К переименованию: Использован шаблон.
Строка 1: Строка 1:
{{К переименованию | 2014-05-02 | Реализации алгоритмов/Сортировка/Выбором}}

{{wikipedia|Сортировка выбором}}
{{wikipedia|Сортировка выбором}}
== [[w:Си (язык программирования)|C]] ==
== [[w:Си (язык программирования)|C]] ==
Строка 187: Строка 189:


min = i
min = i

for j in i + 1..a.length - 1
for j in i + 1..a.length - 1


Строка 209: Строка 211:
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]

def select_sort(arr):
def select_sort(arr):
i = len(arr)
i = len(arr)
Строка 229: Строка 231:
for i in xrange(j+1, len(arr)):
for i in xrange(j+1, len(arr)):
if(arr[i] < arr[min]): min = i
if(arr[i] < arr[min]): min = i
if(min != j):
if(min != j):
value = arr[min]
value = arr[min]
for l in xrange(min, j-1,-1):
for l in xrange(min, j-1,-1):
Строка 241: Строка 243:
i,j,t:integer;
i,j,t:integer;
min:integer;
min:integer;
mas1:arr;
mas1:arr;
begin
begin
for i in 1..n-1 loop
for i in 1..n-1 loop
Строка 272: Строка 274:
}
}
}
}

$temp = $arr[$i];
$temp = $arr[$i];
$arr[$i] = $arr[$min];
$arr[$i] = $arr[$min];

Версия от 19:36, 2 мая 2014

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;
                    }
                }

                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 xrange(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 xrange(len(arr)):
        min = j
        for i in xrange(j+1, len(arr)):
            if(arr[i] < arr[min]): min = i
	if(min != j):
            value = arr[min]
            for l in xrange(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; $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)