Commits

Yujie Wu committed 0c79e04 Merge

flow: Merged <feature> 'sort' to <develop> ('develop').

Comments (0)

Files changed (1)

+/******************************************************************************************************************************
+ * Several basic sorting algorithms
+ *
+ * Copyright (c) 2012  Yujie Wu
+ *
+ * Distributed under the MIT License
+ * (See accompanying file LICENSE or copy at http://www.opensource.org/licenses/mit-license.php)
+ */
+
+
+
+% Insert sort
+% Returns a list in the ascending order.
+fast_insert( E, [],            [E]              ).
+fast_insert( E, [Elem | Tail], [E, Elem | Tail] ) :- E =< Elem.
+fast_insert( E, [Elem | Tail], [   Elem | T   ] ) :- E > Elem, fast_insert( E, Tail, T ).
+
+insert_sort( [],            []            ).
+insert_sort( [Elem],        [Elem]        ).
+insert_sort( [Elem | Tail], [Elem, E | T] ) :- insert_sort( Tail, [E | T] ), Elem =< E.
+insert_sort( [Elem | Tail], [E       | T] ) :- insert_sort( Tail, [E | S] ), Elem  > E, fast_insert( Elem, S, T ).
+
+% Another (much slower) way to implement:
+% insert_sort( [Elem | Tail], [E       | T] ) :- insert_sort( Tail, [E | S] ), Elem  > E, insert_sort( [Elem | S], T ).
+
+
+
+% Bubble sort
+% Returns a list in the ascending order.
+bubble_swap( Elem, [],           [Elem]             ).
+bubble_swap( Elem, [E | Sorted], [Elem, E | Sorted] ) :- Elem =< E.
+bubble_swap( Elem, [E | Sorted], [      E | T     ] ) :- Elem  > E, bubble_swap( Elem, Sorted, T ).
+
+bubble_sort( [Elem],        [Elem] ).
+bubble_sort( [Elem | Tail], Result ) :- bubble_sort( Tail, T ), bubble_swap( Elem, T, Result ).
+
+
+
+% Merge sort
+% Returns a list in the ascending order.
+divide_impl( 0, List,          [],         List  ).
+divide_impl( N, [Elem | Tail], [Elem | T], Right ) :- M is dec( N ), divide_impl( M, Tail, T, Right ).
+
+divide( List, Left, Right ) :- length( List, N ), M is N // 2, divide_impl( M, List, Left, Right ).
+
+merge( List,     [],       List         ).
+merge( [],       List,     List         ).
+merge( [L | TL], [R | TR], [R | Merged] ) :- L  > R, merge( [L | TL],      TR,  Merged ).
+merge( [L | TL], [R | TR], [L | Merged] ) :- L =< R, merge( TL,       [R | TR], Merged ).
+
+merge_sort( [Elem], [Elem] ).
+merge_sort( List,   Result ) :-
+   length( List, N ),
+   N > 1,
+   divide( List, Left, Right ),
+   merge_sort( Left,  RL ),
+   merge_sort( Right, RR ),
+   merge( RL, RR, Result ).
+
+
+
+% Quick sort
+% Returns a list in the ascending order.
+
+% Trivial pivot selection algorithm: Select the first element as the pivot.
+pivot( [Elem | Tail], Elem, Tail ).
+
+partition( [],            _,     [],            []               ).
+partition( [Elem | Tail], Pivot, [Elem | Less],         Greater  ) :- Elem =< Pivot, partition( Tail, Pivot, Less, Greater ).
+partition( [Elem | Tail], Pivot,         Less,  [Elem | Greater] ) :- Elem  > Pivot, partition( Tail, Pivot, Less, Greater ).
+
+quick_sort( [],     []     ).
+quick_sort( [Elem], [Elem] ).
+quick_sort( List, Sorted ) :-
+   pivot( List, Pivot, Reduced ),
+   partition( Reduced, Pivot, Less, Greater ),
+   quick_sort( Less,    L ),
+   quick_sort( Greater, G ),
+   append( L, [Pivot | G], Sorted ).
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.