Задача 3 (24). Дан массив чисел. Расставить их по возрастанию.
3.1. Постановка задачи. Сортировка массивов – это одна из основных операций во многих достаточно сложных программах. Она в обязательном порядке реализована в базовых библиотеках любого современного языка. Существует множество разных алгоритмов сортировки массивов, неэквивалентных с точки зрения вычислительной сложности. Одним из самых широко известных алгоритмов, вычислительно эффективных «в среднем» для достаточно больших массивов, является так называемая «быстрая сортировка» или qsort. Это классический алгоритм использующий стратегию «разделяй и властвуй». Мы его и будем реализовывать.
3.2. Алгоритм. Мы используем рекурсию, поэтому сначала приводим блок– схему основной части алгоритма:
Затем
приводим блок–схему собственно процедуры
qsort (вернее её часть):
Вторая
часть блок-схемы процедуры qsort:
3.3. Текст программы (C++).
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <assert.h>
static void qsort(int* p_data, const long low, const long high) {
long
i = low; long j = high;
const int z = p_data[(low + high) / 2];
do { while (p_data[i] < z) i++;
while (p_data[j] > z) j-- ; if (i <= j) {
const int y = p_data[i]; p_data[i] = p_data[j]; p_data[j] = y;
i++; j-- ;}}
while (i <= j);
if (low < j) qsort(p_data, low, j);
if (i < high) qsort(p_data, i, high);}
int main() {
std::cout << "Быстрая сортировка массива." << std::endl;
std::vector<int> a; while (true) {
std::cout
<< "Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : "; std::string s; std::cin >> s; if (s == "*") {
break;}
a.push_back(atoi(s.c_str())); }
qsort(&a[0], 0, (int)a.size() - 1);
std::cout << "Отсортированный массив: "; for (int i = 0; i < a.size(); i++) {
std::cout << a[i] << " "; }
std::cout << std::endl; return 0; }
3.4. Результат работы программы (C++).
$ g++ -o qsort ./qsort.cpp $ ./qsort
Быстрая сортировка массива.
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 2
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 7
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 9
Введите
элемент массива и нажмите <Enter> (или
ведите <*>+<Enter> для завершения) : 3
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 11
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 4
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 2
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 2
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 1
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 5
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : 15
Введите элемент массива и нажмите <Enter> (или ведите <*>+<Enter> для завершения) : *
Отсортированный массив: 1 2 2 2 3 4 5 7 9 11 15