diff options
author | Jed Barber <jjbarber@y7mail.com> | 2015-10-17 14:20:48 +1100 |
---|---|---|
committer | Jed Barber <jjbarber@y7mail.com> | 2015-10-17 14:20:48 +1100 |
commit | 63c3043200de6b28a8c192f1b5625940435ea55e (patch) | |
tree | ab761edbbc71b2b2f28e0ef7e10b8adc58d44320 /sort/quick.adb | |
parent | 5933f248c18914fbbce03102b340361a575eae3c (diff) |
Organised source code a bit, added makefile with clean target
Diffstat (limited to 'sort/quick.adb')
-rw-r--r-- | sort/quick.adb | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/sort/quick.adb b/sort/quick.adb new file mode 100644 index 0000000..4586b3b --- /dev/null +++ b/sort/quick.adb @@ -0,0 +1,49 @@ + + +package body Quick is + + + procedure Swap(A, B : in out Element_T) is + Temp : Element_T; + begin + Temp := A; + A := B; + B := Temp; + end Swap; + + + procedure In_Place(Arr : in out Array_T) is + Pivot, Left, Right : Index_T; + begin + if Arr'Length <= 1 then + return; + end if; + + Pivot := Arr'First; + Left := Index_T'Succ(Pivot); + Right := Arr'Last; + + loop + while not (Arr(Left) > Arr(Pivot)) and Left < Arr'Last loop + Left := Index_T'Succ(Left); + end loop; + while Arr(Right) > Arr(Pivot) and Right > Arr'First loop + Right := Index_T'Pred(Right); + end loop; + exit when Left >= Right; + Swap(Arr(Left), Arr(Right)); + end loop; + + Swap(Arr(Pivot), Arr(Right)); + + if Right > Arr'First then + In_Place( Arr(Arr'First .. Index_T'Pred(Right)) ); + end if; + if Right < Arr'Last then + In_Place( Arr(Index_T'Succ(Right) .. Arr'Last) ); + end if; + end In_Place; + + +end Quick; + |