Common sorted list
Given an integer array nums, the goal is create common sorted list with unique elements.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
- Example
nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]
output = [1,3,4,5,7,8,9]
11l
<lang 11l>F csl(nums)
Set[Int] r L(num) nums r.update(num) R sorted(Array(r))
print(csl([[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]]))</lang>
- Output:
[1, 3, 4, 5, 7, 8, 9]
Action!
<lang Action!>INCLUDE "D2:SORT.ACT" ;from the Action! Tool Kit
PROC PrintArray(BYTE ARRAY a BYTE len)
BYTE i
Print(" [") IF len>0 THEN FOR i=0 TO len-1 DO PrintB(a(i)) IF i<len-1 THEN Put(' ) FI OD FI PrintE("]")
RETURN
BYTE FUNC Contains(BYTE ARRAY a BYTE len,value)
BYTE i
IF len>0 THEN FOR i=0 TO len-1 DO IF a(i)=value THEN RETURN(1) FI OD FI
RETURN (0)
PROC CommonListElements(CARD ARRAY arrays
BYTE ARRAY lengths BYTE count BYTE ARRAY res BYTE POINTER resLen) BYTE ARRAY a BYTE i,j,len,value,cnt,maxcnt
resLen^=0 IF count=0 THEN RETURN ELSEIF count=1 THEN MoveBlock(res,a,len) RETURN FI
FOR i=0 TO count-1 DO a=arrays(i) len=lengths(i) IF len>0 THEN FOR j=0 TO len-1 DO value=a(j) IF Contains(res,resLen^,value)=0 THEN res(resLen^)=value resLen^==+1 FI OD FI OD SortB(res,resLen^,0)
RETURN
PROC Test(CARD ARRAY arrays BYTE ARRAY lengths BYTE count)
BYTE ARRAY res(100) BYTE len,i
CommonListElements(arrays,lengths,count,res,@len) PrintE("Input:") FOR i=0 TO count-1 DO PrintArray(arrays(i),lengths(i)) OD PrintE("Output:") PrintArray(res,len) PutE()
RETURN
PROC Main()
CARD ARRAY arrays(3) BYTE ARRAY lengths(3)=[8 5 4], a1(8)=[5 1 3 8 9 4 8 7], a2(5)=[3 5 9 8 4], a3(4)=[1 3 7 9], a4(8)=[5 1 1 1 9 9 8 7], a5(5)=[5 5 9 9 9], a6(4)=[1 7 7 9] BYTE len
Put(125) PutE() ;clear the screen arrays(0)=a1 arrays(1)=a2 arrays(2)=a3 Test(arrays,lengths,3)
arrays(0)=a4 arrays(1)=a5 arrays(2)=a6 Test(arrays,lengths,3)
lengths(0)=0 Test(arrays,lengths,3)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
Input: [5 1 3 8 9 4 8 7] [3 5 9 8 4] [1 3 7 9] Output: [1 3 4 5 7 8 9] Input: [5 1 1 1 9 9 8 7] [5 5 9 9 9] [1 7 7 9] Output: [1 5 7 8 9] Input: [] [5 5 9 9 9] [1 7 7 9] Output: [1 5 7 9]
Ada
<lang Ada>with Ada.Text_Io; with Ada.Containers.Vectors;
procedure Sorted is
package Integer_Vectors is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Integer); use Integer_Vectors;
package Vector_Sorting is new Integer_Vectors.Generic_Sorting; use Vector_Sorting;
procedure Unique (Vec : in out Vector) is Res : Vector; begin for E of Vec loop if Res.Is_Empty or else Res.Last_Element /= E then Res.Append (E); end if; end loop; Vec := Res; end Unique;
procedure Put (Vec : Vector) is use Ada.Text_Io; begin Put ("["); for E of Vec loop Put (E'Image); Put (" "); end loop; Put ("]"); New_Line; end Put;
A : constant Vector := 5 & 1 & 3 & 8 & 9 & 4 & 8 & 7; B : constant Vector := 3 & 5 & 9 & 8 & 4; C : constant Vector := 1 & 3 & 7 & 9; R : Vector := A & B & C;
begin
Sort (R); Unique (R); Put (R);
end Sorted;</lang>
- Output:
[ 1 3 4 5 7 8 9 ]
APL
<lang>csl ← (⊂∘⍋⌷⊢)∪∘∊</lang>
- Output:
csl (5 1 3 8 9 4 8 7)(3 5 9 8 4)(1 3 7 9) 1 3 4 5 7 8 9
AppleScript
<lang applescript>use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later use framework "Foundation"
local nums, output
set nums to current application's class "NSArray"'s arrayWithArray:({{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}}) set output to (nums's valueForKeyPath:("@distinctUnionOfArrays.self"))'s sortedArrayUsingSelector:("compare:") return output as list</lang>
- Output:
<lang applescript>{1, 3, 4, 5, 7, 8, 9}</lang>
Or, as a composition of slightly more commonly-used generic functions
(given that distinctUnionOfArrays is a relatively specialised function,
while concat/flatten and nub/distinct are more atomic, and more frequently reached for):
<lang applescript>use AppleScript version "2.4" use framework "Foundation"
COMMON SORTED ARRAY ------------------
on run
sort(nub(concat({¬ {5, 1, 3, 8, 9, 4, 8, 7}, ¬ {3, 5, 9, 8, 4}, ¬ {1, 3, 7, 9}})))
end run
GENERIC FUNCTIONS -------------------
-- concat :: a -> [a] on concat(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬ valueForKeyPath:"@unionOfArrays.self") as list
end concat
-- nub :: [a] -> [a]
on nub(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬ valueForKeyPath:"@distinctUnionOfObjects.self") as list
end nub
-- sort :: Ord a => [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬ sortedArrayUsingSelector:"compare:") as list
end sort</lang>
- Output:
{1, 3, 4, 5, 7, 8, 9}
AutoHotkey
<lang AutoHotkey>Common_sorted_list(nums){
elements := [], output := [] for i, num in nums for j, d in num elements[d] := true for val, bool in elements output.push(val) return output
}</lang> Examples:<lang AutoHotkey>nums := [[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]] output := Common_sorted_list(nums) return</lang>
- Output:
[1, 3, 4, 5, 6, 7, 9]
AWK
<lang AWK>
- syntax: GAWK -f COMMON_SORTED_LIST.AWK
BEGIN {
PROCINFO["sorted_in"] = "@ind_num_asc" nums = "[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]" printf("%s : ",nums) n = split(nums,arr1,"],?") - 1 for (i=1; i<=n; i++) { gsub(/[\[\]]/,"",arr1[i]) split(arr1[i],arr2,",") for (j in arr2) { arr3[arr2[j]]++ } } for (j in arr3) { printf("%s ",j) } printf("\n") exit(0)
} </lang>
- Output:
[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9] : 1 3 4 5 7 8 9
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
void fatal(const char* message) {
fprintf(stderr, "%s\n", message); exit(1);
}
void* xmalloc(size_t n) {
void* ptr = malloc(n); if (ptr == NULL) fatal("Out of memory"); return ptr;
}
int icompare(const void* p1, const void* p2) {
const int* ip1 = p1; const int* ip2 = p2; return (*ip1 < *ip2) ? -1 : ((*ip1 > *ip2) ? 1 : 0);
}
size_t unique(int* array, size_t len) {
size_t out_index = 0; int prev; for (size_t i = 0; i < len; ++i) { if (i == 0 || prev != array[i]) array[out_index++] = array[i]; prev = array[i]; } return out_index;
}
int* common_sorted_list(const int** arrays, const size_t* lengths, size_t count, size_t* size) {
size_t len = 0; for (size_t i = 0; i < count; ++i) len += lengths[i]; int* array = xmalloc(len * sizeof(int)); for (size_t i = 0, offset = 0; i < count; ++i) { memcpy(array + offset, arrays[i], lengths[i] * sizeof(int)); offset += lengths[i]; } qsort(array, len, sizeof(int), icompare); *size = unique(array, len); return array;
}
void print(const int* array, size_t len) {
printf("["); for (size_t i = 0; i < len; ++i) { if (i > 0) printf(", "); printf("%d", array[i]); } printf("]\n");
}
int main() {
const int a[] = {5, 1, 3, 8, 9, 4, 8, 7}; const int b[] = {3, 5, 9, 8, 4}; const int c[] = {1, 3, 7, 9}; size_t len = 0; const int* arrays[] = {a, b, c}; size_t lengths[] = {COUNTOF(a), COUNTOF(b), COUNTOF(c)}; int* sorted = common_sorted_list(arrays, lengths, COUNTOF(arrays), &len); print(sorted, len); free(sorted); return 0;
}</lang>
- Output:
[1, 3, 4, 5, 7, 8, 9]
C++
<lang cpp>#include <iostream>
- include <vector>
- include <set>
- include <algorithm>
template<typename T> std::vector<T> common_sorted_list(const std::vector<std::vector<T>>& ll) {
std::set<T> resultset; std::vector<T> result; for (auto& list : ll) for (auto& item : list) resultset.insert(item); for (auto& item : resultset) result.push_back(item); std::sort(result.begin(), result.end()); return result;
}
int main() {
std::vector<int> a = {5,1,3,8,9,4,8,7}; std::vector<int> b = {3,5,9,8,4}; std::vector<int> c = {1,3,7,9}; std::vector<std::vector<int>> nums = {a, b, c}; auto csl = common_sorted_list(nums); for (auto n : csl) std::cout << n << " "; std::cout << std::endl; return 0;
}</lang>
- Output:
1 3 4 5 7 8 9
Excel
LAMBDA
Binding the name COMMONSORTED to the following lambda expression in the Name Manager of the Excel WorkBook:
(See LAMBDA: The ultimate Excel worksheet function)
<lang lisp>COMMONSORTED =LAMBDA(grid,
SORT( UNIQUE( CONCATCOLS(grid) ) )
)</lang>
and also assuming the following generic bindings in the Name Manager for the WorkBook:
<lang lisp>CONCATCOLS =LAMBDA(cols,
LET( nRows, ROWS(cols), ixs, SEQUENCE( COLUMNS(cols) * nRows, 1, 1, 1 ),
FILTERP( LAMBDA(x, 0 < LEN("" & x)) )( INDEX(cols, LET( r, MOD(ixs, nRows),
IF(0 = r, nRows, r) ), 1 + QUOTIENT(ixs - 1, nRows) ) ) )
)
FILTERP
=LAMBDA(p,
LAMBDA(xs, FILTER(xs, p(xs)) )
)</lang>
The formula in cell B2 defines a dynamic array of values, additionally populating further cells in column B.
- Output:
fx | =COMMONSORTED(C2:E9) | |||||
---|---|---|---|---|---|---|
A | B | C | D | E | ||
1 | Common sorted | |||||
2 | 1 | 5 | 3 | 1 | ||
3 | 3 | 1 | 5 | 3 | ||
4 | 4 | 3 | 9 | 7 | ||
5 | 5 | 8 | 8 | 9 | ||
6 | 7 | 9 | 4 | |||
7 | 8 | 4 | ||||
8 | 9 | 8 | ||||
9 | 7 |
F#
<lang fsharp> // Common sorted list. Nigel Galloway: February 25th., 2021 let nums=[|[5;1;3;8;9;4;8;7];[3;5;9;8;4];[1;3;7;9]|] printfn "%A" (nums|>Array.reduce(fun n g->n@g)|>List.distinct|>List.sort) </lang>
- Output:
[1; 3; 4; 5; 7; 8; 9]
Factor
Note: in older versions of Factor, union-all
is called combine
.
<lang factor>USING: formatting kernel sets sorting ;
{ { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } } dup union-all natural-sort "Sorted union of %u is:\n%u\n" printf</lang>
- Output:
Sorted union of { { 5 1 3 8 9 4 8 7 } { 3 5 9 8 4 } { 1 3 7 9 } } is: { 1 3 4 5 7 8 9 }
Go
<lang go>package main
import (
"fmt" "sort"
)
func distinctSortedUnion(ll [][]int) []int {
var res []int for _, l := range ll { res = append(res, l...) } set := make(map[int]bool) for _, e := range res { set[e] = true } res = res[:0] for key := range set { res = append(res, key) } sort.Ints(res) return res
}
func main() {
ll := [][]int{{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}} fmt.Println("Distinct sorted union of", ll, "is:") fmt.Println(distinctSortedUnion(ll))
}</lang>
- Output:
Distinct sorted union of [[5 1 3 8 9 4 8 7] [3 5 9 8 4] [1 3 7 9]] is: [1 3 4 5 7 8 9]
Haskell
<lang haskell>import Data.List (nub, sort)
COMMON SORTED LIST ------------------
commonSorted :: Ord a => a -> [a] commonSorted = sort . nub . concat
TEST -------------------------
main :: IO () main =
print $ commonSorted [ [5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9] ]</lang>
- Output:
[1,3,4,5,7,8,9]
J
<lang j>csl =: /:~@~.@;</lang>
- Output:
nums =: 5 1 3 8 9 4 8 7;3 5 9 8 4;1 3 7 9 csl nums 1 3 4 5 7 8 9
JavaScript
<lang javascript>(() => {
"use strict";
// --------------- COMMON SORTED LIST ----------------
// commonSorted :: Ord a => a -> [a] const commonSorted = xs => sort(nub(concat(xs)));
// ---------------------- TEST ----------------------- const main = () => commonSorted([ [5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9] ]);
// --------------------- GENERIC ---------------------
// concat :: a -> [a] const concat = xs => [].concat(...xs);
// nub :: [a] -> [a] const nub = xs => [...new Set(xs)];
// sort :: Ord a => [a] -> [a] const sort = xs => // An (ascending) sorted copy of xs. xs.slice().sort();
return main();
})();</lang>
- Output:
[1, 3, 4, 5, 7, 8, 9]
jq
Works with gojq, the Go implementation of jq
Assuming the input is a single array of arrays, we can simply chain the `add` and `unique` filters: <lang jq>jq -nc '[[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]] | add | unique'</lang>
- Output:
[1,3,4,5,7,8,9]
If the arrays are presented individually in an external stream, we could use the `-s` command-line option.
Alternatively, here's a stream-oriented version of `add` that could be used: <lang jq>def add(s): reduce s as $x (null; . + $x);</lang> For example: <lang jq>jq -nc '
def add(s): reduce s as $x (null; . + $x); add(inputs) | unique' <<< '[5,1,3,8,9,4,8,7] [3,5,9,8,4] [1,3,7,9]'</lang>
Julia
<lang julia> julia> sort(union([5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9])) 7-element Array{Int64,1}:
1 3 4 5 7 8 9
julia> sort(union([2, 3, 4], split("3.14 is not an integer", r"\s+")), lt=(x, y) -> "$x" < "$y") 8-element Array{Any,1}:
2 3 "3.14" 4 "an" "integer" "is" "not"
</lang>
Mathematica/Wolfram Language
<lang Mathematica>Union[{5, 1, 3, 8, 9, 4, 8, 7}, {3, 5, 9, 8, 4}, {1, 3, 7, 9}]</lang>
- Output:
{1, 3, 4, 5, 7, 8, 9}
Nim
We could use a HashSet
or an IntSet
to deduplicate. We have rather chosen to use the procedure deduplicate
from module sequtils
applied to the sorted list.
<lang Nim>import algorithm, sequtils
proc commonSortedList(list: openArray[seq[int]]): seq[int] =
sorted(concat(list)).deduplicate(true)
echo commonSortedList([@[5,1,3,8,9,4,8,7], @[3,5,9,8,4], @[1,3,7,9]])</lang>
- Output:
@[1, 3, 4, 5, 7, 8, 9]
Perl
<lang perl>@c{@$_}++ for [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]; print join ' ', sort keys %c; @c{@$_}++ for [qw<not all is integer ? is not ! 4.2>]; print join ' ', sort keys %c;</lang>
- Output:
1 3 4 5 7 8 9 ! 1 3 4 4.2 5 7 8 9 ? all integer is not
Phix
?unique(join({{5,1,3,8,9,4,8,7}, {3,5,9,8,4}, {1,3,7,9}, split("not everything is an integer")},{}))
Note the join(x,{}): the 2nd param is needed to prevent it putting 32 (ie the acsii code for a space) in the output.
- Output:
(Unexpectedly rather Yoda-esque)
{1,3,4,5,7,8,9,"an","everything","integer","is","not"}
Python
<lang python>Common sorted list
from itertools import chain
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Sorted union of lists
print( sorted(nub(concat([ [5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9] ]))) )
- ----------------------- GENERIC ------------------------
- concat :: a -> [a]
- concat :: [String] -> String
def concat(xs):
The concatenation of all the elements in a list. return list(chain(*xs))
- nub :: [a] -> [a]
def nub(xs):
A list containing the same elements as xs, without duplicates, in the order of their first occurrence. return list(dict.fromkeys(xs))
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
[1, 3, 4, 5, 7, 8, 9]
Quackery
uniquewith
is defined at Remove duplicate elements#Quackery.
<lang Quackery> ' [ [ 5 1 3 8 9 4 8 7 ]
[ 3 5 9 8 4 ] [ 1 3 7 9 ] ] [] swap witheach [ witheach join ] uniquewith > echo</lang>
- Output:
[ 1 3 4 5 7 8 9 ]
Raku
<lang perl6>put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]; put sort keys [∪] [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9], [<not everything is an integer so why not avoid special cases # ~ 23 4.2>];</lang>
- Output:
1 3 4 5 7 8 9 # 1 3 4 4.2 5 7 8 9 23 an avoid cases everything integer is not so special why ~
REXX
<lang rexx>/*REXX pgm creates and displays a common sorted list of a specified collection of sets*/ parse arg a /*obtain optional arguments from the CL*/ if a= | a="," then a= '[5,1,3,8,9,4,8,7] [3,5,9,8,4] [1,3,7,9]' /*default sets.*/ x= translate(a, ,'],[') /*extract elements from collection sets*/ se= words(x)
- = 0; $= /*#: number of unique elements; $: list*/
$= /*the list of common elements (so far).*/
do j=1 for se; _= word(x, j) /*traipse through all elements in sets.*/ if wordpos(_, $)>0 then iterate /*Is element in the new list? Yes, skip*/ $= $ _; #= # + 1; @.#= _ /*add to list; bump counter; assign──►@*/ end /*j*/
$= call eSort # /*use any short (small) exchange sort.*/
do k=1 for #; $= $ @.k /*rebuild the $ list, it's been sorted.*/ end /*k*/
say 'the list of sorted common elements in all sets: ' "["translate(space($), ',', " ")']' exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ eSort: procedure expose @.; arg h 1 z; do while h>1; h= h%2; do i=1 for z-h; j= i; k= h+i
do while @.k<@.j; t=@.j; @.j=@.k; @.k=t; if h>=j then leave; j=j-h; k=k-h; end;end end; return /*this sort was used 'cause of brevity.*/</lang>
- output when using the default inputs:
the list of sorted common elements in all sets: [1,3,4,5,7,8,9]
Ring
<lang ring> nums = [[5,1,3,8,9,4,8,7],[3,5,9,8,4],[1,3,7,9]] sumNums = []
for n = 1 to len(nums)
for m = 1 to len(nums[n]) add(sumNums,nums[n][m]) next
next
sumNums = sort(sumNums) for n = len(sumNums) to 2 step -1
if sumNums[n] = sumNums[n-1] del(sumNums,n) ok
next
sumNums = sort(sumNums)
see "common sorted list elements are: " showArray(sumNums)
func showArray(array)
txt = "" see "[" for n = 1 to len(array) txt = txt + array[n] + "," next txt = left(txt,len(txt)-1) txt = txt + "]" see txt
</lang>
- Output:
common sorted list elements are: [1,3,4,5,7,8,9]
Ruby
<lang ruby>nums = [5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9] p nums.inject(:+).sort.uniq </lang>
- Output:
[1, 3, 4, 5, 7, 8, 9]
Wren
<lang ecmascript>import "/seq" for Lst import "/sort" for Sort
var distinctSortedUnion = Fn.new { |ll|
var res = ll.reduce([]) { |acc, l| acc + l } res = Lst.distinct(res) Sort.insertion(res) return res
}
var ll = [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]] System.print("Distinct sorted union of %(ll) is:") System.print(distinctSortedUnion.call(ll))</lang>
- Output:
Distinct sorted union of [[5, 1, 3, 8, 9, 4, 8, 7], [3, 5, 9, 8, 4], [1, 3, 7, 9]] is: [1, 3, 4, 5, 7, 8, 9]