Sorting algorithms/Merge sort: Difference between revisions
m
→{{header|Standard ML}}: minor reformat of SML and extra example
m (→{{header|Component Pascal}}: Remove superfluous comments) |
m (→{{header|Standard ML}}: minor reformat of SML and extra example) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 2,877:
The merge sort algorithm is often the best choice for sorting a linked list.
The `Sort` procedure reduces the number of traversals
This optimization leads to a more efficient sorting process, making it faster, especially for large input lists.
Two modules are provided - for implementing and for using the merge sort .
<syntaxhighlight lang="oberon2">
MODULE RosettaMergeSort;
TYPE Template* = ABSTRACT RECORD END;
Line 2,895 ⟶ 2,890:
(* Abstract Procedures: *)
(* Return TRUE if list item`front` comes before list item `rear` in the sorted order, FALSE otherwise *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Template)
(* Return the next
PROCEDURE (IN t: Template)
(* Update the next pointer of list item `s` to the value of list `next` - Return the modified `s` *)
PROCEDURE (IN t: Template) Set- (s, next: ANYPTR): ANYPTR, NEW, ABSTRACT;
(* Merge sorted lists `front` and `rear` - Return the merged sorted list *)
Line 2,922 ⟶ 2,905:
IF front = NIL THEN RETURN rear END;
IF rear = NIL THEN RETURN front END;
IF t.
RETURN t.Set(front, t.Merge(t.
ELSE
RETURN t.Set(rear, t.Merge(front, t.
END
END Merge;
(* Sort the first `n` items in the list `s` and drop them from `s` *)
(* Return the sorted `n` items *)
PROCEDURE (IN t: Template) TakeSort (n: INTEGER; VAR s: ANYPTR): ANYPTR, NEW;
VAR k: INTEGER; front, rear: ANYPTR;
BEGIN
IF n = 1 THEN (* base case: if `n` is 1, return the head of `s` *)
front := s; s := t.Next(s); RETURN t.Set(front, NIL)
END;
(* Divide the first `n` items of `s` into two sorted parts *)
k := n DIV 2;
front := t.TakeSort(k, s);
rear := t.TakeSort(n - k, s);
RETURN t.Merge(front, rear) (* Return the merged parts *)
END TakeSort;
(* Perform a merge sort on `s` - Return the sorted list *)
PROCEDURE (IN t: Template) Sort* (s: ANYPTR): ANYPTR, NEW;
VAR n: INTEGER; r: ANYPTR;
BEGIN
IF s = NIL THEN RETURN
(*
WHILE r # NIL DO INC(n); r := t.Next(r) END;
RETURN t.TakeSort(n, s) (* Return the sorted list *)
END Sort;
Line 2,963 ⟶ 2,947:
Template = ABSTRACT RECORD
(IN t: Template) Before- (front, rear: ANYPTR): BOOLEAN, NEW, ABSTRACT;
(IN t: Template) Next- (s: ANYPTR): ANYPTR, NEW, ABSTRACT;
(IN t: Template) Set- (s, next: ANYPTR): ANYPTR, NEW, ABSTRACT;
Line 2,971 ⟶ 2,954:
END RosettaMergeSort.
</syntaxhighlight>
Use the merge sort implementation from `RosettaMergeSort` to sort a linked list of
<syntaxhighlight lang="oberon2">
MODULE RosettaMergeSortUse;
(* Import Modules: *)
IMPORT Sort := RosettaMergeSort, Out;
(* Type Definitions: *)
TYPE
(* a character list *)
List = POINTER TO RECORD
value:
next: List
END;
(* Implement the abstract record type Sort.Template *)
Asc = RECORD (Order) END;
Bad = RECORD (Order) END;
Desc = RECORD (Order) END;
(* Abstract Procedure Implementations: *)
(* Return the next node in the linked list *)
PROCEDURE (IN t:
BEGIN RETURN s(List).next END Next;
(* Set the next pointer of
PROCEDURE (IN t:
BEGIN
IF next = NIL THEN s(List).next := NIL
ELSE s(List).next :=
RETURN s
END Set;
(* Ignoring case, compare characters to determine ascending order in the sorted list *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Asc) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) <= CAP(rear(List).value)
END Before;
(* Unstable sort!!! *)
PROCEDURE (IN t: Bad) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) < CAP(rear(List).value)
END Before;
(* Ignoring case, compare characters to determine descending order in the sorted list *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Desc) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) >= CAP(rear(List).value)
END Before;
(* Helper Procedures: *)
(*
PROCEDURE
VAR
BEGIN
i := LEN(str$);
WHILE i # 0 DO
t := h; NEW(h);
DEC(i); h.value := str[i];
h.next := t
END;
RETURN h
END Explode;
(*
PROCEDURE Show (s: List);
VAR
BEGIN
Out.Char('"');
WHILE s # NIL DO Out.Char(s.value); s := s.next END;
Out.Char('"')
END Show;
(* Main Procedure: *)
PROCEDURE Use*;
VAR
BEGIN
s := Explode("A quick brown fox jumps over the lazy dog");
Out.String("Before:"); Out.Ln; Show(s); Out.Ln;
s := a.Sort(s)(List); (* Ascending stable sort *)
Out.String("After Asc:"); Out.Ln; Show(s); Out.Ln;
Out.String("After Bad:"); Out.Ln; Show(s); Out.Ln;
s := d.Sort(s)(List); (* Descending stable sort *)
Out.String("After Desc:"); Out.Ln; Show(s); Out.Ln
END Use;
END RosettaMergeSortUse.
</syntaxhighlight>
Execute: ^Q RosettaMergeSortUse.Use
{{out}}
<pre>
"A quick brown fox jumps over the lazy dog"
After Asc:
" Aabcdeefghijklmnoooopqrrstuuvwxyz"
After Bad:
" aAbcdeefghijklmnoooopqrrstuuvwxyz"
After Desc:
"zyxwvuutsrrqpoooonmlkjihgfeedcbaA "
</pre>
Line 4,606 ⟶ 4,591:
=={{header|Julia}}==
<syntaxhighlight lang="julia">function mergesort(arr::Vector)
if length(arr) ≤ 1 return arr end
Line 4,626 ⟶ 4,609:
end
if li ≤ length(lpart)
else
end
return rst
Line 6,933 ⟶ 6,916:
a
]</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
= ;
s.N = s.N;
e.X, <Split e.X>: (e.L) (e.R) = <Merge (<Sort e.L>) (<Sort e.R>)>;
};
Split {
(e.L) (e.R) = (e.L) (e.R);
(e.L) (e.R) s.X = (e.L s.X) (e.R);
(e.L) (e.R) s.X s.Y e.Z = <Split (e.L s.X) (e.R s.Y) e.Z>;
e.X = <Split () () e.X>;
};
Merge {
(e.L) () = e.L;
() (e.R) = e.R;
(s.X e.L) (s.Y e.R), <Compare s.X s.Y>: {
'-' = s.X <Merge (e.L) (s.Y e.R)>;
s.Z = s.Y <Merge (s.X e.L) (e.R)>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|REXX}}==
Line 7,400 ⟶ 7,415:
| merge cmp (xs, []) = xs
| merge cmp (xs as x::xs', ys as y::ys') =
case cmp (x, y) of
| _ => x :: merge cmp (xs', ys)
fun merge_sort cmp [] = []
| merge_sort cmp [x] = [x]
Line 7,410 ⟶ 7,426:
in
merge cmp (merge_sort cmp ys, merge_sort cmp zs)
end</syntaxhighlight>
{{out|Poly/ML}}
<pre>
> merge_sort Int.compare [8,6,4,2,1,3,5,7,9];
val it = [1, 2, 3, 4, 5, 6, 7, 8, 9]: int list
> merge_sort String.compare ["Plum", "Pear", "Peach", "Each"];
val it = ["Each", "Peach", "Pear", "Plum"]: string list
>
</syntaxhighlight>
=={{header|Swift}}==
Line 7,474 ⟶ 7,496:
templates merge
@: $(2);
[ $(1)... ->
when
|
otherwise
^@(1)
end merge
$ -> #
Line 7,701 ⟶ 7,722:
=={{header|Wren}}==
<syntaxhighlight lang="
var result = []
while (left.count > 0 && right.count > 0) {
Line 7,733 ⟶ 7,754:
}
var
for (a in
System.print("Before: %(a)")
a = mergeSort.call(a)
Line 7,752 ⟶ 7,773:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
for (a in
System.print("Before: %(a)")
a = Sort.merge(a)
|