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

Книга адресована школьникам средних и старших классов, желающим испытать себя в «олимпийских схватках». Может быть полезна студентам-первокурсникам и преподавателям информатики.

Модераторы: Oleg_D, Модераторы

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

Сообщение Paster Fob » 15.06.2013 10:32:41

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

Код: Выделить всё
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.


Кто здесь прав и какой алгоритм верный?
Аватара пользователя
Paster Fob
постоялец
 
Сообщения: 188
Зарегистрирован: 22.02.2011 21:53:36
Откуда: Новосибирск.

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

Сообщение trengtor » 16.06.2013 10:31:28

А посмотреть в 3-м томе у Кнута никак?
Аватара пользователя
trengtor
новенький
 
Сообщения: 77
Зарегистрирован: 03.05.2013 08:57:43
Откуда: Москва

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

Сообщение Oleg_D » 16.06.2013 12:16:02

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

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

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

Сообщение Mirage » 16.06.2013 14:54:25

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

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

Сообщение Oleg_D » 08.07.2013 08:48:55

В редакции 12.6 процедура сортировки SelectionSort переименована в FarmSort (фермерская сортировка).
Oleg_D
постоялец
 
Сообщения: 390
Зарегистрирован: 09.05.2011 11:28:36


Вернуться в Книга "Песни о Паскале"

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6

Рейтинг@Mail.ru