Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Алгоритм сортировки методом отбора (постоянная Эйлера)
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Алгоритм сортировки методом отбора (постоянная Эйлера) Печать E-mail
Автор 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;

   end;

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*(n2-n)

  • Для метода отбора n(log n+y)**

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

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

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

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

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


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

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

 

Последнее обновление ( 17.02.2013 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги