Сортировки одномерного массива
Алгоритм - структура обрабатываемых данных. Индексированные элементы массива. Сортировка как процесс перегруппировки множества объектов в некотором определенном порядке. Цель – облегчить последующий поиск элементов в таком отсортированном множестве.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 06.02.2014 |
| Размер файла | 320,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Cодержание
- Введение
- 1. Основная часть
- 1.1 Сортировка пузырьком
- 1.2 Сортировка прямым выбором
- 1.3 Пирамидальная сортировка
- 1.4 Быстрая сортировка
- 1.5 Сортировка слиянием
- 2. Сравнение производительности сортировок
- 3. Массивы
- 3.1 Описание типа "массив"
- Заключение
- Список использованной литературы
- Введение
- Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки - облегчить последующий поиск элементов в таком отсортированном множестве. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах - почти везде, где нужно искать хранимые объекты. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
- сравнение, определяющее упорядоченность пары элементов;
- перестановку, меняющую местами пару элементов;
- собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. алгоритм индексированный сортировка порядок
Цель моей работы - рассмотреть основные алгоритмы сортировки массивов и найти оптимальный.
Массив - это проиндексированная, упорядоченная последовательность однотипных элементов. В данном случае под элементами подразумеваются числа. Сортировка массива - это процесс, направленный на упорядочение массива. Полная сортировка выстраивает элементы массива по возрастанию или по убыванию. То есть каждый последующий элемент больше либо равен предыдущему (X1>X2>X3>…>XN) или наоборот(X1<X2<X3<…<XN).
1. Основная часть
1.1 Сортировка пузырьком
Сортировка пузырьком (BubbleSort) - один из простейших методов сортировки. Название метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого мы просматриваем все элементы снизу вверх, берем пару соседних элементов и, в случае, если они стоят неправильно, меняем их местами.
Вместо поднятия самого «легкого» элемента можно «топить» самый «тяжелый».
Так как за каждый шаг на свое место встает ровно 1 элемент (самый «легкий» из оставшихся), то нам потребуется выполнить N шагов.
Текст процедуры сортировки можно записать так:
procedure bubble_sort(var a:list; n : integer);
var
i, j, k : integer;
begin
for i := 0 to n-1 do
for j := n-1 downto i do
if (a[j-1] > a[j]) then begin
k := a[j-1];
a[j-1] := a[j];
a[j] := k;
end;
end;
Для передачи массивов в процедуры и функции, необходимо определить новый тип:
type
list = array[0..10000] of integer;
который избавляет от необходимости писать длинные команды и уменьшает количество возможных опечаток и ошибок.
Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.
Сложность алгоритма сортировки пузырьком составляет O(N2), количество операций сравнения O(N2).
N (N-1)/2. Это очень плохая сложность, по алгоритм имеет два плюса.
Во-первых, он легко реализуется, а значит, может и должен применяться в тех случаях, когда требуется однократная сортировка массива. При этом размер массива не должен быть больше 10000, т.к. иначе алгоритм сортировки пузырьком не будет укладываться в отведенное время.
Во-вторых, сортировка пузырьком использует только сравнения и перестановки соседних элементов, а значит, может использоваться в тех задачах, где явно разрешен только такой обмен и для сортировки, например, списков.
Существуют разнообразные «оптимизации» сортировки пузырьком, которые усложняют (а нередко и увеличивают время работы алгоритма), но не приносят выгоды ни в плане сложности, ни в плане быстродействия. На этом плюсы сортировки пузырьком заканчиваются.
1.2 Сортировка прямым выбором
Рассмотрим еще один квадратичный алгоритм, который, однако, является оптимальным по количеству присваиваний и может быть использован, когда по условию задачи необходимо явно минимизировать количество присваиваний.
Суть метода заключается в следующем: мы будем выбирать минимальный элемент в оставшейся части массива и приписывать его к уже отсортированной части. Повторив эти действия N раз, мы получим отсортированный массив.
procedure select_sort(var a : list; n : integer);
var
i, j, k : integer;
begin
for i := 0 to n-1 do begin
k := i;
for j := i+1 to n-1 do
if (a[j]<a[k]) then k := j;
j := a[k];
a[k] := a[i];
a[i] := j;
end;
end;
Количество сравнений составляет O(N2), а количество присваиваний всего O(N). В целом это плохой метод, и он должен быть использован только в случаях, когда явно необходимо минимизировать количество присваиваний.
1.3 Пирамидальная сортировка
Одним из эффективных алгоритмов сортировки является пирамидальная сортировка (работает за O(N logN), в которой используются понятие кучи.
Куча - это структура данных, которая может выдавать минимальный (или максимальный) элемент за О(1), добавление нового элемента или добавление минимального элемента происходит О(logN) (где N - количество элементов в куче). Другие операции над кучей не определены (хотя при необходимости могут быть введены, однако эффективность их будет невысокой, и они обязаны поддерживать свойства кучи).
Мы будем выбирать из кучи самый большой элемент, и записывать его в начало уже отсортированной части массива (сортировка выбором в обратном порядке). Т.е. отсортированный массив будет строиться от конца к началу. Такие ухищрения необходимы, чтобы не было необходимости в дополнительной памяти и для ускорения работы алгоритма -- куча будет располагаться в начале массива, а отсортированная часть будет находиться после кучи.
Напомним свойство кучи максимумов: элементы с индексами i + 1 и i + 2 не больше, чем элемент с индексом i (естественно, если i + 1 и i + 2 лежат в пределах кучи). Пусть n -- размер кучи, тогда вторая половина массива (элементы от n/2 + 1 до n) удовлетворяют свойству кучи. Для остальных элементов вызовем процедуру «проталкивания» по куче, начиная с n/2 до 0.
procedure down_heap(var a : list; k : integer; n : integer);
var
y, temp : integer;
begin
temp := a[k];
while (k*2+1 < n) do begin
y := k*2+1;
if (y < n-1) and (a[y] < a[y+1]) then inc(y);
if (temp >= a[y]) then break;
a[k] := a[y];
k := y;
end;
a[k] := temp;
end;
Эта процедура получает указатель на массив, номер элемента, который необходимо протолкнуть и размер кучи. У нее есть небольшие отличия от обычных процедур работы с кучей. Номер минимального предка хранится в переменной у, если необходимость в обменах закончена, то мы выходим из цикла и записываем просеянную переменную на предназначенное ей место.
Сама сортировка будет состоять из создания кучи из массива и N переносов элементов с вершины кучи с последующим восстановлением свойства кучи:
procedure heap_sort(var a : list; n : integer);
var
i, temp : integer;
begin
for i := n div 2 - 1 downto 0 do down_heap(a, i, n);
for i := n-1 downto 0 do begin
temp := a[i];
a[i] := a[0];
a[0] := temp;
down_heap(a, 0, i);
end;
end;
Всего в процессе работы алгоритма будет выполнено 3ЧN/2-2 вызова процедуры down_heap, каждый из которых занимает O(logN). Таким образом, мы и получаем искомую сложность в O(N logN), не используя при этом дополнительной памяти. Количество присваиваний также составляет O(N logN).
Пирамидальную сортировку следует осуществлять, если из условия задачи понятно, что единственной разрешенной операцией является «проталкивание» элемента по куче, либо в случае отсутствия дополнительной памяти.
1.4 Быстрая сортировка
Этот улучшенный метод сортировки основан на обмене. Это самый лучший из всех известных на данный момент методов сортировки массивов. Был разработан в 1962 г. Его производительность столь впечатляюща, что изобретатель Ч. Хоар назвал этот метод быстрой сортировкой (Quicksort).
Выбирается некий опорный элемент и все числа, меньшие его перемещаются в левую часть массива, а все числа большие его -- в правую часть. Затем вызываем процедуру сортировки для каждой из этих частей.
Таким образом, процедура сортировки должна принимать указатель на массив и две переменные, обозначающие левую и правую границу сортируемой области.
Остановимся более подробно на выборе опорного элемента. В некоторых книгах рекомендуется выбирать случайный элемент между левой и правой границей. Хотя теоретически это красиво и правильно, но на практике следует учитывать, что функция генерации случайного числа достаточно медленная и такой метод заметно ухудшает производительность алгоритма в среднем.
Наиболее часто используется середина области, т.е. элемент с индексом (l + r)/2. При таком подходе используются быстрые операции сложения и деления на два, и в целом он работает достаточно неплохо. Однако в некоторых задачах, где сутью является исключительно сортировка, хитрое жюри специально подбирает тесты так, чтобы «завалить» стандартную быструю сортировку с выбором опорного элемента из середины. Стоит заметить, что это очень редкая ситуация, но все же стоит знать, что можно выбирать произвольный элемент с индексом т так, чтобы выполнялось неравенство l ? т ? r. Чтобы это условие выполнялось, достаточно выбрать произвольные два числа х и у и выбирать т исходя из следующего соотношения:
т = (х l + у r)/(х + у).
В целом такой метод будет незначительно проигрывать выбору среднего элемента, т.к. требует двух дополнительных умножений.
Приведем текст процедуры быстрой сортировки с выбором среднего элемента в качестве опорного:
procedure quick_sort(var a : list; left, right : integer);
var
i, j, temp, p : integer;
begin
i := left;
j := right;
p := a[(left+right) div 2];
repeat
while (a[i] < p) do inc(i);
while (a[j] > p) do dec(j);
if (i <= j) then begin
temp := a[i];
a[i] := a[j];
a[j] := temp;
inc(i);
dec(j);
end;
until (i > j);
if (j > left) then quick_sort(a, left, j);
if (i < right) then quick_sort(a, i, right);
end;
Чтобы воспользоваться быстрой сортировкой, необходимо передать в процедуру левую и правую границы сортируемого массива, (т.е., например, вызов для массива а будет выглядеть как quick_sort(a, 0, n-1).
Алгоритм быстрой сортировки в среднем использует O(N logN) сравнений и O(N logN) присваиваний (на практике даже меньше) и использует O(logN) дополнительной памяти (стек для вызова рекурсивных процедур). В худшем случае алгоритм имеет сложность O(N2) и использует О(N) дополнительной памяти, однако вероятность возникновения худшего случая крайне мала: на каждом шаге вероятность худшего случая равна 2/N, где N -- текущее количество элементов.
Рассмотрим возможные оптимизации метода быстрой сортировки.
Во-первых, при вызове рекурсивной процедуры возникают накладные расходы на хранение локальных переменных (которые нам не особо нужны при рекурсивных вызовах) и другой служебной информацией. Таким образом, при замене рекурсии стеком мы получим небольшой прирост производительности и небольшое снижение требуемого объема дополнительной памяти.
Во-вторых, как мы знаем, вызов процедуры -- достаточно накладная операция, а для небольших массивов быстрая сортировка работает не очень хорошо. Поэтому, если при вызове процедуры сортировки в массиве находится меньше, чем К элементов, разумно использовать какой-либо нерекурсивный метод, например, сортировку вставками или выбором. Число К при этом выбирается в районе 20, конкретные значения подбираются опытным путем. Такая модификация может дать до 15% прироста производительности.
Быструю сортировку можно использовать и для двусвязных списков (т.к. в ней осуществляется только последовательный доступ с начала и с конца), но в этом случае возникают проблемы с выбором опорного элемента -- его приходится брать первым или последним в сортируемой области. Эту проблема можно решить неким набором псевдослучайных перестановок элементов списка, тогда даже если данные были подобраны специально, эффект нейтрализуется.
1.5 Сортировка слиянием
Сортировка слияниями также основывается на идее, которая уже была нами затронута при рассмотрении алгоритма поиска двух максимальных элементов. В этом алгоритме мы сначала разобьем элементы на пары и упорядочим их внутри пары. Затем из двух пар создадим упорядоченные четверки и т.д.
|
3 |
7 |
8 |
2 |
1 |
6 |
1 |
5 |
Последовательности длины 1 |
|
|
37 |
28 |
46 |
1 5 |
Слияние до упорядоченных пар |
|||||
|
2378 |
1456 |
Слияние пар в упорядоченные четверки |
|||||||
|
12345678 |
Слияние пар в упорядоченные четверки |
Интерес представляет сам процесс слияния: для каждой из половинок мы устанавливаем указатели на начало, смотрим, в какой из частей элемент по указателю меньше, записываем этот элемент в новый массив и перемещаем соответствующий указатель.
Опишем процедуру слияния следующим образом:
procedure merge(var a, b : list; c, d, e : integer);
var
p1, p2, pres : integer;
begin
p1 := c;
p2 := d;
pres := c;
while (p1 < d) and (p2 < e) do
if (a[p1] < a[p2]) then begin
b[pres] := a[p1];
inc(pres);
inc(p1);
end else begin
b[pres] := a[p2];
inc(pres);
inc(p2);
end;
while (p1 < d) do begin
b[pres] := a[p1];
inc(pres);
inc(p1);
end;
while (p2 < e) do begin
b[pres] := a[p2];
inc(pres);
inc(p2);
end;
end;
Здесь а - исходный массив, b - массив результата, c и d - указатели на начало первой и второй части соответственно, е - указатель на конец второй части.
Далее опишем нерекурсивную процедуру сортировки слиянием.
procedure merge_sort(var a : list; n : integer);
var
c, k, d, e : integer;
temp, a2, b : ^list;
temp_list : list;
begin
b := @temp_list;
a2 := @a;
k := 1;
while (k <= 2*n) do begin
c := 0;
while (c < n) do begin
if (c + k < n) then
d := c + k
else
d := n;
if (c + 2*k < n) then
e := c + 2*k
else
e := n;
merge(a2^, b^, c, d, e);
c := c + k*2;
end;
temp := a2;
a2 := b;
b := temp;
k := k*2;
end;
for c := 0 to n-1 do
a[c] := a2[c];
end;
Рекурсивная реализация сортировки слияниями несколько проще, но обладает меньшей эффективностью и требует O(logN) дополнительной памяти.
Алгоритм имеет сложность O(N logN) и требует O(N) дополнительной памяти.
В оригинале этот алгоритм был придуман для сортировки данных во внешней памяти (данные были расположены в файлах) и требует только последовательного доступа. Этот алгоритм применим для сортировки односвязных списков.
2. Сравнение производительности сортировок
Сортировка -- перестановка местами объектов в определенном порядке. Известно несколько сотен алгоритмов сортировки и их модификаций.
Пусть дана последовательность элементов - A1, А2, …, Аn. Сортировка означает перестановку этих элементов в новом порядке Аk1 , Аk2, …, Akn. Этот порядок соответствует значениям некоторой функции F, такой, что справедливо отношение F(Ak1) < F(Ak2)< ... <F(Akn).
Как у любого вычислительного процесса у сортировки есть свои критерии для сравнительной оценки качества программы и соответствующего ей алгоритма. Такими критериями являются: объем используемой памяти и время работы программы. Хорошей по критерию памяти считается такая сортировка, при которой данные сортируются в том же самом массиве, где находились исходные данные. При оценке времени сортировки используют два показателя: число сравнений ключей (С), число пересылок данных (М). Хорошими по времени считаются сортировки, в которых число сравнений С=N*Ln(N). К простым, то есть не очень хорошим, относятся такие сортировки, в которых число сравнений пропорционально квадрату размерности N исходного массива С?N2. Следует отметить, что показатели С и М существенно зависят от первоначальной упорядоченности сортируемого массива. Наиболее тяжелым (Мах) считается случай, когда массив упорядочен в обратном порядке. Ниже мы рассмотрим три наиболее известных способа сортировки одномерного массива. Сравнительные временные характеристи ки этих способов приведены в следующей таблице:
|
Название |
Сравнений |
Присваиваний |
Память |
|
|
Пузырьком |
O(N2) |
O(N2) |
0 |
|
|
Выбором |
O(N2) |
O(N) |
0 |
|
|
Пирамидальная |
O(N logN) |
O(N logN) |
0 |
|
|
Быстрая |
O(N logN) |
O(N logN) |
O( logN) |
|
|
Слиянием |
O(N logN) |
O(N logN) |
O(N) |
3. Массивы
Рассмотренные ранее простые типы определяют различные мнбжества атомарных (неразделимых) значений. В отличие от них структурные типы задают множества сложных значений, каждое из которых образует совокупность нескольких значений другого типа. В структурных типах выделяют регулярный тип (массивы).
3.1 Описание типа "массив"
С понятием "массив" приходится сталкиваться при решении научно-технических и экономических задач обработки совокупностей большого количества значений. В общем случае массив -- это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.
Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве.
В качестве элементов массива можно использовать и любой другой ранее описанный тип, поэтому вполне правомерно существование массивов записей, массивов указателей, массивов строк, массивов массивов и т.д. Элементами массива могут быть данные любого типа, включая структурированные. Тип элементов массива называется базовым. Особенностью языка Паскаль является то, "что число элементов массива фиксируется при описании и в процессе выполнения программы не меняется.
Элементы, образующие массив, упорядочены таким образом, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа, кроме вещественного. Тип индекса определяет границы изменения значений индекса. Для описания массива предназначено словосочетание array of (массив из).
Если в качестве базового типа взят другой массив, образуется структура, которую принято называть многомерным массивом.
Если в такой форме описания массива задан один индекс, массив называется одномерным, если два индекса -- двумерным, если n индексов -- n-мерным. Одномерный массив соответствует понятию линейной таблицы (вектора), двумерный -- понятию прямоугольной таблицы (матрицы, набору векторов). Размерность ограничена только объемом памяти конкретного компьютера. Одномерные массивы обычно используются для представления векторов, а двумерные -- для представления матриц.
Элементы массива располагаются в памяти последовательно. Элементы с меньшими значениями индекса хранятся в более низких адресах памяти. Многомерные массивы располагаются таким образом, что самый правый индекс возрастает самым первым.
Контроль правильности значений индексов массива может проводиться с помощью директивы компилятора R.. По умолчанию директива R. находится в пассивном состоянии {$R--}. Перевод в активное состояние вызывает проверку всех индексных выражений на соответствие их значений диапазону типа индекса.
Существует различие между регулярными типами в языке Паскаль и массивами в некоторых других языках программирования, заключающееся в том, что в Паскале количество элементов массива всегда должно быть фиксировано, т. е. определяться при трансляции программы. Это считается недостатком языка, так как не во всех программах можно заранее предсказать необходимый размер массива (который может определяться в зависимости от тех или иных условий, возникающих в процессе исполнения). В программах, обрабатывающих массивы, помимо использования для определения размера массива предварительно определенных констант иногда используется прием, позволяющий имитировать работу с массивами переменной длины, который заключается в следующем: в разделе описания констант предварительно определяют возможное максимальное значение размера массива, а затем в программе запрашивают текущее значение размера и используют это значение далее при заполнении и обработке массива.
Для работы с массивом как единым целым используется идентификатор массива без указания индекса в квадратных скобках. Массив может участвовать только в операциях отношения "равно", "не равно" и в операторе присваивания. Массивы, участвующие в этих действиях, должны быть идентичны по структуре, т. е. иметь одинаковые типы индексов и одинаковые типы компонентов.
После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Например, запись Mas[2], VectorZ[10] позволяет обратиться ко второму элементу массива Mas и десятому элементу массива VectorZ. При работе с двумерным массивом указываются два индекса, с п-мерным массивом -- n индексов. Например, запись MartU[4,4] делает доступным для обработки значение элемента, находящегося в четвертой строке четвертого столбца массива MartU.
Индексированные элементы массива называются индексированными переменными и могут быть использованы так же, как и простые переменные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, входить в качестве параметров в операторы Readln, Read, Writeln, Write; им можно присваивать любые значения, соответствующие их типу.
Инициализация (присваивание начальных значений) массива заключается в присваивании каждому элементу массива одного и того же значения, соответствующего базовому типу. Наиболее эффективно эта операция выполняется с помощью оператора for.
Паскаль не имеет средств ввода-вывода элементов массива сразу, поэтому ввод и вывод значений производится поэлементно. Значения элементам массива можно присвоить с помощью оператора присваивания, как показано в примере инициализации, однако чаще всего они вводятся с экрана с помощью оператора Read или Readln с использованием оператора организации цикла for.
В связи с тем, что использовался оператор Readln, каждое значение будет вводиться с новой строки. Можно ввести и значения отдельных элементов, а не всего массива. Так, операторами Read(А[3]); Read(В[6,9]); вводится значение третьего элемента вектора A и значение элемента, расположенного в шестой строке девятого столбца матрицы В. Оба значения набираются на одной строке экрана, начиная с текущей позиции расположения курсора.
Копированием массивов называется присваивание значений всех элементов одного массива всем соответствующим элементам другого массива. Копирование можно выполнить одним оператором присваивания, например A:=D; или с помощью оператора for.
В обоих случаях значение элементов массива D не изменяется, а значения элементов массива A становятся равными значениям соответствующих элементов массива D. Очевидно, что оба массива должны быть идентичны по структуре.
Иногда требуется осуществить поиск в массиве каких-либо элементов, удовлетворяющих некоторым известным условиям. Пусть, например, надо выяснить, сколько элементов массива A имеют нулевое значение. Для ответа на этот вопрос введем дополнительную переменную K и воспользуемся операторами for и if:
После выполнения цикла переменная K будет содержать количество элементов массива A с нулевым значением.
Перестановка значений элементов массива осуществляется с помощью дополнительной переменной того же типа, что и базовый тип массива. Например, так запишется фрагмент программы, обменивающий значения первого и пятого элементов массива A.
Заключение
Сортировка пузырьком является простой в реализации, но крайне медленной. Сортировка прямым выбором сравнима по скорости с пузырьковой, но выигрывает по количеству сравнений. Из представленных сортировок, на практике быстрее всех работает быстрая сортировка. Она является оптимальной по простоте написания и надежной в работе. Пирамидальная сортировка хороша тем, что не требует лишней памяти. Среди представленных выше сортировок наилучшей является быстрая сортировка.
Выбор алгоритма зависит от структуры обрабатываемых данных. В случае сортировки соответствующие методы разбиты на два класса - сортировку массивов и сортировку файлов. Иногда их называют внутренней и внешней сортировкой, поскольку массивы хранятся в оперативной, внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но и более емкой внешней памяти.
Список использованной литературы
1. Вирт Н.. Алгоритмы и структуры данных. 1997.
2. Алексеев Е.Р, Чеснокова О.В. Турбо Паскаль 7.0. 1994.
3. Интернет http://ru.wikipedia.org "Википедия" - универсальная энциклопедия. 1994.
4. Интернет http://informatics.mccme.ru Дистанционная подготовка по информатике
5. Либерман М. Алгоритмы сортировки массивов. М.: Наука, 1997.
6. Нортон П., Уилтон Р. 1ВМ РС РЗ/2. Руководство по программированию: Пер. с англ. - М.: Радио и связь, 1994.
7. Перминов О.Н. Язык программирования Паскаль. - М.: Радио и связь, 1988. - 220 с.
8. Першиков В.И., Савинков В.М. Толковый словарь по информатике. - М.: Финансы и статистика, 1995.
Размещено на Allbest.ru
...Подобные документы
Сортировка как процесс перегруппировки заданного множества объектов в некотором определенном порядке, основные этапы данного процесса. Способы формирования начальных отрезков. Описание структуры программы. Результаты испытаний, их исследование и анализ.
курсовая работа [111,6 K], добавлен 31.01.2014Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Сортировка как процесс расстановки элементов "в некотором порядке", ее структура и основные компоненты, характеристика методов. Порядок выбора того или иного метода сортировки: линейный с обменом и подсчетом, методом Шелла, с отложенными обменами.
реферат [27,1 K], добавлен 13.09.2009Модификация и сравнения двух текстовых файлов. Программа, написанная на языке программирования Cи и работоспособна на IBM совместимых компьютерах. Псевдографический и графический интерфейсы. Анализ программы методом сортировки одномерного массива.
курсовая работа [116,2 K], добавлен 21.02.2008Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Программный комплекс по обработке заданного множества данных в динамической памяти компьютера. Запросы к массиву записей множества данных – групп в детском саду. Функция сортировки массива по числовому полю. Использование главной программы MAINPRO.
курсовая работа [419,3 K], добавлен 23.07.2014Создание программного обеспечения, позволяющего сортировать элементы числового массива в порядке возрастания или убывания их значений. Выбор языка программирования, среды разработки и построение алгоритма. Руководство пользователя и программиста.
курсовая работа [295,4 K], добавлен 07.04.2011Разработка и реализация типовых алгоритмов обработки одномерных массивов на языке Delphi. Максимальный и минимальный элемент массива. Значение и расположение элементов массива. Элементы массива, находящиеся перед максимальным или минимальным элементом.
лабораторная работа [12,8 K], добавлен 02.12.2014Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.
курсовая работа [78,2 K], добавлен 24.09.2010Представление (построение, создание) списка данных в виде линейного однонаправленного списка. Формирование массива данных. Вывод данных на экран. Алгоритм удаления, перемещения данных. Сортировка методом вставки. Алгоритм загрузки данных из файла.
курсовая работа [2,1 M], добавлен 16.05.2015Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Состав DЕLPHI проекта. Алгоритм сортировки вектора. Метод сортировки файла. Сценарий интерфейсного диалога пользователя с программой. Поиск и вычисление времени, затраченного на поиск и сортировку. Исходный текст модуля Project.dpr, MainForm.pas.
курсовая работа [827,4 K], добавлен 07.11.2010Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.
курсовая работа [359,0 K], добавлен 23.05.2012Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.
курсовая работа [242,3 K], добавлен 12.11.2010Решения задачи графическим и программным способами. Описание алгоритма решения графическим способом, укрупненная схема алгоритма. Ввод элементов двумерного массива, вывод преобразованного массива, разработка программы на языке pascal, листинг программы.
курсовая работа [115,5 K], добавлен 22.05.2010Структура программного комплекса. Ввод информации из заданного файла. Создание набора данных. Добавление элементов в конец набора данных. Просмотр всех элементов набора данных. Копирование информации из НД в заданный файл. Сортировка массива по номерам.
курсовая работа [630,5 K], добавлен 01.06.2014Учет товаров, контроль их срока хранения на складах фирмы как предметная область проектируемой базы данных "Хранение товаров". Содержание основных запросов базы данных. Методы сортировки массива данных - пузырька, цифровой сортировки и деревьев сравнений.
контрольная работа [3,4 M], добавлен 12.02.2014Описание алгоритма решения задачи графическим способом. Ввод элементов исходного массива в цикле. Нахождение определённых элементов. Сортировка элементов с помощью пузырькового метода. Разработка программы на языке Pascal. Поиск наибольшего элемента.
лабораторная работа [123,5 K], добавлен 15.01.2014Программа обработки одномерного массива средствами Visual Basic for Application (VBA) на предмет преобразования, печати, удаления, сортировки, поиска сумм, положительных, чётных элементов, их кратности и дополнения другими элементами и значениями данных.
контрольная работа [12,3 K], добавлен 07.10.2012Анализ различных способов хранения информации: одномерный массив, типизированный файл и динамический список. Сортировка только положительных чисел. Словесное описание алгоритма. Блок-схема процедуры обработки данных с помощью одномерного массива.
контрольная работа [319,7 K], добавлен 29.05.2014
