Сортировка выборкой на месте




Сортировка массивов

 

Постановка задачи

Сортировка - процесс упорядочения данных.

Пусть дана совокупность из N элементов данных, которые условно назовем записями: r1, r2, r3,..., rN. Вся совокупность данных называется набором данных.

Каждая запись в общем случае имеет сложную внутреннюю структуру (может состоять из нескольких полей различных типов). Как правило, сортировка осуществляется по одному из полей (если необходимо провести сортировку по нескольким полям, то она может быть сведена к последовательным сортировкам по одному полю). Поле, по которому осуществляется сортировка, называется ключом сортировки, или ключевым полем.

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

Для множества значений ключа сортировки (в дальнейшем - ключа) обязательно должны выполняться следующие условия.

1. Для любых а, b и с К справедливо только одно из соотношений:

а > b, a = b, a < b.

2. Если а < b и b < c, то a < c.

Задача сортировки состоит в том, чтобы найти такую перестановку элементов rL, при которой значения ключей расположились бы в неубывающем (не возрастающем) порядке.

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

Сортировка выборкой на месте

 

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

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

 
 


x1 x2 xmin
             
xmin x2 xmin’
             
xmin xmin’ x3 xmin”…
xmin xmin’ xmin” x4

Далее следует пример программы сортировки выборкой на месте. Как и в других примерах, в тексте программы имеются комментарии, поясняющие смысл каждой команды.

 

% программная реализация алгоритма сортировки

% выборкой на месте

clear all;

T = []; % формируется пустой массив времени сортировки

N = [];

for n = [ 1000: 1000: 5000 ]; % меняется размерность массива данных

N = [ N n ];

time = round(clock); % определяется текущее время для инициализации

% датчика случайных чисел

rand('seed', time(5)*time(6)); % осуществляется инициализация

% датчика случайных чисел

x = rand(1, n); % генерируется массив случайных чисел из диапазона

% [ 0 1 ]

x = round(100*x); % случайный массив целых двузначных чисел

t_start = clock; % фиксируется время старта сортировки

for I = 1: (n-1)

min_x = x(I); index = I; % предполагается, что минимальный

% элемент имеет номер I

for J = (I+1): n % перебираются все элементы от I+1 до n

if x(J) < min_x % если находится элемент меньше, чем

% текущий минимум, то он становится

min_x = x(J); % текущим минимальным

index = J; % фиксируется его номер

end

end

buff = x(I); % текущий элемент и минимальный

x(I) = x(index); % меняются местами

x(index) = buff;

end

t_stop = clock; % фиксируется время остановки сортировки

t = t_stop(6) - t_start(6); % вычисляется время сортировки (сек)

T = [ T t ]; % формируется массив времен сортировки

end;

plot(N, T), grid on % строится график зависимости времени сортировки

% от количества элементов массива

 

Примерный вид графика зависимости времени сортировки от объема сортируемых данных показан на следующем рисунке:

 

Конкретный характер рассматриваемой зависимости определяется в большой мере производительностью процессора и объемом оперативной памяти: чем они больше, тем быстрее сортируется массив.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-19 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: