Файл: Исследование алгоритмов поиска и сортировки данных..pdf

Универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например из файла, сокета или консоли).

Например, исходная последовательность имеет вид:

4, 3, 5, 1, 7, 8, 6, 2

Корнем дерева будет начальный элемент последовательности. Далее все элементы, меньшие корневого, располагаются в левом поддереве, все элементы, большие корневого, располагаются в правом поддереве. Причем это правило должно соблюдаться на каждом уровне (Рисунок 4).

Рисунок 4 Сортировка деревом.

Для этой сортировки даже не обязательно выучить структуры данных типа «дерево»: дерево можно организовать на массиве. Это дерево — просто удобное представление массива, а не реальная структура данных в памяти компьютера. Такое дерево будет плоским и ветвистым, что, несомненно, эффективно для хранения данных. Будем заполнять дерево следующим образом. Берём элементы входных данных тройками, и максимальный из них ставим над двумя другими. Вставляем эту тройку в массив. Если в воображаемом дереве при этом нарушается порядок следования чисел, то нужно менять местами соответствующие элементы, пока порядок не будет восстановлен. Легче всего это показать на анимированном примере.

1.8. Сортировка подсчётом

Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла[уточнить], так как каждый элемент придётся просматривать более одного раза.

Сортировка подсчётом также называется countsort. Для каждого элемента вводится число, которое хранит количество раз, когда этот элемент встретился в массиве. Пройдёмся в цикле по массиву и заполним все такие числа. После этого наберём новый массив, заполненный соответствующими количествами элементов. Такая процедура эквивалент- на сортировке исходного массива. Пусть исходный массив состоит из чисел от 0 до 19. Для того, чтобы его отсортировать, заведём ещё один массив из 20 целых чисел. Заполним его так, как только что было описано. После этого запишем в новый массив столько чисел от 0 до 19, сколь- ко их было подсчитано при заполнении массива из 20 элементов. Например, если нулей встретилось 4, то в позиции 0, 1, 2 и 3 нового массива нужно поставить нули. Если число единиц равно 3, то следующие три позиции будут заняты единицами, и т. д. Сортировка подсчётом эффективна тогда, когда элементы массива входных данных имеют ограниченный диапазон и повторяются. Если же элементы могут принимать широкий диапазон значений, или количество повторов чисел мало, то эта сортировка невыгодна. Стабильность алгоритма может быть достигнута, если использовать допол- нительную память, в противном случае алгоритм нестабилен. Времен- на́я сложность алгоритма — ????(????).

1.9. Поразрядная сортировка

Алгоритм сортировки за линейное время. Поразрядная сортировка (radixsort) имеет два варианта: 1. если сначала сортировка производится по младшим разрядам, затем по старшим, то это LSD (least significant digit); 2. если сначала сортировка производится по старшим разрядам, а затем по младшим, то это MSD (most significant digit). Эта сортировка применима в случае, когда, например, нужно отсортировать миллион трёхзначных чисел. В случае LSD применим сортировку подсчётом сначала по единицам, потом — по десяткам, потом — по сотням. При этом нужен вспомогательный массив размером в 10 элементов. После того, как произведена сортировка по единицам, взаимное расположение чисел по единицам в дальнейшем сохраняется, то же самое и для десятков. Можно взять не десятичную разрядность, а, например, шестнадцатеричную. Тогда вспомогательный массив вводится не на 10, а на 16 элементов. Алгоритм поразрядной сортировки, как и сортировка подсчётом, работает за линейное время.

1.10. Сортировка корзинками

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

Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.

Сортировка корзинками также называется basketsort. Этот алгоритм удобно проиллюстрировать на примере стирки в семье с 12 детьми. Если постирать чьи-то джинсы с чьим-то белым платьем, то после этого начнутся внутрисемейные конфликты. Нужно распределить всю одежду для стирки на несколько корзинок. В одну корзину пойдут грязные немаркие вещи, в другую — белую одежду. Пусть все элементы (для определённости, числа) могут принимать малый диапазон значений. Разобьём числа на «корзинки»: от 0 до 2, от 3 до 5, от 6 до 8. Для каждой корзинки заводим свой упорядоченный список чисел. Каждый элемент из входного массива попадает в одну корзинку и занимает своё место в соответствующем списке. После этого списки всех корзинок склеиваются вместе, и получается отсортированный массив. Этот алгоритм лучше всего работает, когда в каждую корзинку попадает примерно одинаковое количество элементов. Если же входные данные разбросаны неравномерно, например, большое количество данных в одной-двух корзинках, то сортировка работает медленно.

Сложности алгоритмов удобно изобразить в виде таблицы (Рисунок 5). Заметим, что в худшем случае быстрая сортировка quicksort даёт сложность ????(????2 ).

Рисунок 5 Сложности алгоритмов.

Если производительность библиотечного алгоритма сортировки имеет значение, то нужно ознакомиться с тем, как он устроен, прежде чем использовать в программе. За стандартной функцией qsort в некоторых языках скрывается не быстрая сортировка, а другие алгоритмы. При выборе алгоритма сортировки нужно учитывать специфику конкретной задачи, понимать, какие данные нужно сортировать, и насколько важны скорость алгоритма и объём дополнительной памяти, которые он требует.

ГЛАВА II. РАЗРАБОТКА КОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ НА СОРТИРОВКУ

Задача 1. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку методом линейной сортировки по невозрастанию и выводит отсортированный массив на экран.

program Sort_Lin;

crt;

Count=20;

M:array [1..Count] of byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9, 12,20,20,19,2,5);

I, J, N, L: Byte;

A: integer;;(Исходный массив:);I:=1 to Count do Write( , M[I]); Writeln;:=0;I:=1 to Count-1 do

for J:=I+1 to Count do

begin

A:=A+1;

if M[I] < M[J] then

begin

N:=M[I];

M[I]:=M[J];

M[J]:=N;

end;

for L:=1 to Count do Write( , M[L]); Writeln(Число итераций=, A);

end;;.

Задача 2. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку методом пузырька по невозрастанию и выводит отсортированный массив на экран.

program Sort_Puz;

uses;

const

Count=10;

M:array [1..Count] of byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18);

var

I, J, K, L: Byte;

A: integer;

ClrScr;

Writeln(Исходный массив);

for I:=1 to Count do Write(M[I], ); Writeln;

A:=0;

for I:=2 to Count do

begin

for J:=Count downto I do

begin

A:=A+1;

if M[J-1]<M[J] then

begin

K:=M[J-1];

M[J-1]:=M[J];

M[J]:=K;

for L:=1 to Count do Write( , M[L]);(Число итераций =, A);

end;

end;;.

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

{ быстрая сортировка }

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

procedure qs(l, r: integer; var it: DataArray);
var

i, j: integer;

x, y: DataItem;

begin

i:=l; j:=r;

x:=it[(l+r) div 2];

repeat

while it[i]<x do i := i+1;

while x<it[j] do j := j-1;

if y<=j then

begin

y := it[i];

it[i] := it[j];

it[j] := y;

i := i+1; j := j-1;

end;

until i>j;

if l<j then qs(l, j, it);

if l<r then qs(i, r, it)

end;

begin

qs(1, count, item);

end; { конец быстрой сортировки }

Задача 4. Составить программу, которая формирует двумерный массив случайных чисел и вычисляет значение среднего арифметического его элементов, больших, чем 20. Решение задачи сводится к последовательному перебору всех элементов массива с вычислением суммы тех элементов, значение которых больше, чем 20, а по окончании их суммирования - к вычислению частного полученной суммы и количества элементов массива, удовлетворяющих условию суммирования.

program Preobr_Mas_2;

Strok=10;=Strok;

array [1. .Strok, 1. .Stolb] of integer;

C: array [1. .Strok*6] of integer;

J, X,Y: integer;;;I:= 1 to Strok doJ:= 1 to Stolb do [I, J] :=Random(99);

(A[ I, J] :2, ' ');;;;;:= 0;:= 0;I:=1 to Strok doJ:= 1 to Stolb doJ >=I then:= X+1;[X] := A[I,J];:= Y+1;

C[Y] := A[I,J];

end;

Writeln('Элементы расположенные на главной диагонали и выше: ');

for I:=1 to X do Write(B[I]:2,' ');

Writeln;('Элементы, расположенные ниже главной диагонали: ') ;

for I:=1 to Y do Write(C[I]:2,' ');

Writeln;;.

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

#include <stdio.h>
void selectionSort(int *num, int size) {

int i, j;

int min, temp;

for (i = 0; i < size-1; i++) {

min = i;

for (j = i+1; j < size; j++) {

if (num[j] < num[min])

min = j;

}

temp = num[i];

num[i] = num[min];

num[min] = temp;

}

}
int main() {

int a[10];

int i, j, index;

for(i=0;i<10;i++) {

printf("a[%d] = ", i);

scanf("%d",&a[i]);

}

selectionSort(a,10);

for(i=0;i<10;i++)

printf("%d ", a[i]);

getchar();getchar();

return 0;
}

Задача 6. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку слиянием по невозрастанию и выводит отсортированный массив на экран.

void merge(int *a, int n) {

int mid = n/2;

if(n%2==1)

mid++;

int h = 1; // шаг

int *c;

int step;

c = (int*)malloc(n*sizeof(int));

while(h < n) {

step = h;

int i = 0;

int j = mid;

int k = 0;

while(step <= mid) {

while((i<step) && (j<n) && (j<(mid+step))) {

if(a[i] < a[j]) {

c[k] = a[i];

i++; k++;

} else {

c[k] = a[j];

j++; k++;

}

while(i<step) {

c[k] = a[i];

i++;k++;

}

while((j < (mid+step)) && (j<n)) {

c[k] = a[j];

j++; k++;

}

step = step + h;

}

h = h * 2;

for(i=0;i<n;i++)

a[i]=c[i];

}

Задача 7. Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку подсчетом по невозрастанию и выводит отсортированный массив на экран.

#include <iostream>

using namespace std;

int a[100];

int c[100];

int main()

{

int n;//количество элементов в массиве

int k = 100;

cin >> n;

//считываем массив

for(int i = 0; i < n; i++)

{

cin>>a[i];

}

//строим массив с

for(int i = 0; i < n; i++)

{

c[a[i]]++;

}

//бежимся по всему отрезку

//с 0 до k-1

for(int i = 0; i < k; i++)

{

//выводим i c[i] раз

for(int j = 0; j < c[i]; j++)

cout<<i<<" ";

}

return 0;

}

ЗАКЛЮЧЕНИЕ

Для реализации различных методов сортировки необходимо применить алгоритмические языки программирования, такие как: Delphi, Pascal, С++. Применение различных языков программирования, в данной курсовой работе, необходимо для понимания самого алгоритма без привязки к лексике языка программирования.

В результате выполнения курсового проекта были написаны программы, выполняющие сортировку массивов различными методами. Программы обладают высокими параметрами быстродействия, маленькими размерами и не требовательны к системным ресурсам компьютера

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Абрамов. С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987.- 112с.

2. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. - М.Наука, 1988. - 224 с.

3. Алексеев Е.С., Мячев А.А. Англо-русский толковый словарь по системотехнике ЭВМ. - М.: Финансы и статистика, 1993. - 256 с.

4. Борковский А.Б. Англо-русский словарь по программированию и информатике (с толкованиями). - М.: Русский язык, 1990. - 333 с.

5. Васюкова Н.Д., Тюяева В.В. Практикум по основам программирования. Язык Паскаль: Учеб. пособ. для учащихся средн. спец. уч. завед. М.Высшая школа, 1991.- 160с.

6. Вирт Н. Язык программирования Паскаль // Алгоритмы и организация решения экономических задач.

7. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. - М.: Мир, 1985. - 406 с,

8. Григас Г. Начала программирования: Книга для учащихся : Пер. с лит. / Под ред. Ю.А.Первина. - М.: Просвещение, 1987.-112 с.