Алгоритм сортировки методом отбора (постоянная Эйлера)

Автор megabax

03.01.2011 г.

Циклы

Алгоритм сортировки методом отбора (постоянная Эйлера)

Исходники к уроку можно скачать здесь.

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

procedure SelectSort(var item:DataArray; count:integer);

var c,t,i,j:integer; exchange:boolean;

begin

for i:=0 to Count - 1 do

begin

exchange:=false;

c:=i;

t:=item[i];

for j := i+1 to Count do if item[j]<t then

begin

c:=j;

t:=item[j];

exchange:=true;

end;

if exchange then

begin

item[c]:=item[i];

item[i]:=t;

end;

На том же Delphi напишем тестовый пример для проверки этого алгоритма. Для начала кинем на форму необходимые компоненты (ListBox-ы lbIn и lbOut)*:

тип DataArray объявим как

DataArray = array [0..1000] of integer;

и глобальную переменную на него (выделено красным):

var

frmSelectSort: TfrmSelectSort;

ar:DataArray;

Теперь напишем обработчик нажатия на кнопочку "Старт":

procedure TfrmSelectSort.btnStartClick(Sender: TObject);

var i,cn:LongInt;

begin

cn:=StrToInt(edCount.Text);

lbIn.Clear;

lbOut.Clear;

for i:=1 to cn do

begin

ar[i]:=random(1000);

lbIn.Items.Add(IntToStr(ar[i]));

end;

SelectSort(ar, cn);

for i:=1 to cn do lbOut.Items.Add(IntToStr(ar[i]));

end;

Да, и не забудьте в обработчик создание формы вставить randomize:

procedure TfrmSelectSort.FormCreate(Sender: TObject);

begin

randomize;

end;

Теперь мы можем запустить нашу программу на выполнение:

Давайте теперь сравним этом метод с пузырьковой сортировкой. Возьмем для среднего случая, при котором количество сравнений можно вычислить по формуле

Для метода пузырьковой сортировки 3/4*(n²-n)
Для метода отбора n(log n+y)**

где n - количество элементов в массиве, y - постоянная Эйлера, равная примерно 0.577216.

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

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

Исходники к уроку можно скачать здесь.

Скриншоты, помеченные знаком * , являются цитатами и иллюстрациями программного продукта "Turbo Delphi", авторское право на который принадлежит "Borland Software Corporation,

** Г. Шилдт, "Теория и практика С++".

Последнее обновление ( 17.02.2013 г. )

« След.		Пред. »

Вернуться