AceSorting  0.1.0
Sorting algorithms for Arduino (Bubble Sort, Insertion Sort, Shell Sort, Comb Sort, Quick Sort)
quickSort.h
Go to the documentation of this file.
1 /*
2 MIT License
3 
4 Copyright (c) 2021 Brian T. Park
5 
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12 
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15 
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24 
31 #ifndef ACE_SORTING_QUICK_SORT_H
32 #define ACE_SORTING_QUICK_SORT_H
33 
34 #include "swap.h"
35 
36 namespace ace_sorting {
37 
47 template <typename T>
48 void quickSortMiddle(T data[], uint16_t n) {
49  if (n <= 1) return;
50 
51  T pivot = data[n / 2];
52  T* left = data;
53  T* right = data + n - 1;
54 
55  while (left <= right) {
56  if (*left < pivot) {
57  left++;
58  } else if (*right > pivot) {
59  right--;
60  } else {
61  swap(*left, *right);
62  left++;
63  right--;
64  }
65  }
66 
67  quickSortMiddle(data, right - data + 1);
68  quickSortMiddle(left, data + n - left);
69 }
70 
80 template <typename T>
81 void quickSortMedian(T data[], uint16_t n) {
82  if (n <= 1) return;
83 
84  // Select the median of data[low], data[mid], and data[high] as the estimate
85  // of the ideal pivot. Don't swap (low, mid) or (mid, high) (compare that
86  // quickSortMedianSwapped()) to save flash memory. They will get swapped in
87  // the partitioning while-loop below.
88  uint16_t mid = n / 2;
89  T pivot = data[mid];
90  if (data[0] > data[n - 1]) {
91  swap(data[0], data[n - 1]);
92  }
93  if (data[0] > pivot) {
94  pivot = data[0];
95  } else if (pivot > data[n - 1]) {
96  pivot = data[n - 1];
97  }
98 
99  T* left = data;
100  T* right = data + n - 1;
101 
102  while (left <= right) {
103  if (*left < pivot) {
104  left++;
105  } else if (*right > pivot) {
106  right--;
107  } else {
108  swap(*left, *right);
109  left++;
110  right--;
111  }
112  }
113 
114  quickSortMedian(data, right - data + 1);
115  quickSortMedian(left, data + n - left);
116 }
117 
127 template <typename T>
128 void quickSortMedianSwapped(T data[], uint16_t n) {
129  if (n <= 1) return;
130 
131  // Select the median of data[low], data[mid], and data[high] as the estimate
132  // of the ideal pivot. In the process, the (low, mid, high) become sorted.
133  uint16_t mid = n / 2;
134  T pivot = data[mid];
135  if (data[0] > data[n - 1]) {
136  swap(data[0], data[n - 1]);
137  }
138  if (data[0] > pivot) {
139  swap(data[0], data[mid]);
140  } else if (pivot > data[n - 1]) {
141  swap(data[mid], data[n - 1]);
142  }
143  pivot = data[mid];
144 
145  // We can skip the low and high because they are already sorted.
146  T* left = data + 1;
147  T* right = data + n - 2;
148 
149  while (left <= right) {
150  if (*left < pivot) {
151  left++;
152  } else if (*right > pivot) {
153  right--;
154  } else {
155  swap(*left, *right);
156  left++;
157  right--;
158  }
159  }
160 
161  quickSortMedianSwapped(data, right - data + 1);
162  quickSortMedianSwapped(left, data + n - left);
163 }
164 
165 }
166 
167 #endif
ace_sorting::quickSortMedianSwapped
void quickSortMedianSwapped(T data[], uint16_t n)
Same as quickSortMedian(), but swap the low and high so that low, mid, and high elements become sorte...
Definition: quickSort.h:128
swap.h
ace_sorting::swap
void swap(T &a, T &b)
Swap the parameters.
Definition: swap.h:41
ace_sorting::quickSortMiddle
void quickSortMiddle(T data[], uint16_t n)
Quick sort using Hoare's original partition where the pivot is the middle of the array.
Definition: quickSort.h:48
ace_sorting::quickSortMedian
void quickSortMedian(T data[], uint16_t n)
Quick sort using Sedgewick's recommendation of using the median of low, middle and high.
Definition: quickSort.h:81