Files
addr2line
adler
aho_corasick
ansi_term
atty
backtrace
base64
bincode
bitflags
bitmaps
bstr
byteset
search
unicode
byteorder
bytes
buf
fmt
bytesize
cargo
core
compiler
resolver
source
ops
cargo_clean.rscargo_compile.rscargo_doc.rscargo_fetch.rscargo_generate_lockfile.rscargo_install.rscargo_new.rscargo_output_metadata.rscargo_package.rscargo_pkgid.rscargo_read_manifest.rscargo_run.rscargo_test.rscargo_uninstall.rscommon_for_install_and_uninstall.rsfix.rslockfile.rsmod.rsregistry.rsresolve.rsvendor.rs
sources
util
canonical_url.rscommand_prelude.rscpu.rsdependency_queue.rsdiagnostic_server.rserrors.rsflock.rsgraph.rshex.rsimportant_paths.rsinto_url.rsinto_url_with_base.rsjob.rslev_distance.rslockserver.rsmachine_message.rsmod.rsnetwork.rspaths.rsprocess_builder.rsprofile.rsprogress.rsread2.rsrustc.rssha256.rsto_semver.rsvcs.rsworkspace.rs
cargo_platform
cfg_if
chrono
format
naive
offset
sys
clap
app
args
completions
color_backtrace
corpus_database
corpus_database_dsl
generator
corpus_extractor
corpus_manager
queries
corpus_manager_driver
corpus_queries_derive
corpus_queries_impl
crates_index
crates_io
crc32fast
crossbeam_queue
crossbeam_utils
crypto_hash
csv
csv_core
curl
curl_sys
darling
darling_core
ast
codegen
error
options
usage
util
darling_macro
datafrog
datapond
datapond_derive
datapond_macro
either
encoding_rs
env_logger
filter
fmt
error_chain
failure
failure_derive
filetime
flate2
deflate
ffi
gz
zlib
fnv
foreign_types
foreign_types_shared
form_urlencoded
fs2
futures
future
sink
stream
and_then.rsbuffer_unordered.rsbuffered.rscatch_unwind.rschain.rschannel.rschunks.rscollect.rsconcat.rsempty.rsfilter.rsfilter_map.rsflatten.rsfold.rsfor_each.rsforward.rsfrom_err.rsfuse.rsfuture.rsfutures_ordered.rsfutures_unordered.rsinspect.rsinspect_err.rsiter.rsiter_ok.rsiter_result.rsmap.rsmap_err.rsmerge.rsmod.rsonce.rsor_else.rspeek.rspoll_fn.rsrepeat.rsselect.rsskip.rsskip_while.rssplit.rstake.rstake_while.rsthen.rsunfold.rswait.rszip.rs
sync
task_impl
unsync
futures_channel
futures_core
futures_io
futures_macro
futures_sink
futures_task
futures_util
async_await
future
future
try_future
io
lock
stream
futures_unordered
stream
buffer_unordered.rsbuffered.rscatch_unwind.rschain.rschunks.rscollect.rsconcat.rscycle.rsenumerate.rsfilter.rsfilter_map.rsflatten.rsfold.rsfor_each.rsfor_each_concurrent.rsfuse.rsinto_future.rsmap.rsmod.rsnext.rspeek.rsready_chunks.rsscan.rsselect_next_some.rsskip.rsskip_while.rstake.rstake_until.rstake_while.rsthen.rsunzip.rszip.rs
try_stream
task
getrandom
gimli
read
git2
blame.rsblob.rsbranch.rsbuf.rsbuild.rscall.rscert.rscherrypick.rscommit.rsconfig.rscred.rsdescribe.rsdiff.rserror.rsindex.rslib.rsmerge.rsmessage.rsnote.rsobject.rsodb.rsoid.rsoid_array.rspackbuilder.rspanic.rspatch.rspathspec.rsproxy_options.rsrebase.rsreference.rsreflog.rsrefspec.rsremote.rsremote_callbacks.rsrepo.rsrevspec.rsrevwalk.rssignature.rsstash.rsstatus.rsstring_array.rssubmodule.rstag.rstime.rstransport.rstree.rstreebuilder.rsutil.rs
git2_curl
glob
globset
h2
codec
frame
hpack
proto
hashbrown
heck
hex
home
http
http_body
httparse
httpdate
humantime
hyper
body
client
common
proto
service
hyper_tls
ident_case
idna
ignore
im_rc
hash
nodes
ord
vector
indexmap
iovec
ipnet
itertools
combinations.rscombinations_with_replacement.rsconcat_impl.rscons_tuples_impl.rsdiff.rseither_or_both.rsexactly_one_err.rsformat.rsfree.rsgroup_map.rsgroupbylazy.rsgrouping_map.rsimpl_macros.rsintersperse.rsk_smallest.rskmerge_impl.rslazy_buffer.rslib.rsmerge_join.rsminmax.rsmultipeek_impl.rspad_tail.rspeek_nth.rspeeking_take_while.rspermutations.rspowerset.rsprocess_results_impl.rsput_back_n_impl.rsrciter_impl.rsrepeatn.rssize_hint.rssources.rstee.rstuple_impl.rsunique_impl.rswith_position.rszip_eq_impl.rszip_longest.rsziptuple.rs
itoa
jobserver
lazy_static
lazycell
libc
unix
libgit2_sys
libnghttp2_sys
libssh2_sys
libz_sys
lock_api
log
log_derive
matches
maybe_uninit
memchr
mime
miniz_oxide
mio
event
net
sys
mio_uds
native_tls
nix
net
sys
num_cpus
num_integer
num_traits
object
read
once_cell
opener
openssl
openssl_probe
openssl_sys
parking_lot
parking_lot_core
percent_encoding
pest
iterators
unicode
pin_project
pin_project_lite
pin_utils
ppv_lite86
print_stats
proc_macro2
proc_macro_error
proc_macro_error_attr
proc_macro_hack
proc_macro_nested
quick_error
quote
rand
distributions
weighted
rngs
seq
rand_chacha
rand_core
rand_xoshiro
common.rslib.rssplitmix64.rsxoroshiro128plus.rsxoroshiro128plusplus.rsxoroshiro128starstar.rsxoroshiro64star.rsxoroshiro64starstar.rsxoshiro128plus.rsxoshiro128plusplus.rsxoshiro128starstar.rsxoshiro256plus.rsxoshiro256plusplus.rsxoshiro256starstar.rsxoshiro512plus.rsxoshiro512plusplus.rsxoshiro512starstar.rs
regex
regex_automata
regex_syntax
ast
hir
unicode_tables
remove_dir_all
reqwest
async_impl
blocking
rustc
rustc_demangle
rustc_hash
rustc_workspace_hack
rustfix
rustwide
cmd
crates
native
tools
ryu
same_file
scopeguard
semver
semver_parser
serde
de
private
ser
serde_derive
serde_ignored
serde_json
serde_urlencoded
shell_escape
signal_hook_registry
simplelog
sized_chunks
inline_array
ring_buffer
sized_chunk
sparse_chunk
slab
smallvec
socket2
strip_ansi_escapes
strsim
structopt
structopt_derive
syn
attr.rsawait.rsbigint.rsbuffer.rscustom_keyword.rscustom_punctuation.rsdata.rsderive.rsdiscouraged.rserror.rsexport.rsexpr.rsext.rsfile.rsgenerics.rsgroup.rsident.rsitem.rslib.rslifetime.rslit.rslookahead.rsmac.rsmacros.rsop.rsparse.rsparse_macro_input.rsparse_quote.rspat.rspath.rsprint.rspunctuated.rsreserved.rssealed.rsspan.rsspanned.rsstmt.rsthread.rstoken.rstt.rsty.rsverbatim.rswhitespace.rs
synstructure
tar
tempdir
tempfile
termcolor
textwrap
thiserror
thiserror_impl
thread_local
time
tinyvec
tinyvec_macros
tokio
future
io
driver
util
async_buf_read_ext.rsasync_read_ext.rsasync_seek_ext.rsasync_write_ext.rsbuf_reader.rsbuf_stream.rsbuf_writer.rschain.rscopy.rscopy_bidirectional.rscopy_buf.rsempty.rsflush.rslines.rsmem.rsmod.rsread.rsread_buf.rsread_exact.rsread_int.rsread_line.rsread_to_end.rsread_to_string.rsread_until.rsrepeat.rsshutdown.rssink.rssplit.rstake.rsvec_with_initialized.rswrite.rswrite_all.rswrite_buf.rswrite_int.rswrite_vectored.rs
loom
std
macros
net
tcp
unix
park
runtime
blocking
task
thread_pool
sync
mpsc
rwlock
task
task
time
util
tokio_executor
tokio_io
_tokio_codec
codec
io
tokio_native_tls
tokio_process
tokio_reactor
tokio_signal
tokio_stream
stream_ext
wrappers
tokio_sync
tokio_util
codec
sync
toml
tower_service
tracing
tracing_core
tracing_futures
try_lock
typenum
ucd_trie
unicode_bidi
unicode_normalization
unicode_segmentation
unicode_width
unicode_xid
url
utf8parse
vec_map
vte
walkdir
want
xattr
>
1 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
// This Source Code Form is subject to the terms of the Mozilla Public // License, v. 2.0. If a copy of the MPL was not distributed with this // file, You can obtain one at http://mozilla.org/MPL/2.0/. use crate::vector::FocusMut; use rand_core::{RngCore, SeedableRng}; use std::cmp::Ordering; fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize { let range = max - min; min + (rng.next_u64() as usize % range) } // Ported from the Java version at: // http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf // Should be O(n) to O(n log n) fn do_quicksort<A, F, R>( vector: &mut FocusMut<'_, A>, left: usize, right: usize, cmp: &F, rng: &mut R, ) where A: Clone, F: Fn(&A, &A) -> Ordering, R: RngCore, { if right <= left { return; } let l = left as isize; let r = right as isize; let p = gen_range(rng, left, right + 1) as isize; let mut l1 = l; let mut r1 = r; let mut l2 = l - 1; let mut r2 = r; vector.swap(r as usize, p as usize); loop { while l1 != r && vector.pair(l1 as usize, r as usize, |a, b| cmp(a, b)) == Ordering::Less { l1 += 1; } r1 -= 1; while r1 != r && vector.pair(r as usize, r1 as usize, |a, b| cmp(a, b)) == Ordering::Less { if r1 == l { break; } r1 -= 1; } if l1 >= r1 { break; } vector.swap(l1 as usize, r1 as usize); if l1 != r && vector.pair(l1 as usize, r as usize, |a, b| cmp(a, b)) == Ordering::Equal { l2 += 1; vector.swap(l2 as usize, l1 as usize); } if r1 != r && vector.pair(r as usize, r1 as usize, |a, b| cmp(a, b)) == Ordering::Equal { r2 -= 1; vector.swap(r1 as usize, r2 as usize); } } vector.swap(l1 as usize, r as usize); r1 = l1 - 1; l1 += 1; let mut k = l; while k < l2 { vector.swap(k as usize, r1 as usize); r1 -= 1; k += 1; } k = r - 1; while k > r2 { vector.swap(l1 as usize, k as usize); k -= 1; l1 += 1; } if r1 >= 0 { do_quicksort(vector, left, r1 as usize, cmp, rng); } do_quicksort(vector, l1 as usize, right, cmp, rng); } pub(crate) fn quicksort<A, F>(vector: &mut FocusMut<'_, A>, left: usize, right: usize, cmp: &F) where A: Clone, F: Fn(&A, &A) -> Ordering, { let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0); do_quicksort(vector, left, right, cmp, &mut rng); } #[cfg(test)] mod test { use super::*; use crate::test::is_sorted; use crate::vector::proptest::vector; use ::proptest::num::i32; use ::proptest::proptest; proptest! { #[test] fn test_quicksort(ref input in vector(i32::ANY, 0..1000)) { let mut vec = input.clone(); let len = vec.len(); if len > 1 { quicksort(&mut vec.focus_mut(), 0, len - 1, &Ord::cmp); } assert!(is_sorted(vec)); } } }