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

[Paster Fob]

Добрый день Олег Виленович.Как-то на просторах инета один студент попросил помощи решить задачу "Отсортировать массив по возрастанию сортировкой выбором". Я написал код и отправил ему.

Код: Выделить всё

const
  n=20;

type
  tarray=array [1..20] of shortint;

var
  arr:tarray;

procedure CreateArray;
var
  i:byte;
begin
  for i:=1 to n do
    arr[i]:=random(61)-10;
end;

procedure PrintArray;
var
  i:byte;
begin
  for i:=1 to n do
    write(arr[i],' ');
  writeln; writeln;
end;

procedure SelectionSort;
var
  l,r,t:byte;
begin
  for l:=1 to n-1 do
    for r:=n downto l+1 do
      if arr[l]>arr[r] then begin
        t:=arr[l];
        arr[l]:=arr[r];
        arr[r]:=t;
        end;
end;

begin
  randomize;
  CreateArray;
  writeln('До сортировки : ');
  writeln;
  PrintArray;
  SelectionSort;
  writeln('После сортировки : ');
  writeln;
  PrintArray;
  readln;
end.

Но препод не принял моё решение и сказал что это не та сортировка.
В книгах и на различных сайтах нашёл нужный алгоритм,но он не тот что был в книге.
Вот как выполнена сортировка выбором:

Код: Выделить всё

const
  n=20;

type
  tarray=array [1..20] of shortint;

var
  arr:tarray;

procedure CreateArray;
var
  i:byte;
begin
  for i:=1 to n do
    arr[i]:=random(61)-10;
end;

procedure PrintArray;
var
  i:byte;
begin
  for i:=1 to n do
    write(arr[i],' ');
  writeln; writeln;
end;

procedure SelectionSort;
var
  i,j,m,t:integer;
begin
  for i:=1 to n-1 do begin
    m:=i;
    t:=arr[i];
    for j:=i+1 to n do
      if t>arr[j] then begin
        m:=j;
        t:=arr[j];
      end;
    arr[m]:=arr[i];
    arr[i]:=t;
  end;
end;

begin
  randomize;
  CreateArray;
  writeln('До сортировки : ');
  writeln;
  PrintArray;
  SelectionSort;
  writeln('После сортировки : ');
  writeln;
  PrintArray;
  readln;
end.

Кто здесь прав и какой алгоритм верный?

[trengtor]

А посмотреть в 3-м томе у Кнута никак?

[Oleg_D]

Кто здесь прав и какой алгоритм верный?

Препод прав, конечно. Тут у меня ошибочка: надо найти другое название тому методу, что придумал Лефт.
Сортировка выбором делает меньше обменов, чем метод Лефта, и при желании там можно ещё сократить фиктивные обмены. Но настоящий SelectionSort был бы не удобен Райту: ему пришлось бы запастись ещё карандашом и бумагой, чтобы запоминать положение арбуза с минимальным весом в оставшейся не отсортированной части массива.
На практике для больших объёмов данных чаще применяют QuickSort, а упрощённые алгоритмы – для небольших массивов, и там разница в скорости разных методов несущественна.

[Mirage]

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

[Oleg_D]

В редакции 12.6 процедура сортировки SelectionSort переименована в FarmSort (фермерская сортировка).