Last active
December 6, 2015 01:01
-
-
Save 1995eaton/c46825b680297e8294d1 to your computer and use it in GitHub Desktop.
Quicksort implementations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <random> | |
#include <vector> | |
namespace ArrayUtils { | |
std::vector<uint32_t> random_array(uint32_t low, uint32_t high, size_t count) { | |
std::vector<uint32_t> result(count); | |
std::mt19937 eng(std::random_device{}()); | |
std::uniform_int_distribution<uint32_t> gen(low, high); | |
for (size_t i = 0; i < count; i++) | |
result[i] = gen(eng); | |
return result; | |
} | |
template <typename T> bool is_sorted(const T& array) { | |
auto it = array.begin(); | |
auto end = array.end(); | |
if (it == end) return true; | |
auto last = it; | |
while (++it != end) { | |
if (*last > *it) | |
return false; | |
last = it; | |
} | |
return true; | |
} | |
} | |
template <typename T> class quicksort_impl { | |
private: | |
T begin, end; | |
void partition(T left, T right) { | |
auto mid = *(left + (std::distance(left, right) >> 1)); | |
T i = left, j = right; | |
while (i < j) { | |
while (*i < mid) ++i; | |
while (*j > mid) --j; | |
if (i <= j) { | |
auto temp = *i; | |
*i++ = *j; | |
*j-- = temp; | |
} | |
} | |
if (left < j) partition(left, j); | |
if (i < right) partition(i, right); | |
} | |
public: | |
quicksort_impl(T _begin, T _end) : begin(_begin), end(_end) {} | |
void operator()() { | |
if (std::distance(begin, end) <= 1) return; | |
partition(begin, end - 1); | |
} | |
}; | |
template <typename T> constexpr void quicksort(T begin, T end) { | |
quicksort_impl<T>(begin, end)(); | |
} | |
int main() { | |
auto array = ArrayUtils::random_array(0, 1000, 5000000); | |
quicksort(array.begin(), array.end()); | |
std::cout << ArrayUtils::is_sorted(array) << std::endl; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'use strict'; | |
class ArrayUtils { | |
static randomArray(low, high, count) { | |
let result = []; | |
for (let i = 0; i < count; i++) | |
result.push(Math.floor(Math.random() * (high - low) + low)); | |
return result; | |
} | |
static isSorted(array) { | |
for (let i = 1; i < array.length; i++) | |
if (array[i] < array[i - 1]) return false; | |
return true; | |
} | |
} | |
function quicksort(array) { | |
if (array.length <= 1) return; | |
(function partition(left, right) { | |
let mid = array[left + ((right - left) >> 1)]; | |
let i = left, j = right; | |
while (i < j) { | |
while (array[i] < mid) ++i; | |
while (array[j] > mid) --j; | |
if (i <= j) { | |
let temp = array[i]; | |
array[i++] = array[j]; | |
array[j--] = temp; | |
} | |
} | |
if (left < j) partition(left, j); | |
if (i < right) partition(i, right); | |
})(0, array.length - 1); | |
} | |
((low, high, count) => { | |
let array = ArrayUtils.randomArray(low, high, count); | |
quicksort(array); | |
console.log(ArrayUtils.isSorted(array)); | |
})(0, 1000, 5000000); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment