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

ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Исходные данные

Исходным массивом будет являться следующий массив целочисленных значений:

Реализация метода вывода значений массива на дисплей:

voidprintArray(int* arr, int size)

{

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

std::cout<<arr[i] <<" ";

}

std::cout<<std::endl;

}

2.2 Реализация алгоритмов сортировки на языке C++

2.1.1 Сортировка пузырьком

Реализация алгоритма:

voidbubbleSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size - 1; ++i) // i - номерпрохода

{

for(int j = 0; j <size - 1; ++j) // внутренний цикл прохода

{

if (arr[j + 1] <arr[j])

{

tmp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = tmp;

}

}

}

std::cout<<"Sortirovkapyzirkem"<<std::endl;

}

Результат работы:

2.1.2 Сортировка методом вставок

Реализация алгоритма:

voidinsertSort(int* a, int size)

{

inttmp;

for (int i = 1, j; i < size; ++i) // циклпроходов, i - номерпрохода

{

tmp = a[i];

for (j = i - 1; j >= 0 && a[j] >tmp; --j) // поиск места элемента в готовой последовательности

a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли

a[j + 1] = tmp; // место найдено, вставить элемент

}

std::cout<<"Sortirovkavstavkami"<<std::endl;

}

Результат работы:

2.1.3 Сортировка методом выбора

Реализация алгоритма:

voidselectSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

intpos = i;

tmp = arr[i];

for(int j = i + 1; j <size; ++j) // цикл выбора наименьшего элемента

{

if (arr[j] <tmp)

{

pos = j;

tmp = arr[j];

}

}

arr[pos] = arr[i];

arr[i] = tmp; // меняемместаминаименьшийс a[i]

}

std::cout<<"Sortirovkaviborom"<<std::endl;

}

Результат работы:

2.2 Сравнение эффективности алгоритмов

Было проведено сравнение алгоритмов сортировки, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n²) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n²). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 2.1.

Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой и сортировки вставками, зато сортировка выбором выполняется, как обычно.

Таблица 2.1 – Сравнение алгоритмов

ЗАКЛЮЧЕНИЕ

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

1. среднее время выполнения алгоритма
2. наибольшее значение времени выполнения алгоритма
3. объем занимаемой оперативной памяти
4. скорость оперирования сортируемыми данными
5. специфичность области и среды применения алгоритма

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

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