Алгоритм «Поиска моды» (Mode Search)

Цель работы.

Изучение и программирование стандартного алгоритма «поиска моды».

Блок-схема программы для сортировки выбором.

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

clc;

clear all; N=8;

mt=1;

mc=1;

im=1;

i=1;

s=[4 4 4 7 7 7 7 7];

%s=[4 4 4 4 4 7 7 7];

%s=[1 2 3 4 5 6 7 8];

while i<N-1 % рассмотрим весь массив

2

j=i;

while (j<N) && (s(j)==s(j+1)) % пока элемент повторяется,

а его номер в массиве меняется, и номер этого элемента <=8 mt=mt+1;

j=j+1;

end i=i+mt;

if mt>mc % сохраняем кол-во повторений (>1) в переменной

mc

mc=mt; im=i-mt;

end mt=1;

end

if mc>1 % если номер элемента > 1 disp('Значение моды :'); disp(s(im));

disp('Индекс начала последовательности значений моды:'); disp(im);

disp('Количество значений mc в последовательности моды:'); disp(mc);

else disp('No mode'); end

Таблица 1 листингов трех версий вектора S(8).

3

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

clear all;

N=10^4; % N=10^5; N=10^6; N=10^7; mt=1;

mc=1;

im=1;

i=1;

s=fix(50*rand ([1 N])); tic;

y=quicksort(s);

while i<N-1 % рассмотрим весь массив j=i;

while (j<N) && (s(j)==s(j+1)) % пока элемент повторяется,

а его номер в массиве меняется, и номер этого элемента <=8 mt=mt+1;

j=j+1;

end i=i+mt;

if mt>mc % сохраняем кол-во повторений (>1) в переменной

mc

mc=mt; im=i-mt;

end mt=1;

end toc;

if mc>1 % если номер элемента > 1 disp('Значение моды :'); disp(s(im));

disp('Индекс начала последовательности значений моды:'); disp(im);

disp('Количество значений mc в последовательности моды:'); disp(mc);

else disp('No mode'); end

function[vector]=quicksort(vector)

if ~isempty(vector)% если вектор пустой, программа остановится

global cm; cm=cm+1; pivot=vector(1);

A1=quicksort(vector(vector<pivot));

A2=vector(vector==pivot);

A3=quicksort(vector(vector>pivot)); vector=[A1 A2 A3];

end end

4

Таблица 2.

Таблица 3.

KN=Nj/Ni, Kt=tj/ti

Вывод.

Временя поиска моды увеличивается с увеличением размерности вектора.

5