Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Delphi] Сортировка одномерного массива


Автор: Phenom 15.3.2008, 17:05
Общее описание
Одномерный массив заполнить с использованием генератора случайных чисел. Алгоритм сортировки реализовать в отдельной процедуре (подпрограмме). 
Для вывода на экран элементов массива до и после сортировки использовать списки ListBox. Так же, найти наибольший и наименьший элементы массива, вывести на экран.
Само задание
Отсортировать массив вещественных чисел по возрастанию методом поиска экстремального.

Автор: THandle 15.3.2008, 18:16
Вот код юнита главной формы:

Код

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    ListBox1: TListBox;
    Button1: TButton;
    ListBox2: TListBox;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

const
  MAX = 10;

type
  TArray = array [1..MAX] of integer;
var
  Form1: TForm1;
  a : TArray;

implementation

{$R *.dfm}
procedure PrintArray(a : TArray; Strings : TStrings);
var
  i : integer;
begin
  if not Assigned(Strings) then
    Exit;
  Strings.Clear;
  for i := 1 to MAX do
    Strings.Add(IntToStr(a[i]));
end;

procedure Swap(var iArray : TArray; iPos1, iPos2 : integer);
var
  tmp : integer;
begin
  tmp := iArray[iPos1];
  iArray[iPos1] := iArray[iPos2];
  iArray[iPos2] := tmp;
end;

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

function MaxI(a : TArray) : integer;
var
  i : integer;
begin
  result := a[1];
  for i := 2 to MAX do
    if a[i] > result then
      result := a[i];
end;

function MinI(a : TArray) : integer;
var
  i : integer;
begin
  result := a[1];
  for i := 2 to MAX do
    if a[i] < result then
      result := a[i];
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i : integer;
begin
  for i := 1 to MAX do
    a[i] := random(1000);//к примеру:)
  PrintArray(a, ListBox1.Items);
  BubbleSort(a);
  PrintArray(a, ListBox2.Items);
  ShowMessage('Максимальный элемент: ' + IntToStr(MaxI(a)));
  ShowMessage('Минимальный элемент: ' + IntToStr(MinI(a)));
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
end;

end.



На форме два ListBox и один Button.

На всякий пожарный в аттаче сам проект. Написан в Delphi 2007.

Автор: Phenom 15.3.2008, 20:22
При компиляции возникает ошибка
Undeclared identifier:'MainFormOnTaskbar'
У меня дельфи 7

Автор: THandle 15.3.2008, 20:44
Phenom, так... это вот действительно несовместимость семерки и 2007. Во втрой теме уже такое наблюдаю))) Есть два варианта в твоём случае:
1. Попробуй сам создать проект, разместить компоненты, потом скопируй код с форума,
 затем поприсваивай компонентам нужные методы(Button1Click, Form1Create) и запускай, если что то еще пиши сюда.
2. Я ставлю Делфи 7 и делаю тебе проект smile  

Автор: Phenom 15.3.2008, 20:54
Сделал вот это 
Цитата

Попробуй сам создать проект, разместить компоненты, потом скопируй код с форума
, Прога робит но пишит Variable tmp is declared but never used in BubbleSort
Дак зачем там tmp? (строчка 56)

Автор: THandle 15.3.2008, 21:07
Phenom, это пузырьковая сортировка smile 

Ну давай попробую доказать что tmp там нужен smile 

Есть у нас некий массив.
нам нужно поменять два его элемента местами.

Вот так там реализовано:

Код

procedure Swap(var iArray : TArray; iPos1, iPos2 : integer);
var
  tmp : integer;
begin
  tmp := iArray[iPos1];
  iArray[iPos1] := iArray[iPos2];
  iArray[iPos2] := tmp;
end;


а если убрать tmp?

Код

procedure Swap(var iArray : TArray; iPos1, iPos2 : integer);
begin
  iArray[iPos1] := iArray[iPos2];
  iArray[iPos2] := iArray[iPos1];
end;


Получается что мы сначала ставим на место с индексом iPos1 данные из элемента с индексом iPos2. Далее нам надо перебросить данные из элемента iPos1 в iPos2, но как? ведь в iPos1 находится теперь то же самое что и в iPos2. так что же получается? мы не поменяли местами, а просто присвоили двум элементам одно и то же значение.

tmp хранит в себе промежточное значение из элемента ipos1, и после обмена первого на второе, все еще продолжает содержать предыдущие данные. После этого на позиию iPos2 встают старые данные из iPos1, содержащиеся теперь в tmp, так как в iPos1 уже лежат другие данные, а конкретно из элемнтп iPos2. Вот и происходит обмен.

 Надеюсь, что понятно выразился?

Автор: Phenom 15.3.2008, 21:14
Кстати мне нужна сортировка по метуду  Поиск наименьшего (наибольшего) 

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

В модифицированном варианте метода выбранные элементы пересылаются в другой массив. При этом исходный массив не изменяется, но при очередном цикле выбора ищется не безусловно максимальный (минимальный) элемент, а элемент, больший (меньший) всех, но меньший (больший) элемента, выбиравшегося на предыдущем шаге. 

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

Автор: THandle 15.3.2008, 21:48
Phenom, никогда не слышал о такой сортировке(может слышал, но под другим нажванием), но ничего сложного в ней не вижу. Сейчас попробую написать. Результат сегодня не гарантирую, так как поздно уже, времени много.

Автор: Phenom 15.3.2008, 22:08
Хорошо, буду ждать smile 

Автор: VICTAR 15.3.2008, 22:15
Цитата(THandle @  15.3.2008,  20:44 Найти цитируемый пост)
это вот действительно несовместимость семерки и 2007. 

Ребят, вы чего? 
Project -> View Source
Убираем строчку Application.MainFormOnTaskbar := True;

Автор: THandle 17.3.2008, 13:52
Phenom, вот, держи, хотя не знаю тот это алгоритм какой надо или не тот, но по описанию вроде подходит.
Писал так долго, так как - http://forum.vingrad.ru/forum/topic-201047/anchor-entry1444855/0.html


Код

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    ListBox1: TListBox;
    ListBox2: TListBox;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
const
  MAX = 5;

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


procedure PrintArray(a : TArray; Strings : TStrings);
var
  i : integer;
begin
  if not Assigned(Strings) then
    Exit;
  Strings.Clear;
  for i := 1 to MAX do
    Strings.Add(IntToStr(a[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;  

function MaxI(a : TArray) : integer;
var
  i : integer;
begin
  result := a[1];
  for i := 2 to MAX do
    if a[i] > result then
      result := a[i];
end;

function MinI(a : TArray) : integer;
var
  i : integer;
begin
  result := a[1];
  for i := 2 to MAX do
    if a[i] < result then
      result := a[i];
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  i : integer;
begin
  for i := 1 to MAX do
    a[i] := random(1000);//к примеру:)
  PrintArray(a, ListBox1.Items);
  MaxSort(a);
  PrintArray(a, ListBox2.Items);
  ShowMessage('Максимальный элемент: ' + IntToStr(MaxI(a)));
  ShowMessage('Минимальный элемент: ' + IntToStr(MinI(a)));
end;

end.


Добавлено через 56 секунд
Цитата(VICTAR @  15.3.2008,  22:15 Найти цитируемый пост)
Ребят, вы чего? 
Project -> View Source
Убираем строчку Application.MainFormOnTaskbar := True; 


Глючу. smile 

Автор: Phenom 17.3.2008, 17:54
Спасибо за прогу. Сверю с описанием.

Автор: Phenom 18.3.2008, 21:17
THandle, Можешь вкратце алгоритм расписать с вырезками из проги?

Автор: THandle 18.3.2008, 21:34
Phenom, алгоритм реализован в процедуре 

Код

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 нужен что бы его можно было изменять).

Код

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

Автор: Phenom 19.3.2008, 18:15
Код

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


procedure PrintArray(a : TArray; Strings : TStrings);
var
  i : integer;
begin
  if not Assigned(Strings) then
    Exit;
  Strings.Clear;
  for i := 1 to MAX do
    Strings.Add(IntToStr(a[i]));
end;

Можно ещё вот это пояснить.
Особенно Assigned и последующее.

Автор: THandle 19.3.2008, 19:18
Phenom, это уже, имхо, отход в сторону от темы.

Поясню вкратце:

Тебе ведь нужно все в listbox вносить? Точнее в его items, а эти items имеют как раз то тип TStrings, поэтому второй параметр этой процедуры как раз такого типа.(с первым я думаю всё понятно - это наш массив).


Код

  if not Assigned(Strings) then
    Exit;


проверяет создано ли Strings. Если создано, то продолжаем работу, иначе выходим из процедуры. Я бы лично предпочел бы поднимать тут исключение, но я думаю тебе это не подойдет, так как не проходили скорее всего.
Впринципе если ListBox ты кладешь в Design-time можно и не делать этой проверки, но всё лучше сделать.

Цитата(Phenom @  19.3.2008,  18:15 Найти цитируемый пост)
Strings.Clear;

Тут мы очищаем Strings от всякого мусора(если он там конечно есть).


Код

  for i := 1 to MAX do
    Strings.Add(IntToStr(a[i]));


Тут мы все элементы нашего массива добавляем в Strings.

А так кк вызываем мы эту процедуру так:

В первый раз(до сортировки):
Код

  PrintArray(a, ListBox1.Items);


То весь массив будет добавлен в ListBox1.Items.

Далее мы массив сортируем:

Код

 MaxSort(a);


А теперь все элементы массива "распечатываем" в ListBox2.Items:

Код

  PrintArray(a, ListBox2.Items);

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)