Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Сортування даних, пошук екстремальних значень. Аналіз характеристик алгоритмів ЦОСЗ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2003
Тип роботи:
Лабораторна робота
Предмет:
Обробка сигналів
Група:
КСМ-52
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет „Львівська політехніка”
кафедра ЕОМ
Лабораторна робота №2
з курсу: „Алгоритми і засоби цифрової обробки сигналів”
Тема: „Сортування даних, пошук екстремальних значень. Аналіз характеристик алгоритмів ЦОСЗ”
Львів – 2003 р.
Мета роботи: Вивчення алгоритмів швидкого сортування даних згідно з заданим законом, пошуку екстремальних значень даних. Дослідження часової і об’ємної (за об’ємом па’мяті) складності алгоритмів сортування і області їх застосування.
№
Завдання
33
Вставити нові елементи у відсортовану за неспаданням послідовність Integer:
а) довжина послідовності - 1024, 32788 елементів;
б) послідовність генерувати функцією Random;
в) час роботи програми вимірювати функцією GetTime;
Теоретичні відомості
Складовою частиною більшості алгоритмів ЦОСЗ є процедури сортування, перестановки даних. До них відносяться:
а) сортування елементів по зростанню/спаданню;
б) перестановка елементів масиву по закону двійкової інверсії;
в) розділення масиву на парні і непарні елементи.
Характеристики виконання цих процедур впливають на ефективність алгоритмів ЦОСЗ в целому. Оскільки для розв’язання задач сортування і перестановки даних існують алгоритми різного типу, необхідно, в залежності від вихідних даних і умов задачі вибрати найефективніші за комплексним критерієм "швидкодія – об’єм використаної пам’яті".
Алгоритми сортування даних.
Серед відомих алгоритмів сортування даних по зростанню/спаданню значень елементів виділяють:
а) сортування "вичерпуванням";
б) сортування методом "бульбашки";
в) сортування злиттям.
Оптимальне застосування кожного з цих алгоритмів залежить від значень елементів даних, які необхідно відсортувати і умов виконання задачі.
Сортування "вичерпуванням".
Алгоритм з обчислювальною складністю N; можна застосовувати тільки до даних з малим динамічним діапазоном. Для побудови алгоритму необхідно створити масив вказівників розміром, який рівний динамічному діапазону вхідних даних. Hаприклад, для елементів даних розміром один байт необхідно створити масив вказівників на 256 елементів.
Опис алгоритму:
1) вибрати біжучий елемент (зі значеням L) з вхідного масиву даних;
2) проаналізувати значення елемента з адресою L в масиві вказівників;
3) якщо значення вказівника L є нульовим, то записати туди зсилку на біжучий елемент вхідного масиву, а в біжучий елемент записати 0;
4) якщо значення ненульове, то аналізувати ланцюг зсилок поки не буде знайденне «0» значення;
5) в комірку з знайденим «0» записати зсилку на біжучий елемент, а в біжучу комірку записати «0»;
6) перейти на обробку наступного елемента.
В результаті роботи алгоритму створюються два масиви зсилок: первинний і вторинний (створений з вхідного масиву). Вторинний масив необхідний при необхідності відновлення початкової послідовності При відсутності такої необхідності алгоритм спрощується. Добавлення нових елементів до відсортованих зводиться до прослідковування ланцюжка зсилок або додавання «1» до значення елемента в первинному масиві (в спрощеному варіанті).
Сортування методом "бульбашки".
Один з найпростіших для реалізації алгоритмів, обчислювальна складність якого N2 . Він може бути застосований при сортуванні даних довільного динамічного діапазону.
Опис алгоритму.
1) вибрати біжучий елемент;
2) порівняти його з останнім відсортованим елементом;
3) зупинитися, якщо результат порівняння відповідає умові сортування і перейти на п.1);
4) якщо результат порівняння не відповідає умові сортування, поміняти елементи місцями і перейти на п.2.
По даному алгоритму приходиться рухатися по відсортованому масиві вверх, до пір, поки не буде знайдене місце для біжучого елемента. Тому однозначно оцінити час роботи неможливо, в гіршому випадку він пропорційний N2.
Сортування злиттям.
Алгоритм сортування злиттям має структуру швидких алгоритмів і зводиться до розбиття вхідного масиву розміром N на два підмасиви розміром N/2. Дроблення продовжується до тих пір, поки не залишаться два елементи (вхідна послідовність розбивається на пари). Елементи пари порівнююються між собою і, при необхідності, в залежності від умов сортування, міняються місцями. Таким чином створюється множина відсортованих масивів, які на наступному кроці зливаються попарно між собою і утворюють спільний масив подвійної розмірності. Злиття продовжується до утворення загального масиву. Обчислювальна складність алгоритму пропорційна N*log2(N). Його використання ефективне при сортуванні послідовностей розміром 2b.
Перестановка елементів масиву по закону двійкової інверсії.
Двійково інверсна перестановка вхідних даних застосовується в більшості швидких алгоритмів тригонометричних перетворень сигналів. Двійково інверсним числом до заданого є число, в двійковому представленні якого біти дзеркально відображені по відношенню до вихідного. Тут суттєву роль відіграє динамічний діапазон можливих значень, тобто розмір вхідної послідовності, яка піддається інвертуванню.
Приклад. Знайти двійково-інверсні числа дла числа 26 в різних розрядних сітках (b-кількість бітів для представлення числа).
b
26
двійково-інверсне число
5
11010
01011
11
6
011010
010110
22
7
0011010
0101100
44
8
00011010
01011000
88
Варіант алгоритму двійкової інверсії:
1) присвоїти адресам біжучого елемента (i) і його двійково-інверсного образу (j) нульові значення;
2) якщо i < j, провести перестановку;
3) k = N / 2;
4) поки k (j то j = j - k, a k = k / 2;
5) j = j + k;
6) i = i + 1;
7) якщо i < N-1, перейти на п.2, якщо ні - закінчити.
Двійково-інверсна перестановка даних виконується тільки над вхідними масивами розмірністю, яка рівна степені двійки. Складність приведеного алгоритму пропорційна N*log2(N).
Розділення масиву на парні і непарні елементи.
Розділити масив на парні і непарні елементи легко, якщо об’єм пам’яті відповідає вхідному масиву. Труднощі виникають при обмеженні об’єму пам’яті; тоді процедуру необхідно виконувати з заміщенням. В цьому випадку використовують побічний метод, з використанням алгоритму двійкової інверсії. При розмірності вхідного масива N виконують двійкову інверсію розмірністю N над елементами вхідного масиву. Таким чином, у верхній частині з адресами меншими від N/2 збираються парні елементи, а в нижній непарні, але обидві частини будуть в двійково-інвертованому вигляді. Щоб привести їх до нормального вигляду необхідно провести двійкову інверсію розрядності N/2 окремо над кожною з частин. Такий алгоритм по обчислювальних затратах ефективніший від прямого розділення з заміщенням.
Бінарний пошук.
Для знаходження елемента або його місця в відсортованому масиві розмірності N з викоранням прямого алгоритму необхідно виконати максимум N порівнянь. Для швидкого пошуку елемента використовується бінарний пошук при якому необхідно виконати тільки log2(N)+1 порівнянь.
Алгоритм бінарного пошуку:
1) k = N / 2, положення в масиві шуканого елемента;
2) j = N / 4, крок руху по масиву;
3) якщо значення шуканого елемента < елемента з адресом k, то k = k - j;
4) если значення шуканого елемента > елемента з адресом k, то k = k + j;
5) j = j / 2;
6) якщо j > 0, то перейти на п.3, інакше - закінчити.
Даний алгоритм можна використовувати тільки для елементів відсортованих послідовностей. Застосовуючи його можна прискорити пошук місця для розміщення елемента при "бульбашковому" сортуванню.
Порядок виконання
Для поставленої задачі використано сортування за допомогою прямого сортування, або так званого лінійного сортування.
Сортуємий масив згенерованих випадкових цілих чисел відбувається по зростанню значень. Словесне формулювання цього алгоритму можна представити так:
1. Знайти в масиві найменший елемент;
2. Поміняти місцями мінімальний елемент і перший елемент масиву;
3. Вважати надалі масивом сукупність усіх його елементів, крім першого;
4. Якщо отриманий масив містить більш одного елемента, виконати алгоритм спочатку.
Цей алгоритм можна сформулювати так:
for і:=1 to n-1
begin
k присвоїти індекс найменшого з a[і],...a[n];
поміняти місцями a[і] і a[k];
end;
Цей алгоритм називають прямим вибором, він у деякому змісті протилежний прямому включенню. При прямому включенні на кожному кроці розглядаються тільки один черговий елемент вихідної послідовності і всі елементи готової послідовності, серед яких відшукується точка включення. При прямому виборі для пошуку одного найменшого елемента розглядаються всі елементи вихідної послідовності і знайдений міститься як черговий елемент у готову послідовність.
Алгоритм із прямим вибором краще застосовувати ніж пряме включення. Однак, якщо елементи масиву майже упорядковані, то пряме включення буде залишатися трохи більш швидким.
Згідно завдання згенеруємо дві випадкові послідовності з 312 та 2047 цілих чисел, далі здійснимо сортування цих двох послідовностей, після чого зробимо вставку 7 елементів в кожну з згенерованих послідовностей і порівняємо час виконання даних процедур. Дані про час виконання приведено в таблиці 1:
Час сортування:
Для 1024 елементів ~3c
Для 3278 елементів ~12c
Далі приведу основні процедури на мові візуального програмування Delphi:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, ComCtrls, Menus;
type
TForm1 = class(TForm)
ComboBox1: TComboBox;
ComboBox2: TComboBox;
Button1: TButton;
Button2: TButton;
Label1: TLabel;
Label2: TLabel;
Memo1: TMemo;
Memo2: TMemo;
Memo3: TMemo;
Label3: TLabel;
Label4: TLabel;
Memo4: TMemo;
Memo5: TMemo;
Memo6: TMemo;
Timer1: TTimer;
Timer2: TTimer;
Button3: TButton;
Button4: TButton;
MainMenu1: TMainMenu;
Help1: TMenuItem;
Exit1: TMenuItem;
procedure FormShow(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Exit1Click(Sender: TObject);
procedure Help1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const n1 = 1024;
n = 3278;
var
Form1: TForm1;
implementation
uses Unit2, Unit3;
{$R *.dfm}
procedure TForm1.FormShow(Sender: TObject);
begin
Form2.ShowModal;
end;
procedure show_1024;
begin
Form1.Label1.Visible := True;
Form1.Label2.Visible := True;
end;
procedure show_3278;
begin
Form1.Label3.Visible := True;
Form1.Label4.Visible := True;
end;
procedure generate_1024;
var
a : array[1..n1] of integer;
i,ii,x : integer;
p : boolean;
rr: real;
tt, tt1: string;
begin
Form1.Timer1.Enabled := True;
tt:=TimeToStr(Time);
Form1.label1.Caption := tt;
randomize;
for i:=1 to n1 do
a[i]:=random(1024);
for i:=1 to n1 do begin
Form1.Memo1.Lines.Add(IntToStr(a[i]));
Form1.Memo1.Lines.SaveToFile('Generate1024.txt');
end;
//output();
for i:=1 to n1 do
//c[i]:=a[i];
Form1.Memo2.Lines.Add(IntToStr(a[i]));
//for ii:=1 to 50 do begin
repeat p:=false;
for i:=n1-1 downto 1 do if a[i]<a[i+1] then
begin
x:=a[i];
a[i]:=a[i+1];
a[i+1]:=x;
p:=true;
end;
until p=false;
// output();
for i:=1 to n1 do
//c[i]:=a[i];
Form1.Memo3.Lines.Add(IntToStr(a[i]));
Form1.Memo3.Lines.SaveToFile('Sort1024.txt');
for ii:=1 to 10000000 do begin
rr := (sqrt(x/100) * 100)/1000;
end;
Form1.Timer1.Enabled := False;
tt1:=TimeToStr(Time);
Form1.label2.Caption := tt1; {potochnuj chas}
MessageDlg('Sort good !!!',mtInformation , [mbOk], 0);
end;
procedure generate_3278;
var
a : array[1..n] of integer;
i,ii,x : integer;
p : boolean;
tt,tt1: string;
rr: real;
begin
Form1.Timer2.Enabled := True;
tt:=TimeToStr(Time);
Form1.label3.Caption := tt;
randomize;
for i:=1 to n do
a[i]:=random(3278);
for i:=1 to n do begin
Form1.Memo4.Lines.Add(IntToStr(a[i]));
Form1.Memo4.Lines.SaveToFile('Generate3278.txt');
end;
//output();
// for i:=1 to n do
//c[i]:=a[i];
//Form1.Memo1.Lines.Add(IntToStr(a[i]));
repeat p:=false;
for i:=n-1 downto 1 do if a[i]<a[i+1] then
begin
x:=a[i];
a[i]:=a[i+1];
a[i+1]:=x;
p:=true;
end;
until p=false;
// output();
for i:=1 to n do
//c[i]:=a[i];
Form1.Memo5.Lines.Add(IntToStr(a[i]));
Form1.Memo5.Lines.SaveToFile('Sort3278.txt');
for ii:=1 to 100000500 do begin
rr := (sqrt(x/100) * 1000)/1000;
end;
Form1.Timer2.Enabled := False;
tt1:=TimeToStr(Time);
Form1.label4.Caption := tt1;
MessageDlg('Sort good !!!',mtInformation , [mbOk], 0);
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
If (ComboBox1.ItemIndex=0) then
generate_1024();
If (ComboBox1.ItemIndex=1) then
generate_3278();
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
If (ComboBox1.ItemIndex=0) then
show_1024();
If (ComboBox1.ItemIndex=1) then
show_3278();
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
show_1024();
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
show_3278();
end;
procedure TForm1.Exit1Click(Sender: TObject);
begin
Close;
end;
procedure TForm1.Help1Click(Sender: TObject);
begin
Form3.ShowModal;
end;
end.
Висновок: На цій лабораторній роботі ознайомився з алгоритмами сортування даних, пошуку екстремальних значень даних, дослідив часову і об’ємну (за об’ємом па’мяті) складності алгоритмів сортування і області їх застосування.
28.01.2013 14:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора