Common sorted list
From Rosetta Code
Common sorted list is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For other sorting algorithms, see Category: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
Given an integer array nums, the goal is create common sorted list with unique elements.
- 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]
Contents
Ada[edit]
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;
- Output:
[ 1 3 4 5 7 8 9 ]
APL[edit]
csl ← (⊂∘⍋⌷⊢)∪∘∊
- 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[edit]
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
- Output:
{1, 3, 4, 5, 7, 8, 9}
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):
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
- Output:
{1, 3, 4, 5, 7, 8, 9}
AutoHotkey[edit]
Common_sorted_list(nums){Examples:
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
}
nums := [[5,1,3,8,9,4,8,7], [3,5,9,8,4], [1,3,7,9]]
output := Common_sorted_list(nums)
return
- Output:
[1, 3, 4, 5, 6, 7, 9]
AWK[edit]
# 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)
}
- 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[edit]
#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;
}
- Output:
[1, 3, 4, 5, 7, 8, 9]
C++[edit]
#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;
}
- Output:
1 3 4 5 7 8 9
Excel[edit]
LAMBDA[edit]
Binding the name COMMONSORTED to the following lambda expression in the Name Manager of the Excel WorkBook:
(See LAMBDA: The ultimate Excel worksheet function)
COMMONSORTED
=LAMBDA(grid,
SORT(
UNIQUE(
CONCATCOLS(grid)
)
)
)
and also assuming the following generic bindings in the Name Manager for the WorkBook:
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))
)
)
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#[edit]
// 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->[email protected])|>List.distinct|>List.sort)
- Output:
[1; 3; 4; 5; 7; 8; 9]
Factor[edit]
Note: in older versions of Factor, union-all is called combine.
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
- 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[edit]
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))
}
- 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[edit]
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]
]
- Output:
[1,3,4,5,7,8,9]
J[edit]
csl =: /:[email protected][email protected];
- 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[edit]
(() => {
"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();
})();
- Output:
[1, 3, 4, 5, 7, 8, 9]
Julia[edit]
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"
Nim[edit]
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.
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]])
- Output:
@[1, 3, 4, 5, 7, 8, 9]
Perl[edit]
@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;
- Output:
1 3 4 5 7 8 9 ! 1 3 4 4.2 5 7 8 9 ? all integer is not
Phix[edit]
?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[edit]
'''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()
- Output:
[1, 3, 4, 5, 7, 8, 9]
Quackery[edit]
uniquewith is defined at Remove duplicate elements#Quackery.
' [ [ 5 1 3 8 9 4 8 7 ]
[ 3 5 9 8 4 ]
[ 1 3 7 9 ] ]
[] swap witheach [ witheach join ]
uniquewith > echo
- Output:
[ 1 3 4 5 7 8 9 ]
Raku[edit]
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>];
- 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[edit]
/*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; [email protected].j; @.[email protected].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.*/
- output when using the default inputs:
the list of sorted common elements in all sets: [1,3,4,5,7,8,9]
Ring[edit]
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
- Output:
common sorted list elements are: [1,3,4,5,7,8,9]
Wren[edit]
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))
- 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]
