mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-09-24 20:10:13 +01:00
Richard Smith
b8814f6c80
Also add a default for `EqWith.NotEqual`. Switch advent examples to use these named constraints, and also go through all the other TODOs in the advent examples and fix the ones that are trivially fixable now.
45 lines
1.2 KiB
Plaintext
45 lines
1.2 KiB
Plaintext
// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
|
|
// Exceptions. See /LICENSE for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
|
|
library "sort";
|
|
|
|
fn Swap[T: Core.Copy & Core.Destroy](ref from: T, ref to: T) {
|
|
var tmp: T = from;
|
|
from = to;
|
|
to = tmp;
|
|
}
|
|
|
|
fn Partition
|
|
[T: Core.Copy & Core.Destroy & Core.Ordered, N: Core.IntLiteral]
|
|
(ref a: array(T, N), from_in: i32, to_in: i32) -> i32 {
|
|
var pivot_index: i32 = from_in;
|
|
let pivot: T = a[pivot_index];
|
|
var from: i32 = from_in + 1;
|
|
var to: i32 = to_in;
|
|
while (from < to) {
|
|
if (a[from] <= pivot) {
|
|
++from;
|
|
} else if (a[to - 1] > pivot) {
|
|
--to;
|
|
} else {
|
|
// Element at `from` is > pivot, and
|
|
// element at `to - 1` is <= pivot.
|
|
Swap(ref a[from], ref a[to - 1]);
|
|
++from;
|
|
--to;
|
|
}
|
|
}
|
|
Swap(ref a[pivot_index], ref a[from - 1]);
|
|
return from - 1;
|
|
}
|
|
|
|
fn Quicksort
|
|
[T: Core.Copy & Core.Destroy & Core.Ordered, N: Core.IntLiteral]
|
|
(ref a: array(T, N), from: i32, to: i32) {
|
|
if (from + 1 >= to) { return; }
|
|
var pivot: i32 = Partition(ref a, from, to);
|
|
Quicksort(ref a, from, pivot);
|
|
Quicksort(ref a, pivot + 1, to);
|
|
}
|