Уроки C++

Быстрая сортировка C++

“Быстрая” сортировка считается одной из самых эффективных. Идея работы её алгоритма следующая:
  1.Исходный массив разбивается на меньшие подмассивы;
    2.Происходит сортировка подмассивов, в заданном направлении;
      3.Отсортированные подмассивы объединяются в один конечный массив;
Вот код данной сортировки:

---

#include "stdafx.h"
#include "iostream"
#include "time.h"
#include "iomanip"

using namespace std;

void QuickSort(int *, int);   // объявление функции сортировки

int main()
{
setlocale(LC_ALL, "Russian");
int n; // Количество элементов массива
cout << "Введите размер массива: ";
cin >> n;
cout << endl;
cout << "Массив: " << endl;
int *mas = new int [n];
srand(time(NULL));
for (int i = 0; i < n; i++)
{
mas[i] = rand() % 200 - 100;   // заполняем массив случайными числами
cout << mas[i] << " ";   /// выводим массив на экран
}
cout << "\n\n";

QuickSort(mas, 0, n-1);   /// вызываем функцию Быстрой сортировки
cout << "Отсортированный массив: " << endl;
for (int i = 0; i < n; i++)
{
cout << mas[i] << " ";   /// Вывод на экран отсортированного массива
}
cout << "\n";
system("PAUSE");
return 0;
}

void swap(int *x, int *y)   /// описываем функцию swap
{
int z;
z=*x;
*x=*y;
*y=z;
}
void QuickSort(int* sort_el, int first, int last)
{
int i = first, j = last, x = sort_el[(first + last) / 2];

do {
while (sort_el[i] < x) i++;
while (sort_el[j] > x) j--;

if(i <= j) {
if (i < j) swap(sort_el + i, sort_el + j);
i++;
j--;
}
} while (i <= j);

if (i < last)
QuickSort(sort_el, i, last); if (first < j) QuickSort(sort_el, first,j); }

---

Результат:



<< К списку сортировок

---