Быстрая сортировка
Совет по повышению эффективности
Замечание по технике программирования
Типичная ошибка программирования
Совет по повышению эффективности
Избегайте использования рекурсий в случаях, когда требуется высокая эффективность. Рекурсивные вызовы требуют времени и дополнительных затрат памяти.
Случайный вызов нерекурсивной функции самой себя либо непосредственно, либо косвенно, через другую функцию.
Хорошая техника программирования важна. Часто важна и высокая производительность. К несчастью, эти цели часто не coвмecтимы друг с другом. Хорошая техника программирования - это ключевой момент в вопросе управления созданием все более сложных и крупных программных систем. Высокая производительность этих систем - ключ к созданию систем будущего, которые предъявят еще большие требования к аппаратным средствам. Что же важнее?
Функционализация программ в четком иерархическом стиле - свидетельство хорошей техники программирования. Но за все надо платить.
Программа, разбитая на множество функций, потенциально требует большего количества вызовов функций по сравнению с монолитной программой без функций. Это увеличивает время выполнения и затраты памяти компьютера. Но монолитные программы трудно программировать, тестировать, отлаживать, сопровождать и развивать. Так что функционализируйте ваши программы с учетом здравого смысла, всегда учитывая хрупкий баланс между производительностью и хорошей техникой программирования.
Быстрая сортировка - это один из наиболее эффективных алгоритмов сортировки. При быстой сортировке используется следующая стратегия:
- Массив разбивается на меньшие подмассивы
- Подмассивы сортируются
- Отсортированные подмассивы объединяются
Быструю сортировку можно реализовать несколькими способами, но цель каждого подхода будет заключаться в выборе элемента данных и помещении его в правильную позицию (этот элемент будет называться точкой разбиения), таким образом, чтобы все элементы слева от точки разбиения оказались меньше (или предшествовали) точки разбиения, а все элементы справа от точки разбиения оказались больше (или следовали за) точки разбиения. Способ выбора точки разбиения оказывает огромное влияние на производительность сортировки. Рассмотрим рекурсивную реализацию быстрой сортировки.
Алгоритм:
- Выбрать элемент данных и сделать его точкой разбиения таким образом, чтобы он разбивал массив на левый и правый подмассивы, как было описано выше.
- Применить быструю сортировку к левому подмассиву.
- Применить быструю сортировку к правому подмассиву.
Пример алгоритма нахождения точки разбиения:
- Выбрать первый элемент данных как точку разбиения. Point = A[first].
- Инициализировать два указателя поиска, i и j, чтобы i = first (наименьший индекс подмассива), а j = last (наибольший индекс подмассива).
- Используя указатель поиска i, найти, начиная слева, элемент данных, который будет больше или равен точке разбиения (Point).
- Используя указатель поиска j, найти, начиная справа, элемент данных, который будет меньше или равен точке разбиения (Point).
- Если i < j, то поменять местами A[i] и A[j].
- Повторить пункты 2 - 4, пока не выполнится условие i > j.
- Поменять местами точку разбиения и 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); }