Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [FAQ][Pascal|VB]Сортировка массива поиском наибольшего(наименьшего)

Автор: THandle 20.3.2008, 17:15

Рассмотрим реализацию алгоритма сортировки поиском наибольшего.

Описание:

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

Пример на Паскале:

Код


program Project1;


const
  MAX = 5;

type
  TArray = array [1..MAX] of integer;

procedure PrintArray(iArray : TArray);
var
  i : integer;
begin
  for i := 1 to MAX do
    WriteLn(iArray[i]);
end;


procedure MaxSort(var iArray : TArray);
var
  i, j, pmax, tmp : integer;
begin
  for i := 1 to MAX do
    begin
      pmax := i;
      for j := i+1 to MAX  do
        if iarray[j] > iarray[pmax] then
          pmax := j;
      tmp := iarray[i];
      iarray[i] := iarray[pmax];
      iarray[pmax] := tmp;
    end;
end;  

var
  IArray : TArray;
  i : integer;
begin
  for i := 1 to MAX do
    begin
      write('Enter element: ');
      readln(iArray[i]);
    end;
  PrintArray(IArray);
  MaxSort(IArray);
  writeln('After sort: ');
  PrintArray(IArray);
  readln;
end.

Пример на Visual Basic:

Код


Option Base 1
Const Max = 5
Dim A(1 To Max) As Long

Sub MaxSort(ByRef Arr() As Long)
  Dim I, J, PMax, Tmp As Long
  For I = 1 To Max
    PMax = I
    For J = I + 1 To Max
      If Arr(J) > Arr(PMax) Then PMax = J
    Next J
      Tmp = Arr(I)
      Arr(I) = Arr(PMax)
      Arr(PMax) = Tmp
  Next I
End Sub

'Пример использования - по нажатию кнопки
Private Sub Command1_Click()
  For I = 1 To Max
    A(I) = CLng(InputBox("Введите элемент:"))
  Next I
  Call MaxSort(A)
  'Массив отсортирован. Можно вывести данные, например, в ListBox
  For I = 1 To Max
    List1.AddItem CStr(A(I))
  Next I
End Sub

Теперь посмотрим как всё это работает(используя пример на Паскале).

Алгоритм сортировки реализован в процедуре:

Код


procedure MaxSort(var iArray : TArray);
var
  i, j, pmax, tmp : integer;
begin
  for i := 1 to MAX do
    begin
      pmax := i;
      for j := i+1 to MAX  do
        if iarray[j] > iarray[pmax] then
          pmax := j;
      tmp := iarray[i];
      iarray[i] := iarray[pmax];
      iarray[pmax] := tmp;
    end;
end;

В качестве единственного параметра в процедуру передается изменяемый массив.

Код


for i := 1 to MAX do

В цикле от 1 до константы MAX(объявлена ранее) делаем следующее:

Код


pmax := i;

pmax это у нас индекс максимального числа в массиве на проходе i.
каждый раз мы ему присваиваем минимально возможное значение, то етсть i.

Код


      for j := i+1 to MAX  do
        if iarray[j] > iarray[pmax] then
          pmax := j;

тут мы находим индекс максимального элемента массива на данном проходе.
В переменной pmax находится этот самый индекс.
Главное заметьте, что в цикле мы идем не с 1, а с i, то есть как бы разделяем массив на упорядоченную часть и не упорядоченную.

Код


      tmp := iarray[i];
      iarray[i] := iarray[pmax];
      iarray[pmax] := tmp;

ставим на место i-ного элемента в упорядоченной части максимальный элемент, который находится в pmax. а элемент с индексом i переносим на место максимального элемента.

Всё.

Вот небольшой пример как будет сортироваться следующий массив:

Код


1 5 8 3 6

Это неупорядоченный массив из 5 элементов.

1 шаг сортировки:

Код


8 5 1 3 6

2 шаг сортировки:

Код


8 6 1 3 5

3 шаг сортировки:

Код


8 6 5 3 1

4 шаг сортировки:

Код


8 6 5 3 1

получаем на выходе следующий отсортированный массив:

Код


8 6 5 3 1

Авторы:
http://vingrad.ru/@Rrader - пример на VB.
http://vingrad.ru/@THandle - всё остальное smile

Идея появилась на основе следующей темы:
http://forum.vingrad.ru/forum/topic-200813/0.html