VPF::[Delphi] Сортировка одномерного массива

Phenom

Дата 15.3.2008, 17:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

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

THandle

Дата 15.3.2008, 18:16 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

Вот код юнита главной формы:

Код


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.

Это сообщение отредактировал(а) THandle - 15.3.2008, 18:17

Присоединённый файл ( Кол-во скачиваний: 46 )

sortmaxmin.rar 3,95 Kb

Phenom

Дата 15.3.2008, 20:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

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

Это сообщение отредактировал(а) Phenom - 15.3.2008, 20:44

THandle

Дата 15.3.2008, 20:44 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

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

Phenom

Дата 15.3.2008, 20:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

Сделал вот это

Цитата

Попробуй сам создать проект, разместить компоненты, потом скопируй код с форума

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

Это сообщение отредактировал(а) Phenom - 15.3.2008, 20:56

THandle

Дата 15.3.2008, 21:07 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

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. Вот и происходит обмен.

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

Это сообщение отредактировал(а) THandle - 15.3.2008, 21:08

Phenom

Дата 15.3.2008, 21:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

Кстати мне нужна сортировка по метуду Поиск наименьшего (наибольшего)

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

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

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

Это сообщение отредактировал(а) Phenom - 15.3.2008, 21:16

THandle

Дата 15.3.2008, 21:48 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

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

Phenom

Дата 15.3.2008, 22:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

Хорошо, буду ждать smile

VICTAR

Дата 15.3.2008, 22:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1108
Регистрация: 6.10.2006

Репутация: 2
Всего: 80

Цитата(THandle @ 15.3.2008, 20:44

)

это вот действительно несовместимость семерки и 2007.

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

THandle

Дата 17.3.2008, 13:52 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

Phenom, вот, держи, хотя не знаю тот это алгоритм какой надо или не тот, но по описанию вроде подходит.
Писал так долго, так как - http://forum.vingrad.ru/forum/topic-201047...y1444855/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;

Глючу.

Phenom

Дата 17.3.2008, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

Спасибо за прогу. Сверю с описанием.

Phenom

Дата 18.3.2008, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

THandle, Можешь вкратце алгоритм расписать с вырезками из проги?

Это сообщение отредактировал(а) Phenom - 18.3.2008, 21:18

THandle

Дата 18.3.2008, 21:34 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

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

Это сообщение отредактировал(а) THandle - 18.3.2008, 21:35

Phenom

Дата 19.3.2008, 18:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 10.3.2008

Репутация: нет
Всего: нет

Код


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 и последующее.

Это сообщение отредактировал(а) Phenom - 19.3.2008, 18:27

THandle

Дата 19.3.2008, 19:18 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 30
Всего: 372

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);

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »