Алгоритм быстрой сортировки.

Что бы смотреть урок полностью, подпишитесь на платный раздел.

В платном разделе статья находиться здесь.

Исходники к уроку можно скачать в платном разделе.

Алгоритм сортировки, который мы рассмотрим в данном уроке, считается одним из самых лучших алгоритмов сортировки. Этот алгоритм называется алгоритм быстрой сортировки. В его основе лежит идея ...

...

... И так, теперь будем тестировать алгоритм. Пример для проверки правильности его работы (делаем все это в примере из прошлого урока, заменив в нем обработчик нажатия на кнопочку "Старт":

//обработчик нажатия на кнопку "пуск"

private void btnStart_Click(object sender, EventArgs e)

{

lbIntAfter.Items.Clear();

lbIntBefore.Items.Clear();

lbStringAfter.Items.Clear();

lbStringBefore.Items.Clear();

InitInt(amount);

InitString(amount);

ShowInt(lbIntBefore, intsort.list);

ShowString(lbStringBefore, stringsort.list);

intsort.QuickSort(0,amount-1);

stringsort.QuickSort(0, amount - 1);

ShowInt(lbIntAfter, intsort.list);

ShowString(lbStringAfter, stringsort.list);

}

И убеждаемся, что все работает правильно:

Напишем процедуру тестирования:

private void btnQuick_Click(object sender, EventArgs e)

{

int count = 10000;

InitInt(count);

DateTime dt1 = DateTime.Now;

intsort.QuickSort(0, count-1);

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. " +

" Время нач. сортировки: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

Теперь проверим время выполнения при разном количестве сортируемых элементов:

Количество элементов	Время
10000	менее 1 сек
100000	менее 1 сек
1 млн.	≈1 сек
10 млн.	13 сек
20 млн.	25 сек
50 млн	66 сек

Как видим, время сортировки почти пропорционально количеству элементов. На самом же деле, сложность этого алгоритма в среднем случае ...

...

Последнее обновление ( 27.01.2013 г. )

« След.		Пред. »

Вернуться