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

Министерство образования Российской Федерации

Владивостокский государственный университет экономики и сервиса

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

курсовая работа

по дисциплине

«Алгоритмизация и программирование»

Выполнил:

студент гр. ИТ-0401

Иванова Т.А.

Проверил:

доцент. каф. ИСКТ

к.т.н. Гриняк В.М.

Владивосток 2006

ВВЕДЕНИЕ

Целью курсовой работы является закрепление основ и углубление знаний приемов программирования на алгорит­мических языках высокого уровня, получение практических на­выков в создании программного продукта, отработка приёмов проведения вычислительных экспериментов на ЭВМ.

Данная курсовая работа содержит в себе два программы, сортирующих массив со случайными числами. В первой программе описана сортировка методом вставок, во второй – пузырьковая сортировка. Для того чтобы выяснить, какая сортировка эффективнее, производится подсчет среднего числа сравнений, необходимого для сортировки n элементов тем и другим алгоритмом.

ПОСТАНОВКА ЗАДАЧИ

Сравнить эффективность алгоритмов сортировки – пузырьковой и сортировки вставками.

ОПИСАНИЕ РЕШЕНИЯ ЗАДАЧИ

СОРТИРОВКА ВСТАВКАМИ

Сортировка вставками элементов a₁, a₂, …, a_n относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a₀=-, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент a_j временно размещается в переменной w, и просматриваются элементы a_j-1, a_j-2, …,a₁ (уже к этому времени упорядоченные). Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w.

//----------------------------------------------

for (j=2; j

{

w=a[j]; i=j-1;

while(w

a[i+1]=w;

};

//----------------------------------------------

Сложность алгоритма определяется числом проверок условия w

ПУЗЫРЬКОВАЯ СОРТИРОВКА

Метод пузырьковой сортировки последовательности a₁, a₂, …, a_n представляет собой систематический обмен местами слева направо смежных элементов, не отвечающих выбранному порядку, до тех пор, пока они не оказываются на правильном месте. Большие элементы при этом как бы «всплывают пузырьками вверх» в конец списка. В приведённом ниже алгоритме используется переменная b, значение которой содержит число ещё не отсортированных элементов

//---------------------------------------

b=n;

while (b!=0)

{

t=0;

for(j=1;j

{

if (a[j]>a[j+1]) {w=a[j]; a[j]=a[j+1]; a[j+1]=w; t=j;};

}

b=t;

}

//--------------------------------------------

Сложность данного алгоритма определяется числом проверок условия a[j]>a[j+1] в цикле и является квадратичной O(n²). Число реально проделанных сравнений существенно зависит от первоначального расположения элементов массива.

Рассмотренный ниже другой алгоритм так называемой «полной» пузырьковой сортировки является наиболее популярным и легко программируемым её вариантом.

//-----------------------------------

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

{

for(j=1;j<=n-i; j++)

{

if (a[j]>a[j+1]) {w=a[j];a[j]=a[j+1];a[j+1]=w;};

}
}

//-------------------------------------

Сложность приведённого алгоритма определяется числом сравнений a[j]>a[j+1]. Она остаётся постоянно равной n(n-1)/2 (то есть квадратичной) и не зависит от расположения исходных данных.

ЗАКЛЮЧЕНИЕ

Основываясь на результатах среднего числа сравнений можно сделать вывод, что сортировка вставками эффективнее пузырьковой сортировки. Это видно и из графика приведенного ниже:

СПИСОК ЛИТЕРАТУРЫ

1. Лекции по курсу «Алгоритмизация и программирование. Структуры и алгоритмы компьютерной обработки данных».

2. Б.Н. Иванов Дискретная математика. Алгоритмы и программы: Учеб. пособие. – Владивосток: Изд-во ДВГТУ, 2000.