Сортировка массива по возрастанию методом Хоара

Kordan

Feb 3rd, 2018

585

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 4.91 KB | None | 0 0

raw download clone embed print report

/*
* Kordan C++ ************************************************************
* Программа заполнения массива определенного размера случайными числами *
* и его сортировка по возрастанию методом Хоара *
* ***********************************************************************
*/
#include <iostream>
#include <cstdlib> // содержит srand() и rand()
#include <ctime> // содержит time()
using namespace std;
int FillArray (int *arr, const int size, const int min_range, const int max_range);
void quickSort (int *arr, int begin, int end);
void print (int *arr, int size);
int main () {
setlocale (LC_ALL, "RUS");
// Количество чисел в массиве
const int SIZE = 13;
// Минимальное число в массиве
const int MIN_RANGE = 13;
// Максимальное число в массиве
const int MAX_RANGE = 81;
int list[SIZE];
if (FillArray (list, SIZE, MIN_RANGE, MAX_RANGE) != 1) {
// Выводим значения исходного массива
print (list, SIZE);
// Сортируем массив по возрастанию
quickSort (list, 0, SIZE - 1);
// Выводим значения отсортированного массива
print (list, SIZE);
}
cout << endl << endl;
//system ("pause");
return 0;
}
// -- Kordan С++ -----------------------------------------
// Функция заполнения массива случайными целочисленными -
// значениями в диапазоне чисел -
// -
// Необходимо подключить: -
// #include <cstdlib> (содержит srand() и rand()) -
// #include <ctime> (содержит time()) -
// -
// Аргументы функции: -
// *arr - Имя массива -
// size - Размер массива -
// min_range - Минимальное значение диапазона -
// max_range - Максимальное значение массива -
// -- begin ----------------------------------------------
int FillArray (int *arr, const int size, const int min_range, const int max_range) {
// Автоматическая рандомизация
srand (time (0));
for (int i = 0; i < size; i++) {
if (min_range <= max_range) arr[i] = min_range + rand () % (max_range + 1 - min_range);
else {
cout << "Ошибка!\nМаксимальное значение диапазона чисел должно быть больше минимального!\n";
return 1;
}
}
}
// -- end --
// -- Kordan C ++ ---------------------------------------
// Функция вывода на консоль значений элементов массива -
// -
// Аргументы функции: -
// *arr - Имя массива -
// size - Размер массива -
// -- begin ---------------------------------------------
void print (int *arr, int size) {
for (int i = 0; i < size; i++) {
cout << *(arr + i) << " ";
}
cout << endl << endl;
}
// -- end --
// -- Kordan C ++ -----------------------------------
// Функция сортировки массива определенного размера -
// методом Хоара -
// -
// Аргументы функции: -
// *arr - Имя массива -
// begin - Начало массива -
// end - Конец массива -
// -
// Пример использования: -
// quickSort (list, 0, SIZE - 1); -
// -- begin -----------------------------------------
void quickSort (int *arr, int begin, int end) {
int first = begin, last = end;
int piv = arr[(first + last) / 2];
while (first <= last) {
while (arr[first] < piv) first++;
while (arr[last] > piv) last--;
if (first <= last) swap (arr[first++], arr[last--]);
}
if (begin < last) quickSort (arr, begin, last);
if (end > first) quickSort (arr, first, end);
}
// -- end --

Add Comment

Please, Sign In to add comment