Очень доброжелательный и компетентный автор. Всегда был на связи, все разъяснил, предоставил несколько вариантов программы. Рекомендую.
Информация о работе
Подробнее о работе
Исследование сортировки выбором. Программа, выполненная на языке С++
- 57 страниц
- 2017 год
- 91 просмотр
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Осуществить исследование метода сортировки выбором, используя массивы упорядоченных и неупорядоченных чисел по 10,100,1000 и 10000 элементов. Реализовать алгоритм на разных языках программирования, а именно Си++, Pascal. Определить количество сравнений, обменов. Измерить время работы алгоритма. Оценить эффективность и устойчивость алгоритма.
4 Эффективность алгоритма
Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n )
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.
Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Приведенная реализация является неустойчивой.
Ниже рассматривается следующий массив из элементов, каждый из которых имеет два поля. Сортировка идет по первому полю.
При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..,a[n],...
...
ПРИЛОЖЕНИЕ Б
Реализация алгоритма в среде Lazarus
unit Unit1;
{$mode objfpc}{$H+}
interface
uses
{$IFDEF UNIX}{$IFDEF UseCThreads}
cthreads,
{$ENDIF}{$ENDIF}
Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, math, LCLIntf, windows;
type
{ TForm1 }
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
RadioButton1: TRadioButton;
procedure Button1Click(Sender: TObject);
private
{ private declarations }
public
{ public declarations }
end;
var
Form1: TForm1;
arr:array[1..10] of integer;
size:integer;
implementation
{$R *.
...
1 Шилдт Г. C++: базовый курс/Герберт Шилдтю-Вильямс, 2008 .-288с.
2 Семакин И.Г. /Основы программирования/И. Г. Семакин, А. П. Шестаков.-М.: Мастерство, 2001 .-241с.
3 Сортировка выбором // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Сортировка_выбором - Загл с экрана Яз. рус., англ.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
