Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.
Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим. Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа — большие (предполагается, что массив сортируется по возрастанию).
Тем самым массив разбивается на две части:
- не отсортированные элементы слева от разрешающего элемента;
- не отсортированные элементы справа от разрешающего элемента.
Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.
Если требуется сортировать больше одного элемента, то нужно
- выбрать в массиве разрешающий элемент;
- переупорядочить массив, помещая элемент на его окончательное место;
- отсортировать рекурсивно элементы слева от разрешающего;
- отсортировать рекурсивно элементы справа от разрешающего.
Ключевым элементом быстрой сортировки является алгоритм переупорядочения.
Рассмотрим сортировку на примере массива:
10, 4, 2, 14, 67, 2, 11, 33, 1, 15.
Для реализации алгоритма переупорядочения используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.
Пусть крайний левый элемент — разрешающий pivot. Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.
Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.
Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.
Эти элементы меняются местами и движение указателей возобновляется.
Процесс продолжается до тех пор, пока right не окажется слева от left.
Тем самым будет определено правильное место разрешающего элемента.
Осуществляется перестановка разрешающего элемента с элементом, на который указывает right.
Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.
Реализация алгоритма быстрой сортировки на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdlib.h>
#define SIZE 20
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers[left];
while (left < right) // пока границы не сомкнутся
{
while ((numbers[right] >= pivot) && (left < right))
right--; // сдвигаем правую границу пока элемент [right] больше [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
left++; // сдвигаем левую границу вправо
}
while ((numbers[left] <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
right--; // сдвигаем правую границу влево
}
}
numbers[left] = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
}
int main()
{
int a[SIZE];
// Заполнение массива случайными числами
for (int i = 0; i<SIZE; i++)
a[i] = rand() % 201 - 100;
// Вывод элементов массива до сортировки
for (int i = 0; i<SIZE; i++)
printf("%4d ", a[i]);
printf("\n");
quickSort(a, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i<SIZE; i++)
printf("%4d ", a[i]);
printf("\n");
getchar();
return 0;
}
Результат выполнения
Еще по теме:
Назад: Алгоритмы сортировки и поиска
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
auto qsort(std::vector<int> A)
{
if(A.empty())
return A;
std::vector<int> p, mn, mx;
p.push_back(A[A.size()-1]);
A.pop_back();
for(int i=0; i<A.size(); i++)
if(A[i]<p[0])
mn.push_back(A[i]);
else
mx.push_back(A[i]);
std::vector<int>A1,A2;
A1=qsort(mn);
A2=qsort(mx);
A1.insert(A1.end(),p.begin(),p.end());
A1.insert(A1.end(),A2.begin(),A2.end());
return A1;
}
int main()
{
std::vector<int> Am;
int am;
std::cin>>am;
for(int i = 0; i < am; i++)
Am.push_back(rand() % 20000);
Am=qsort(Am);
for(int i=0; i<am; i++)
std::cout<<Am[i]<<" ";
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdlib.h>
#define SIZE 20
void qsort (int* arr, int left, int right)
{
int i = left, j = right;
int temp, pivot = arr[ (left+right)/2 ];
while (i <= j)
{
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j)
{
if (arr[i] > arr[j])
{
temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
i++; j--;
}
};
if (left < j) qsort (arr, left, j);
if (i < right) qsort (arr, i, right);
}
//-------------------------------------------------------------------
int main()
{
int Arr[SIZE];
// Заполнение массива случайными числами
for (int i = 0; i<SIZE; i++) Arr[i] = rand()%100;
// Вывод элементов массива до сортировки
for (int i = 0; i<SIZE; i++) printf("%3d ", Arr[i]); printf("\n");
qsort(Arr, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i<SIZE; i++) printf("%3d ", Arr[i]); printf("\n");
getchar(); return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
int l = begin, r = end;
int v = nums[l+(r-l)/2];
while(l <= r)
{
while(nums[l] < v) l++;
while(nums[r] > v) r--;
if(l <= r)
{
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
l++, r--;
}
}
if(begin < r)
sort(nums, begin, r);
if(l < end)
sort(nums, l, end);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{
int l = begin, r = end;
int v = nums[l+(r-l)/2];
while(l <= r)
{
while((nums[l] < v)&&(l<end)) l++;
while((nums[r] > v)&&(r>begin)) r--;
if(l <= r)
{
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
if (l<end)
{
l++;
}
if (r>0)
{
r--;
}
}
}
if(begin < r)
sort(nums, begin, r);
if(l < end)
sort(nums, l, end);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
{
int i = lo;
int j = hi + 1;
while (true)
{
while (vector[++i] < vector[lo])
{
if (i == hi) break;
}
while (vector[--j] > vector[lo])
{
if (j == lo)
{
break;
}
}
if (i >= j)
{
break;
}
std::swap(vector[i], vector[j]);
}
std::swap(vector[lo], vector[j]);
return j;
}
void quickSort2(std::vector<int>& vector, int lo, int hi)
{
if (hi <= lo) return;
int j = partition2(vector, lo, hi);
quickSort2(vector, lo, j - 1);
quickSort2(vector, j + 1, hi);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
! qsort_reals.f90 --
!
! Example belonging to "Modern Fortran in Practice"
! by Arjen Markus
!
! This work is licensed under the
! Creative Commons Attribution 3.0 Unported License.
! To view a copy of this license,
! visit http://creativecommons.org/licenses/by/3.0/
! or send a letter to:
! Creative Commons, 444 Castro Street, Suite 900,
! Mountain View, California, 94041, USA.
!
! Compact implementation of the QuickSort algorithm
!
! Note:
! Because the function uses Fortran 90 features,
! its interface should be made
! explicit when using it in an actual program.
! This is easiest via a module.
!
module qsort_functions
implicit none
contains
recursive function qsort_reals( data ) result( sorted )
real, dimension(:), intent(in) :: data
real, dimension(1:size(data)) :: sorted
if ( size(data) > 1 ) then
sorted = &
(/ qsort_reals( pack( data(2:), data(2:) > data(1) ) ), &
data(1), &
qsort_reals( pack( data(2:), data(2:) <= data(1) ) ) /)
else
sorted = data
endif
end function qsort_reals
end module qsort_functions
2
3
4
5
6
7
8
9
10
11
12
if (array.length < 2)
return array;
const pivot = array.filter(e => e === array[0]);
const greater = array.filter(e => e < array[0]);
const less = array.filter(e => e > array[0]);
return [...quick_sort(less), ...pivot, ...quick_sort(greater)];
};