Сортировка данных в массиве

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: сочинение рассуждение, реферат молодежь
| Добавил(а) на сайт: Funtusov.

Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата

Рис.4

Затем происходит обмен значениями центрального элемента A[0] с A[scanDown]:

Swap(A[0], A[scanDown]);

В результате у нас появляются два подсписка A[0] – A[5] и A[6] – A[9], причем все элементы первого подсписка меньше элементов второго, и последний элемент первого подсписка является его наибольшим элементом. Таким образом, можно считать, что после проделанных операций подсписки разделены элементом А[5] = 550 (рисунок 5). Если теперь отсортировать каждый подсписок по отдельности, то у нас получится полностью отсортированный массив. Заметьте, что по сути оба этих подсписка являются такими же массивами, как и исходный, поэтому к ним можно применить тот же самый алгоритм. Применение того же алгоритма к частям массива называется рекурсивной фазой.

Рекурсивная фаза

Одним и тем же методом обрабатываются два подсписка: Sl(A[0] – A[4]) и Sh(A[6] – A[9]). Элемент А[5] обрабатывать не надо, так как он уже находится на своем месте.

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

Рис.5

Алгоритм QuickSort

Этот рекурсивный алгоритм разделяет список A[low]--A[high] по центральному элементу, который выбирается из середины списка

mid = (high + low) / 2;

pivot = A[mid];

После обмена местами центрального элемента с A[low], задаются начальные значения индексам scanUp = low + 1 и scanDown = high, указывающим на начало и конец списка, соответственно. Алгоритм управляет этими двумя индексами. Сначала scanUp продвигается вверх по списку, пока не превысит значение scanDown или пока не встретится элемент больший, чем центральный.

while (scanUp <= scanDown && A[scanUp] <= pivot)

scanUp++;

После позиционирования scanUp индекс scanDown продвигается вниз по списку, пока не встретится элемент, меньший или равный центральному.

while (pivot < A[scanDown])

scanDown--;

По окончании этого цикла (и при условии что scanUp < scanDown) оба индекса адресуют два элемента, находящихся не в тех подсписках. Эти элементы меняются местами.

Swap(A[scanUp], A[scanDown]);

Обмен элементов прекращается, когда scanDown становится меньше, чем scanUp. В этот момент scanDown указывает начало левого подсписка, который содержит меньшие или равные центральному элементы. Индекс scanDown становится центральным. Взять центральный элемент из A[low]:

Swap(A[low], A[scanDown]);

Для обработки подсписков используется рекурсия. После обнаружения точки разбиения мы рекурсивно вызываем QuickSort с параметрами low, mid-1 и mid+1, high. Условие останова возникает, когда в подсписке остается менее двух элементов, так как одноэлементный или пустой массив упорядочивать не нужно.

// Swap меняет местами элементы массива. Соответствующий тип данных

// должен поддерживать операцию «=».

Рекомендуем скачать другие рефераты по теме: инвестиции реферат, реферат память.

Claw.ru | Рефераты по информатике, программированию | Сортировка данных в массиве

Сортировка данных в массиве

Рекурсивная фаза

Категории:

Поделитесь этой записью или добавьте в закладки

Рефераты от А до Я

Полезные заметки