Быстрая сортировка. Совет по повышению эффективности

Совет по повышению эффективности

Замечание по технике программирования

Типичная ошибка программирования

Совет по повышению эффективности

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

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

Хорошая техника программирования важна. Часто важна и высокая производительность. К несчастью, эти цели часто не coвмecтимы друг с другом. Хорошая техника программирования - это ключевой момент в вопросе управления созданием все более сложных и крупных программных систем. Высокая производительность этих систем - ключ к созданию систем будущего, которые предъявят еще большие требования к аппаратным средствам. Что же важнее?

Функционализация программ в четком иерархическом стиле - свидетельство хорошей техники программирования. Но за все надо платить.

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

Быстрая сортировка - это один из наиболее эффективных алгоритмов сортировки. При быстой сортировке используется следующая стратегия:

1. Массив разбивается на меньшие подмассивы
2. Подмассивы сортируются
3. Отсортированные подмассивы объединяются

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

Алгоритм:

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

Пример алгоритма нахождения точки разбиения:

1. Выбрать первый элемент данных как точку разбиения. Point = A[first].
2. Инициализировать два указателя поиска, i и j, чтобы i = first (наименьший индекс подмассива), а j = last (наибольший индекс подмассива).
3. Используя указатель поиска i, найти, начиная слева, элемент данных, который будет больше или равен точке разбиения (Point).
4. Используя указатель поиска j, найти, начиная справа, элемент данных, который будет меньше или равен точке разбиения (Point).
5. Если i < j, то поменять местами A[i] и A[j].
6. Повторить пункты 2 - 4, пока не выполнится условие i > j.
7. Поменять местами точку разбиения и A[j].

Пример:

Возьмем массив из чисел:

-1

Поиск точки разбиения:

Point
		-1
i									j

Движение

Point
		-1
			i						j

Обмен:

Point
		-1
			i						j

Движение:

Point
		-1
					i			j

Обмен:

Point
		-1
					i			j

Движение:

Point
		-1
							j	i

Обмен:

A.

							Point
		-1

A1. Левый подмассив

-1

Поиск точки разбиения:

Point
		-1
i						j

Движение:

Point
		-1
			i			j

Обмен:

Point
		-1
			i			j

Движение:

Point
		-1
			j	i

Обмен:

B.

			Point
		-1

B1. Левый подмассив

-1

Поиск точки разбиения:

Point
		-1
i		j

Движение:

Point
		-1
	i	j

Обмен:

Point
	-1
	i	j

Движение:

Point
	-1
	j	i

Обмен:

C.

	Point
-1

C1. Левый подмассив

-1

C2. Правый подмассив

B2. Правый подмассив

Поиск точки разбиения:

Point
i		j

Движение:

Point
j	i

Обмен:

D.

Point

D. Правый подмассив

Поиск точки разбиения:

Point
i	j

Движение:

Point
	i j

Обмен:

E.

	Point

E. Левый подмассив

A2. Правый подмассив

Поиск точки разбиения:

Point
i	j

Движение:

Point
j	i

Обмен:

F.

Point

F. Правый подмассив

Массив отсортирован

-1

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

// Быстрая сортировка #include <iostream.h>#include <iomanip.h>#include <stdlib.h>#include <time.h> template <typename T>void QSort(T array[] /* Сортируемый массив */, int first /* Начальный индекс */, int last /* Конечный индекс */){ if(first < last) { // Переменная для просмотра массива слева int i; // Переменная для просмотра массива справа int j; // Временная переменная для обмена значений элементов T temp; // Элемент - точка разбиения массива T point; // Принимаем за точку разбиения первый элемент массива // (можно выбрать любой) point = array[first]; i = first; j = last; while(i < j) { // Ищем слева элемент, который >= точки разбиения while(array[i] <= point && i < last) i++; // Ищем справа элемент, который <= точки разбиения while(array[j] >= point && j > first) j--; if(i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; } } // Помещаем точку разбиения в правильную позицию, // т. е. все элементы слева не больше нее, а // все элементы справа не меньше нее /* Примечание!!! */ // Использовать переменную point нельзя, так как она всего // лишь копия элемента массива, являющегося точкой разбиения /*****************/ temp = array[first]; array[first] = array[j]; array[j] = temp; // Сортируем левый и правый подмассивы QSort(array, first, j - 1); QSort(array, j + 1, last); }} // Функция для вывода массиваtemplate <typename T>void PrintArray(T array[], int size){ // функция setw(n) создает поле для вывода с шириной n символов for(int i = 0; i < size; i++) { if(i % 5 == 0) cout << endl; cout << setw(15) << array[i]; } cout << endl;} // Тестированиеvoid main(){ // Инициализация генератора случайных чисел srand(time(0)); // Размер массивов const N = 10; int i; int a[N]; float b[N]; // Инициализация массивов случайными числами в диапазоне от -10 до 10 for(i = 0; i < N; i++) { a[i] = rand() % 21 - 10; b[i] = rand() / (float)32767 * 20 - 10; } // Вывод массивов cout << "Array A: "; PrintArray(a, N); cout << "Array B: "; PrintArray(b, N); // Сортировка массивов QSort(a, 0, N - 1); QSort(b, 0, N - 1); // Вывод отсортированных массивов cout << endl; cout << "Array A: "; PrintArray(a, N); cout << "Array B: "; PrintArray(b, N); }

Дата добавления: 2014-01-14