Задача Сортировка 3

Задача

В неупорядоченном массиве могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу. Полученый масив отсортировать методом простого выбора.

Решение

Программа

uses crt;
type MyArray = array [1..100] of integer;
var n:integer;
    a:MyArray;

procedure InPut(var a:MyArray; n:integer);  {Вводим массив}
var i:integer;
begin
  for i:=1 to n do
  begin
    write('a[',i,']=');
    readln(a[i]);
  end;
end;

procedure OutPut(var a:MyArray; n:integer);   {Выводим массив}
var i:integer;
begin
  for i:=1 to n-1 do write(a[i],' ');
  writeln(a[n]);
end;

procedure Sort(var a:MyArray; n:integer); {Сортируем массив}
var i,j,k,temp:integer;
begin
 for i:= n downto 2 do
  begin
    k:=i;                                {считаем что элемент i максимален}
    for j := 1 to i do                   {находим максимальный элемент}
      if a[k] < a[j] then k:=j;
    writeln('Меняем максимальный a[',k,']=',a[k],' и последний a[',i,']=',a[i]);
    temp:=a[i];
    a[i]:=a[k];
    a[k]:=temp;
    OutPut(a,n);     {выводим массив после очередного этапа сортировки}
  end;
end;

procedure Del_ident(var a:MyArray;var n:integer);
var i,j,k:integer;
begin
 i:=1;
 while (i<n) do
 begin
   j:=i;
   k:=0;
   while (j<n) do
   begin
     Inc(j);
     if a[i]=a[j+k] then
      begin
       Inc(k);
       Dec(j);
      end
     else a[j]:=a[j+k];
   end;
   n:=n-k;
   Inc(i);
 end;
end;

begin
  clrscr;
  write('Введите количество элементов массива n:');
  readln(n);
  InPut(a,n);
  writeln('== Исходный массив ==');
  OutPut(a,n);
  writeln('== После удаления одинаковых ==');
  Del_ident(a,n);
  OutPut(a,n);
  writeln('== Сортировка ==');
  Sort(a,n);
  writeln('== Отсортированый массив ==');
  OutPut(a,n);
  readln;
end.

Примеры работы

Пример №1

Введите количество элементов массива n:7
a[1]=7
a[2]=5
a[3]=2
a[4]=5
a[5]=4
a[6]=7
a[7]=1
== Исходный массив ==
7 5 2 5 4 7 1
== После удаления одинаковых ==
7 5 2 4 1
== Сортировка ==
Меняем максимальный a[1]=7 и последний a[5]=1
1 5 2 4 7
Меняем максимальный a[2]=5 и последний a[4]=4
1 4 2 5 7
Меняем максимальный a[2]=4 и последний a[3]=2
1 2 4 5 7
Меняем максимальный a[2]=2 и последний a[2]=2
1 2 4 5 7
== Отсортированый массив ==
1 2 4 5 7

Пример №2

Введите количество элементов массива n:5
a[1]=2
a[2]=1
a[3]=2
a[4]=3
a[5]=1
== Исходный массив ==
2 1 2 3 1
== После удаления одинаковых ==
2 1 3
== Сортировка ==
Меняем максимальный a[3]=3 и последний a[3]=3
2 1 3
Меняем максимальный a[1]=2 и последний a[2]=1
1 2 3
== Отсортированый массив ==
1 2 3