Сортировка выбором

Задача

Используя сортировку выбором отсортировать элементы массива по возрастанию.

Пояснение к задаче и алгоритм решения

Сортировка выбором заключается в поиске в каждом проходе по массиву максимального элемента из оставшихся и перемещении его на последнее место в просматриваемой части массива.

В первом проходе просматривается весь массив, во втором - нет смысла просматривать последний элемент, на третьем - два последних опускаются из области поиска и т.д.

Переменной-счетчику внешнего цикла сначала присваивается индекс последнего элемента массива. Цикл выполняется до тех пор, пока индекс не дойдет до первого элемента (не включая его).

Во вложенном цикле осуществляется поиск максимального элемента. Достаточно сохранить в переменной лишь его индекс, а не значение.
После вложенного цикла происходит обмен последнего элемента просматриваемой части массива (на него указывает счетчик внешнего цикла) на найденный максимум.

Исходный код на языке программирования Pascal

const n = 10;
 
var
    arr: array[1..n] of byte;
    max, id, i, j: byte;
 
begin
    randomize;
    for i := 1 to n do begin
        arr[i] := random(100);
        write(arr[i]:4)
    end;
    writeln;
 
    j := n;
 
    while j > 1 do begin
        id := 1;
        for i := 2 to j do
            if arr[i] > arr[id] then
                id := i;
        max := arr[id];
        arr[id] := arr[j];
        arr[j] := max;
        j := j - 1
    end;
 
    for i := 1 to n do
        write(arr[i]:4);
    writeln;
end.

Пример(ы) выполнения программы на языке Pascal

  36  46  32  54  96  40  38   1  95  19
   1  19  32  36  38  40  46  54  95  96

Исходный код на языке программирования C

#include <stdio.h>
#define N 10
main() {
    int a[N];
    int i, id, j, b;
    srand(time(NULL));
    for (i=0; i<N; i++) {
        a[i] = rand()%100;
        printf("%3d", a[i]);
    }
    printf("\n");
 
    j = N-1;
    while (j > 0) {
        id = 0;
        for (i=1; i<=j; i++)
            if (a[i] > a[id]) id = i;
        b = a[id];
        a[id] = a[j];
        a[j] = b;
        j -= 1;
    }
 
    for (i=0; i<N; i++) {
        printf("%3d", a[i]);
    }
    printf("\n");
}

Пример(ы) выполнения программы на языке C

 35 99 51 17 90 79 71 10 11 91
 10 11 17 35 51 71 79 90 91 99

Исходный код на языке программирования Python

from random import random
a = [0]*10
for i in range(10):
    a[i] = int(random()*100)
print(a)
 
j = 9
while j > 0:
    m = 0
    for i in range(1,j+1):
        if a[i] > a[m]:
            m = i
    a[m], a[j] = a[j], a[m]
    j -= 1
 
print(a)

Пример(ы) выполнения программы на языке Python

[43, 86, 86, 51, 99, 21, 66, 26, 56, 8]
[8, 21, 26, 43, 51, 56, 66, 86, 86, 99]

Исходный код на языке программирования КуМир

алг сортировка выбором
нач
  цел N = 10
  цел таб arr[1:N]
  цел m, id, i, j
  нц для i от 1 до N
    arr[i] := int(rand(0,100))
    вывод arr[i],  " "
  кц
  вывод нс
  j := N;
  нц пока j > 1
    id := 1
    нц для i от 2 до j
      если arr[i] > arr[id] то id := i все
    кц
    m := arr[id]
    arr[id] := arr[j]
    arr[j] := m
    j := j - 1
  кц
  нц для i от 1 до N
    вывод arr[i],  " "
  кц
кон

Пример(ы) выполнения программы на языке КуМир

64 34 72 13 65 7 89 68 41 84
7 13 34 41 64 65 68 72 84 89

Исходный код на языке программирования Basic

dim a(10)
for i=0 to 9
        a[i] = int(rand() * 100)
        print a[i] + " ";
next i
print
 
j = 9
while j > 0
        id = 0
        for i=1 to j
                if a[i] > a[id] then
                        id = i
                endif
        next i
        b = a[id]
        a[id] = a[j]
        a[j] = b
        j = j-1
endwhile
 
for i=0 to 9
        print a[i] + " ";
next i

Пример(ы) выполнения программы на языке Basic

30 40 97 73 8 31 87 20 12 7
7 8 12 20 30 31 40 73 87 97

Тема

Массивы

Уровень сложности

Сложный

Дата публикации