Задача 38. Сортировка массива методом поиска максимума

Условие задачи. Отсортировать заданный целочисленный массив по убыванию методом выбора (методом поиска максимума).

Исходные данные представим в виде одномерного массива А из n целых чисел. Результатом будет тот же массив после сортировки.

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

Алгоритм сортировки использует конструкцию вложенных циклов. Правила использования вложенных циклов рассматривались в примерах 25 и 36. Внешний цикл задает количество просмотров массива n-1. При первом просмотре рассматривается часть массива от первого до последнего, при втором - от второго до последнего, при третьем - от третьего до последнего, при i-м просмотре - от i-го до последнего и так далее. Во внешнем цикле выполняются следующие действия:

§ запоминание i-го элемента как максимального;

§ выполнение внутреннего цикла для элементов от i+1 до n, в котором ищется максимальный элемент;

§ перестановка максимального с i-м элементом. Для перестановки местами максимального элемента с i-м необходимо знать номер этого максимального элемента. Поэтому при поиске наибольшего значения среди элементов от i-го до n-го необходимо запоминать его номер.

Введем обозначения:

n - количество элементов массива,

А - массив из n целых чисел,

i - переменная для организации внешнего цикла,

j - переменная для организации внутреннего цикла,

max – значение максимального элемента массива,

imax - номер (индекс) максимального элемента.

Структурированная запись алгоритма 38

1. Ввести количество элементов массива n.

2. Ввести элементы массива А.

3. Повторять для i от 1 до n-1 следующие действия:

3.1. Принять за максимум элемент массива А[i], max= А[i].

3.2. Запомнить номер i в переменной imax, imax=i.

3.3. Повторять для j от i+1 до n

3.3.1. Если А[j] > max то

3.3.1.1. Max=А[j].

3.3.1.2. imax=j.

3.4. Поменять местами элемент A[imax] с элементом А[i].

4. Вывести элементы массива А.

Схема алгоритма

Текст программы на языке Си

#include <stdio.h>

#define N 25

int main (void)

{

int A[N], k, n, i, j, max, imax;

printf("Введите количество элементов n\n");

scanf("%d", &n);

printf("Введите элементы массива А \n");

for (i=0; i<n; i++)

    scanf ("%d", &A[i]);

k=n-1;

for (i=0; i<k; i++)

{

    max= A[i];

   imax= i;

  for (j=i+1; j<n; j++)

     if (A[j]>max)

     {

        imax=j;

        max=A[j];

     }

 A[imax]= A[i];

 A[i]=max;

}

printf ("Отсортированный массив А \n");

for (i=0; i<n; i++)

   printf ("%3d", A[i]);

return 0;

}

Текст программы на языке Паскаль

Program pr_38;

Var a: array of integer;

i,j,n,imax:integer;

max:integer;

begin

writeln('Введите количество элементов');

readln(n);

setlength(a,n);

writeln('Введите элементы массива');

for i:=0 to n-1 do readln(a[i]);

   for i:=0 to n-2 do

begin

max:=a[i];

    imax:=i;

for j:=i+1 to n-1 do

    if a[j]>max then

   begin

     imax:=j;

     max:=a[j];

     end;

    a[imax]:=a[i];

a[i]:=max;

end;

writeln('Отсортированный массив');

 for i:=0 to n-1 do write(a[i]:3);

a:=nil;  

end.