Рейтинг@Mail.ru
Menu
Скачать картинки на телефон бесплатно.
Заставки для телефона, аватарки.
(Вырезать из фотографии)

Роза `Гренд Могул` Яхта `Алиса` Лесное озеро Музей `Пирогово` Белочка
Выберите рубрику (тему)

Сортировка массивов

Программирование на Паскале
Программа 5

Упорядочить по убыванию методом вставки те элементы каждой строки матрицы, которые расположенные между минимальным и максимальным элементами.


Алгоритм в виде диаграммы действий


Сортировка массивов. Программа 5. Упорядочить по убыванию методом вставки те элементы каждой строки матрицы, которые расположенные между минимальным и максимальным элементами.. Алгоритм в виде диаграммы действий


Текст программы


program Prg5;



{ http://nataliya.kiev.ua/?id=105 }



uses


  crt;

type


  TMatrix = array[1..15, 1..15] of integer;

 

procedure InputMatrix(var a: tMatrix; m, n: byte);


 
var

    i, j: byte;
    q: char;
 
begin

    WriteLn('Input by hand? (y/n)');
    ReadLn(q);
    Randomize;
   
for i := 1 to m do

      for j := 1 to n do
        if (q <> 'y') and (q <> 'Y') then
          a[i, j] := Random(99)
        else
          begin
            Write('A[', i, ',', j, ']=');
            ReadLn(a[i, j]);
          end;
  end;

 

procedure OutputMatrix(const a: TMatrix; m, n: byte);


 
var

    i, j: byte;
 
begin

   
for i := 1 to m do

      begin
        for j := 1 to n do
          Write(a[i, j]:4);
        WriteLn;
      end;
  end;

 

procedure MinMax(const a: TMatrix; m, n, i: byte; var j1, j2: byte);


 
var

    j: byte;
    Min, Max: integer;
 
begin

    j1 := 1;
    j2 := 1;
    Min := a[i, 1];
    Max := a[i, 1];
   
for j := 1 to n do

      begin
        if a[i, j] < min then
          begin
            min := a[i, j];
            j1 := j;
          end;
        if a[i, j] > max then
          begin
            max := a[i, j];
            j2 := j;
          end;
      end;
    if j1 > j2 then
      begin
        j := j1;
        j1 := j2;
        j2 := j;
      end;
  end;

 

procedure Sort(var a: TMatrix; m, n, l, j1, j2: byte);


 
var

    i, j: byte;
    b: integer;
 
begin

   
for i := j2 downto j1 do

      begin
        b := a[l, i];
        j := i;
        while (a[l, j + 1] > b) and (j < j2) do
          begin
            a[l, j] := a[l, j + 1];
            j := j + 1;
          end;
        a[l, j] := b;
      end;
  end;

 

procedure Main(var a: tmatrix; m, n: byte);


 
var

    i, j, j1, j2: byte;
 
begin

   
for i := 1 to m do

      begin
        MinMax(a, m, n, i, j1, j2);
        Sort(a, m, n, i, j1, j2);
      end;
  end;

var


  Matrix: TMatrix;
  m, n: byte;

begin


  ClrScr;
  Write('m=');
  ReadLn(m);
  Write('n=');
  ReadLn(n);
  InputMatrix(Matrix, m, n);
  OutputMatrix(Matrix, m, n);
  Main(Matrix, m, n);
  WriteLn('Result:');
  OutputMatrix(Matrix, m, n);
  ReadLn;
end.

Print

Печатать текст программы!



Source code: «Сортировка массивов».

Редактировать, копировать

(WYSIWYG редактор «NicEdit»)
Загрузить файл с текстом программы: «Сортировка массивов». Печатать текст программы!

Загрузить файл с текстом программы

(Prg5.pas - Windows-1251)

Результат работы программы


1)
m=6
n=12
Input by hand? (y/n)
n
  94 66 26 35 49 98 91 30 89 32 56 73
  14 62 27 66 59 59 11 49 78 66 57 73
  18 69 2 71 80 28 69 96 40 14 40 12
  36 87 97 74 57 18 20 13 14 35 60 19
  45 44 57 85 2 69 50 74 26 91 88 84
  87 90 83 61 74 28 16 65 38 14 6 94
Result:
  94 66 98 49 35 26 91 30 89 32 56 73
  14 62 27 66 59 59 78 49 11 66 57 73
  18 69 96 80 71 69 28 2 40 14 40 12
  36 87 97 74 57 20 18 13 14 35 60 19
  45 44 57 85 91 74 69 50 26 2 88 84
  87 90 83 61 74 28 16 65 38 14 94 6

2)
m=5
n=5
Input by hand? (y/n)
y
A[1,1]=1
A[1,2]=2
A[1,3]=3
A[1,4]=4
A[1,5]=1
A[2,1]=0
A[2,2]=1
A[2,3]=6
A[2,4]=2
A[2,5]=8
A[3,1]=1
A[3,2]=1
A[3,3]=2
A[3,4]=3
A[3,5]=4
A[4,1]=5
A[4,2]=6
A[4,3]=1
A[4,4]=3
A[4,5]=0
A[5,1]=1
A[5,2]=5
A[5,3]=10
A[5,4]=0
A[5,5]=22
   1 2 3 4 1
   0 1 6 2 8
   1 1 2 3 4
   5 6 1 3 0
   1 5 10 0 22
Result:
   4 3 2 1 1
   8 6 2 1 0
   4 3 2 1 1
   5 6 3 1 0
   1 5 10 22 0

Теория к программе


Сортировка массивов



 

Методы сортировки

можно разбить в соответствии с определяющими их принципами на три основные группы:

    1.
Сортировка с помощью вставки (by Іnsertіon) или с помощью включения

    2.
Сортировка с помощью выбора (by Selectіon) или с помощью выделения

    3.
Сортировка с помощью обмена (by Exchange) или пузырьковая
.

  Каждая группа имеет прямой метод (самый простой) и улучшенный(усложненный) методы сортировки

 

I. Сортировка с помощью вставки



 
Принцип сортировки
:

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

При этом надо:

    1.
Найти место, куда нужно вставить этот элемент

    2.
Сдвинуть элементы, которые стоят справа в отсортированной части, на одну позицию вправо
.
    3.
На освобожденное место поставить элемент, который анализируется(вставляется)
.

 
Два способа выполнения этих действий
:

    1)
каждый следующий элемент сравнивается с элементами в отсортированной части
, находится место вставки, все следующие элементы сдвигаются на одну позицию вправо и после этого вставляется элемент;
    2)
элемент, который вставляется, последовательно, слева направо, сравнивается с любым из элементов в отсортированной части
. Если нужно, элемент в отсортированной части сразу сдвигается на одну позицию вправо. Как только найдено нужное место вставки, элемент, который анализируется, вставляется на нужную позицию.

 

II. Сортировка с помощью прямого выбора



Принцип сортировки
:

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

 

III. Сортировка с помощью прямого обмена (пузырьковая)



Принцип сортировки
:

слева направо поочередно направляется сравнение двух соседних элементов
.
Если они не упорядочены между собою, то меняются местами
.
В базовом алгоритме прохождения массива и очередное приведение в порядок
повторяются n-1 раз
.


Дата: 2007-10-20   Автор: Admin
Случайный анекдот

Идет лекция по математике, в аудитории лектор и 3 студента. Внезапно встают 5 человек и уходят. Лектор:
- Вот сейчас придут еще двое, и вообще никого не останется.
Дата: 22-07-2004   Автор: Admin   Подрубрика: Лекции