jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * Copyright (c) 2022, Marc Luqué <marc.luque@outlook.com>
4 *
5 * SPDX-License-Identifier: BSD-2-Clause
6 */
7
8#pragma once
9
10#include <AK/InsertionSort.h>
11#include <AK/StdLibExtras.h>
12
13namespace AK {
14
15// This is a dual pivot quick sort. It is quite a bit faster than the single
16// pivot quick_sort below. The other quick_sort below should only be used when
17// you are stuck with simple iterators to a container and you don't have access
18// to the container itself.
19//
20// We use a cutoff to insertion sort for partitions of size 7 or smaller.
21// The idea is to avoid recursion for small partitions.
22// The value 7 here is a magic number. According to princeton's CS algorithm class
23// a value between 5 and 15 should work well in most situations:
24// https://algs4.cs.princeton.edu/23quicksort/
25
26static constexpr int INSERTION_SORT_CUTOFF = 7;
27
28template<typename Collection, typename LessThan>
29void dual_pivot_quick_sort(Collection& col, int start, int end, LessThan less_than)
30{
31 if ((end + 1) - start <= INSERTION_SORT_CUTOFF) {
32 AK::insertion_sort(col, start, end, less_than);
33 return;
34 }
35
36 while (start < end) {
37 int size = end - start + 1;
38 if (size > 3) {
39 int third = size / 3;
40 if (less_than(col[start + third], col[end - third])) {
41 swap(col[start + third], col[start]);
42 swap(col[end - third], col[end]);
43 } else {
44 swap(col[start + third], col[end]);
45 swap(col[end - third], col[start]);
46 }
47 } else {
48 if (!less_than(col[start], col[end])) {
49 swap(col[start], col[end]);
50 }
51 }
52
53 int j = start + 1;
54 int k = start + 1;
55 int g = end - 1;
56
57 auto&& left_pivot = col[start];
58 auto&& right_pivot = col[end];
59
60 while (k <= g) {
61 if (less_than(col[k], left_pivot)) {
62 swap(col[k], col[j]);
63 j++;
64 } else if (!less_than(col[k], right_pivot)) {
65 while (!less_than(col[g], right_pivot) && k < g) {
66 g--;
67 }
68 swap(col[k], col[g]);
69 g--;
70 if (less_than(col[k], left_pivot)) {
71 swap(col[k], col[j]);
72 j++;
73 }
74 }
75 k++;
76 }
77 j--;
78 g++;
79
80 swap(col[start], col[j]);
81 swap(col[end], col[g]);
82
83 int left_pointer = j;
84 int right_pointer = g;
85
86 int left_size = left_pointer - start;
87 int middle_size = right_pointer - (left_pointer + 1);
88 int right_size = (end + 1) - (right_pointer + 1);
89
90 if (left_size >= middle_size && left_size >= right_size) {
91 dual_pivot_quick_sort(col, left_pointer + 1, right_pointer - 1, less_than);
92 dual_pivot_quick_sort(col, right_pointer + 1, end, less_than);
93 end = left_pointer - 1;
94 } else if (middle_size >= right_size) {
95 dual_pivot_quick_sort(col, start, left_pointer - 1, less_than);
96 dual_pivot_quick_sort(col, right_pointer + 1, end, less_than);
97 start = left_pointer + 1;
98 end = right_pointer - 1;
99 } else {
100 dual_pivot_quick_sort(col, start, left_pointer - 1, less_than);
101 dual_pivot_quick_sort(col, left_pointer + 1, right_pointer - 1, less_than);
102 start = right_pointer + 1;
103 }
104 }
105}
106
107template<typename Iterator, typename LessThan>
108void single_pivot_quick_sort(Iterator start, Iterator end, LessThan less_than)
109{
110 for (;;) {
111 int size = end - start;
112 if (size <= 1)
113 return;
114
115 int pivot_point = size / 2;
116 if (pivot_point)
117 swap(*(start + pivot_point), *start);
118
119 auto&& pivot = *start;
120
121 int i = 1;
122 for (int j = 1; j < size; ++j) {
123 if (less_than(*(start + j), pivot)) {
124 swap(*(start + j), *(start + i));
125 ++i;
126 }
127 }
128
129 swap(*start, *(start + i - 1));
130 // Recur into the shorter part of the remaining data
131 // to ensure a stack depth of at most log(n).
132 if (i > size / 2) {
133 single_pivot_quick_sort(start + i, end, less_than);
134 end = start + i - 1;
135 } else {
136 single_pivot_quick_sort(start, start + i - 1, less_than);
137 start = start + i;
138 }
139 }
140}
141
142template<typename Iterator>
143void quick_sort(Iterator start, Iterator end)
144{
145 single_pivot_quick_sort(start, end, [](auto& a, auto& b) { return a < b; });
146}
147
148template<typename Iterator, typename LessThan>
149void quick_sort(Iterator start, Iterator end, LessThan less_than)
150{
151 single_pivot_quick_sort(start, end, move(less_than));
152}
153
154template<typename Collection, typename LessThan>
155void quick_sort(Collection& collection, LessThan less_than)
156{
157 dual_pivot_quick_sort(collection, 0, collection.size() - 1, move(less_than));
158}
159
160template<typename Collection>
161void quick_sort(Collection& collection)
162{
163 dual_pivot_quick_sort(collection, 0, collection.size() - 1,
164 [](auto& a, auto& b) { return a < b; });
165}
166
167}
168
169#if USING_AK_GLOBALLY
170using AK::quick_sort;
171#endif