Sort disjoint sublist: Difference between revisions
Add Nimrod |
|||
(141 intermediate revisions by 55 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task|Sorting Algorithms}} |
||
{{Sorting Algorithm}} |
|||
Given a list of values and a set of integer indices into that value list, the task is to sort the values at the given indices, but preserving the values at indices outside the set of those to be sorted. |
|||
[[Category:Sorting]] |
|||
Given a list of values and a set of integer indices into that value list, the task is to sort the values at the given indices, while preserving the values at indices outside the set of those to be sorted. |
|||
Make your example work with the following list of values and set of indices: |
Make your example work with the following list of values and set of indices: |
||
<code> |
|||
:: Values: <code>[7, <b>6</b>, 5, 4, 3, 2, <b>1</b>, <b>0</b>]</code> |
|||
indices: {6, 1, 7}</code> |
|||
:: Indices: <code>{6, 1, 7}</code> |
|||
Where the correct result would be: |
Where the correct result would be: |
||
<code>[7, <b>0</b>, 5, 4, 3, 2, <b>1</b>, <b>6</b>]</code>. |
|||
:: <code>[7, <b>0</b>, 5, 4, 3, 2, <b>1</b>, <b>6</b>]</code>. |
|||
Note that for one based, rather than the zero-based indexing above, use the <code>indices: {7, 2, 8}</code>. The indices are described as a set rather than a list but any collection-type of those indices without duplication may be used as long as the example is insensitive to the order of indices given. |
|||
In case of one-based indexing, rather than the zero-based indexing above, you would use the indices <code>{7, 2, 8}</code> instead. |
|||
The indices are described as a set rather than a list but any collection-type of those indices without duplication may be used as long as the example is insensitive to the order of indices given. |
|||
;Cf. |
|||
* [[Order disjoint list items]] |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F sort_disjoint_sublist(&data, indices) |
|||
V sindices = sorted(indices) |
|||
V values = sorted(sindices.map(i -> @data[i])) |
|||
L(index, value) zip(sindices, values) |
|||
data[index] = value |
|||
V d = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
V i = [6, 1, 7] |
|||
sort_disjoint_sublist(&d, i) |
|||
print(d)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[7, 0, 5, 4, 3, 2, 1, 6] |
|||
</pre> |
|||
=={{header|AArch64 Assembly}}== |
|||
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }} |
|||
<syntaxhighlight lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
|||
/* program sublistSort64.s */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly*/ |
|||
.include "../includeConstantesARM64.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessStart: .asciz "Program 64 bits start.\n" |
|||
sMessResult: .ascii "Value : " |
|||
sMessValeur: .fill 11, 1, ' ' // size => 11 |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
ArrayNumber: .quad 7, 6, 5, 4, 3, 2, 1, 0 |
|||
.equ NBELEMENTS, (. - ArrayNumber) / 8 |
|||
ArrayIndex: .quad 6,1,7 |
|||
.equ NBELEMINDEX, (. - ArrayIndex) / 8 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
ArrayExtract: .skip 8 * NBELEMINDEX |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: |
|||
ldr x0,qAdrszMessStart |
|||
bl affichageMess |
|||
ldr x4,qAdrArrayNumber // number array address |
|||
ldr x5,qAdrArrayIndex // index array address |
|||
ldr x6,qAdrArrayExtract // extract array address |
|||
mov x3,#0 // index |
|||
1: |
|||
ldr x0,[x5,x3,lsl #3] // load index |
|||
ldr x1,[x4,x0,lsl #3] // load value of index |
|||
str x1,[x6,x3,lsl #3] // store value in array extract |
|||
add x3,x3,#1 // increment index |
|||
cmp x3,#NBELEMINDEX // end array index ? |
|||
blt 1b // no -> loop |
|||
mov x0,x5 // index array address |
|||
mov x1,#0 // first element |
|||
mov x2,#NBELEMINDEX // array size |
|||
bl insertionSort |
|||
mov x0,x6 // extract array address |
|||
mov x1,#0 // first element |
|||
mov x2,#NBELEMINDEX // array size |
|||
bl insertionSort |
|||
mov x3,#0 // init index |
|||
2: |
|||
ldr x0,[x6,x3,lsl #3] // load value of array extract |
|||
ldr x1,[x5,x3,lsl #3] // load index |
|||
str x0,[x4,x1,lsl #3] // store value in number array in index place |
|||
add x3,x3,#1 // increment indice |
|||
cmp x3,#NBELEMINDEX |
|||
blt 2b |
|||
mov x0,x4 // number array address |
|||
bl displayArray |
|||
100: // standard end of the program |
|||
mov x0, #0 // return code |
|||
mov x8, #EXIT // request to exit program |
|||
svc #0 // perform the system call |
|||
qAdrsMessValeur: .quad sMessValeur |
|||
qAdrszMessStart: .quad szMessStart |
|||
qAdrszCarriageReturn: .quad szCarriageReturn |
|||
qAdrsMessResult: .quad sMessResult |
|||
qAdrArrayNumber: .quad ArrayNumber |
|||
qAdrArrayIndex: .quad ArrayIndex |
|||
qAdrArrayExtract: .quad ArrayExtract |
|||
/******************************************************************/ |
|||
/* insertion sort */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of table */ |
|||
/* x1 contains the first element */ |
|||
/* x2 contains the number of element */ |
|||
insertionSort: |
|||
stp x1,lr,[sp,-16]! // save registers |
|||
stp x2,x3,[sp,-16]! |
|||
stp x4,x5,[sp,-16]! |
|||
stp x6,x7,[sp,-16]! |
|||
add x3,x1,#1 // start index i |
|||
1: // start loop |
|||
ldr x4,[x0,x3,lsl #3] // load value A[i] |
|||
sub x5,x3,#1 // index j |
|||
2: |
|||
ldr x6,[x0,x5,lsl #3] // load value A[j] |
|||
cmp x6,x4 // compare value |
|||
ble 3f |
|||
add x5,x5,#1 // increment index j |
|||
str x6,[x0,x5,lsl #3] // store value A[j+1] |
|||
subs x5,x5,#2 // j = j - 1 |
|||
bge 2b // loop if j >= 0 |
|||
3: |
|||
add x5,x5,#1 // increment index j |
|||
str x4,[x0,x5,lsl #3] // store value A[i] in A[j+1] |
|||
add x3,x3,#1 // increment index i |
|||
cmp x3,x2 // end ? |
|||
blt 1b // no -> loop |
|||
100: |
|||
ldp x6,x7,[sp],16 |
|||
ldp x4,x5,[sp],16 |
|||
ldp x2,x3,[sp],16 |
|||
ldp x1,lr,[sp],16 |
|||
ret |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* x0 contains the address of array */ |
|||
displayArray: |
|||
stp x1,lr,[sp,-16]! |
|||
stp x2,x3,[sp,-16]! |
|||
mov x2,x0 // table address |
|||
mov x3,#0 |
|||
1: // loop display table |
|||
ldr x0,[x2,x3,lsl #3] |
|||
ldr x1,qAdrsMessValeur // display value |
|||
bl conversion10 // call function |
|||
ldr x0,qAdrsMessResult |
|||
bl affichageMess // display message |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
add x3,x3,#1 |
|||
cmp x3,#NBELEMENTS |
|||
blt 1b |
|||
ldr x0,qAdrszCarriageReturn |
|||
bl affichageMess |
|||
100: |
|||
ldp x2,x3,[sp],16 |
|||
ldp x1,lr,[sp],16 |
|||
ret |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
/* for this file see task include a file in language AArch64 assembly*/ |
|||
.include "../includeARM64.inc" |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Program 64 bits start. |
|||
Value : 7 |
|||
Value : 0 |
|||
Value : 5 |
|||
Value : 4 |
|||
Value : 3 |
|||
Value : 2 |
|||
Value : 1 |
|||
Value : 6 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size) |
|||
INT i |
|||
Put('[) |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
IF i>0 THEN Put(' ) FI |
|||
PrintI(a(i)) |
|||
OD |
|||
Put(']) PutE() |
|||
RETURN |
|||
BYTE FUNC InSet(INT ARRAY s INT size INT v) |
|||
INT i |
|||
FOR i=0 TO size-1 |
|||
DO |
|||
IF s(i)=v THEN |
|||
RETURN (1) |
|||
FI |
|||
OD |
|||
RETURN (0) |
|||
PROC Sort(INT ARRAY arr INT arrSize |
|||
INT ARRAY ind INT indSize) |
|||
INT i,j,minpos,tmp |
|||
FOR i=0 TO arrSize-2 |
|||
DO |
|||
IF InSet(ind,indSize,i) THEN |
|||
minpos=i |
|||
FOR j=i+1 TO arrSize-1 |
|||
DO |
|||
IF InSet(ind,indSize,j)=1 AND arr(minpos)>arr(j) THEN |
|||
minpos=j |
|||
FI |
|||
OD |
|||
IF minpos#i THEN |
|||
tmp=arr(i) |
|||
arr(i)=arr(minpos) |
|||
arr(minpos)=tmp |
|||
FI |
|||
FI |
|||
OD |
|||
RETURN |
|||
PROC Test(INT ARRAY arr INT arrSize |
|||
INT ARRAY ind INT indSize) |
|||
PrintE("Array before sort:") |
|||
PrintArray(arr,arrSize) |
|||
PrintE("Indices:") |
|||
PrintArray(ind,indSize) |
|||
Sort(arr,arrSize,ind,indSize) |
|||
PrintE("Array after sort:") |
|||
PrintArray(arr,arrSize) |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY |
|||
arr(8)=[7 6 5 4 3 2 1 0], |
|||
ind(3)=[6 1 7] |
|||
Test(arr,8,ind,3) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sort_disjoint_sublist.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Array before sort: |
|||
[7 6 5 4 3 2 1 0] |
|||
Indices: |
|||
[6 1 7] |
|||
Array after sort: |
|||
[7 0 5 4 3 2 1 6] |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, GNAT.Bubble_Sort; |
||
use Ada.Text_IO; |
use Ada.Text_IO; |
||
Line 68: | Line 342: | ||
New_Line; |
New_Line; |
||
end DisjointSort;</ |
end DisjointSort;</syntaxhighlight> |
||
=={{header| |
=={{header|ALGOL W}}== |
||
Uses the quicksort procedure from the Sorting Algorithms/Quicksort task and a variant for indexed sorting. |
|||
<syntaxhighlight lang="algolw">begin % sort a disjoint sub-set of a list % |
|||
% Quicksorts in-place the array of integers v, from lb to ub % |
|||
procedure quicksort ( integer array v( * ) |
|||
; integer value lb, ub |
|||
) ; |
|||
if ub > lb then begin |
|||
% more than one element, so must sort % |
|||
integer left, right, pivot; |
|||
left := lb; |
|||
right := ub; |
|||
% choosing the middle element of the array as the pivot % |
|||
pivot := v( left + ( ( right + 1 ) - left ) div 2 ); |
|||
while begin |
|||
while left <= ub and v( left ) < pivot do left := left + 1; |
|||
while right >= lb and v( right ) > pivot do right := right - 1; |
|||
left <= right |
|||
end do begin |
|||
integer swap; |
|||
swap := v( left ); |
|||
v( left ) := v( right ); |
|||
v( right ) := swap; |
|||
left := left + 1; |
|||
right := right - 1 |
|||
end while_left_le_right ; |
|||
quicksort( v, lb, right ); |
|||
quicksort( v, left, ub ) |
|||
end quicksort ; |
|||
% Quicksorts in-place the array of integers v, using % |
|||
% the indxexes in unsortedIndexes which has bounds lb to ub % |
|||
% it is assumed all elements of unsortedIndexes are in the % |
|||
% range for subscripts of v % |
|||
procedure indexedQuicksort ( integer array v, unsortedIndexes ( * ) |
|||
; integer value lb, ub |
|||
) ; |
|||
if ub > lb then begin |
|||
% more than one element, so must sort % |
|||
integer array indexes ( lb :: ub ); |
|||
integer left, right, pivot, p; |
|||
% sort the indexes % |
|||
for i := lb until ub do indexes( i ) := unsortedIndexes( i ); |
|||
quicksort( indexes, lb, ub ); |
|||
% sort the indexed items of the v array % |
|||
left := lb; |
|||
right := ub; |
|||
% choosing the middle element of the array as the pivot % |
|||
p := left + ( ( ( right + 1 ) - left ) div 2 ); |
|||
pivot := v( indexes( p ) ); |
|||
while begin |
|||
while left <= ub and v( indexes( left ) ) < pivot do left := left + 1; |
|||
while right >= lb and v( indexes( right ) ) > pivot do right := right - 1; |
|||
left <= right |
|||
end do begin |
|||
integer swap; |
|||
swap := v( indexes( left ) ); |
|||
v( indexes( left ) ) := v( indexes( right ) ); |
|||
v( indexes( right ) ) := swap; |
|||
left := left + 1; |
|||
right := right - 1 |
|||
end while_left_le_right ; |
|||
indexedQuicksort( v, indexes, lb, right ); |
|||
indexedQuicksort( v, indexes, left, ub ) |
|||
end indexedQuicksort ; |
|||
begin % task % |
|||
integer array indexes ( 0 :: 2 ); |
|||
integer array values ( 0 :: 7 ); |
|||
integer aPos; |
|||
aPos := 0; |
|||
for v := 7, 6, 5, 4, 3, 2, 1, 0 do begin |
|||
values( aPos ) := v; |
|||
aPos := aPos + 1 |
|||
end for_v ; |
|||
indexes( 0 ) := 6; |
|||
indexes( 1 ) := 1; |
|||
indexes( 2 ) := 7; |
|||
i_w := 1; s_w := 0; % set output formatting % |
|||
write( "[" ); |
|||
for v := 0 until 7 do writeon( " ", values( v ) ); |
|||
writeon( " ]" ); |
|||
indexedQuicksort( values, indexes, 0, 2 ); |
|||
writeon( " -> [" ); |
|||
for v := 0 until 7 do writeon( " ", values( v ) ); |
|||
writeon( " ]" ) |
|||
end |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 7 6 5 4 3 2 1 0 ] -> [ 7 0 5 4 3 2 1 6 ] |
|||
</pre> |
|||
=={{header|APL}}== |
|||
<syntaxhighlight lang="apl"> |
|||
∇SDS[⎕]∇ |
|||
∇ |
|||
[0] Z←I SDS L |
|||
[1] L[I[⍋I]]←Z[⍋Z←L[I←∪I]] |
|||
[2] Z←L |
|||
∇ |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
⎕IO←0 |
|||
6 1 7 SDS ⎕←⌽⍳8 |
|||
7 6 5 4 3 2 1 0 |
|||
7 0 5 4 3 2 1 6 |
|||
</pre> |
|||
=={{header|AppleScript}}== |
|||
===Functional=== |
|||
Uses Foundation framework (through the ObjC interface), and works with versions of AppleScript from OS X 10.10 onwards. |
|||
<syntaxhighlight lang="applescript">use AppleScript version "2.4" |
|||
use framework "Foundation" |
|||
use scripting additions |
|||
-- disjointSort :: [Int] -> [Int] -> [Int] |
|||
on disjointSort(ixs, xs) |
|||
set ks to sort(ixs) |
|||
script nth -- 1-based index |
|||
on |λ|(k) |
|||
item (succ(k)) of xs |
|||
end |λ| |
|||
end script |
|||
set dct to mapFromList(zip(ks, sort(map(nth, ks)))) |
|||
script build |
|||
on |λ|(x, i) |
|||
set mb to lookupDict(pred(i) as string, dct) |
|||
if Nothing of mb then |
|||
x |
|||
else |
|||
|Just| of mb |
|||
end if |
|||
end |λ| |
|||
end script |
|||
map(build, xs) |
|||
end disjointSort |
|||
on run |
|||
disjointSort({6, 1, 7}, {7, 6, 5, 4, 3, 2, 1, 0}) |
|||
end run |
|||
-- GENERIC FUNCTIONS ---------------------------------------------------- |
|||
-- Just :: a -> Maybe a |
|||
on Just(x) |
|||
{type:"Maybe", Nothing:false, Just:x} |
|||
end Just |
|||
-- Nothing :: Maybe a |
|||
on Nothing() |
|||
{type:"Maybe", Nothing:true} |
|||
end Nothing |
|||
-- length :: [a] -> Int |
|||
on |length|(xs) |
|||
set c to class of xs |
|||
if list is c or string is c then |
|||
length of xs |
|||
else |
|||
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite) |
|||
end if |
|||
end |length| |
|||
-- lookupDict :: a -> Dict -> Maybe b |
|||
on lookupDict(k, dct) |
|||
set ca to current application |
|||
set v to (ca's NSDictionary's dictionaryWithDictionary:dct)'s objectForKey:k |
|||
if v ≠ missing value then |
|||
Just(item 1 of ((ca's NSArray's arrayWithObject:v) as list)) |
|||
else |
|||
Nothing() |
|||
end if |
|||
end lookupDict |
|||
-- map :: (a -> b) -> [a] -> [b] |
|||
on map(f, xs) |
|||
tell mReturn(f) |
|||
set lng to length of xs |
|||
set lst to {} |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs, i, xs) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end map |
|||
-- mapFromList :: [(k, v)] -> Dict |
|||
on mapFromList(kvs) |
|||
set tpl to unzip(kvs) |
|||
script |
|||
on |λ|(x) |
|||
x as string |
|||
end |λ| |
|||
end script |
|||
(current application's NSDictionary's ¬ |
|||
dictionaryWithObjects:(|2| of tpl) ¬ |
|||
forKeys:map(result, |1| of tpl)) as record |
|||
end mapFromList |
|||
-- min :: Ord a => a -> a -> a |
|||
on min(x, y) |
|||
if y < x then |
|||
y |
|||
else |
|||
x |
|||
end if |
|||
end min |
|||
-- Lift 2nd class handler function into 1st class script wrapper |
|||
-- mReturn :: First-class m => (a -> b) -> m (a -> b) |
|||
on mReturn(f) |
|||
if class of f is script then |
|||
f |
|||
else |
|||
script |
|||
property |λ| : f |
|||
end script |
|||
end if |
|||
end mReturn |
|||
-- pred :: Enum a => a -> a |
|||
on pred(x) |
|||
x - 1 |
|||
end pred |
|||
-- sort :: Ord a => [a] -> [a] |
|||
on sort(xs) |
|||
((current application's NSArray's arrayWithArray:xs)'s ¬ |
|||
sortedArrayUsingSelector:"compare:") as list |
|||
end sort |
|||
-- succ :: Enum a => a -> a |
|||
on succ(x) |
|||
1 + x |
|||
end succ |
|||
-- take :: Int -> [a] -> [a] |
|||
-- take :: Int -> String -> String |
|||
on take(n, xs) |
|||
set c to class of xs |
|||
if list is c then |
|||
if 0 < n then |
|||
items 1 thru min(n, length of xs) of xs |
|||
else |
|||
{} |
|||
end if |
|||
else if string is c then |
|||
if 0 < n then |
|||
text 1 thru min(n, length of xs) of xs |
|||
else |
|||
"" |
|||
end if |
|||
else if script is c then |
|||
set ys to {} |
|||
repeat with i from 1 to n |
|||
set v to xs's |λ|() |
|||
if missing value is v then |
|||
return ys |
|||
else |
|||
set end of ys to v |
|||
end if |
|||
end repeat |
|||
return ys |
|||
else |
|||
missing value |
|||
end if |
|||
end take |
|||
-- Tuple (,) :: a -> b -> (a, b) |
|||
on Tuple(a, b) |
|||
{type:"Tuple", |1|:a, |2|:b, length:2} |
|||
end Tuple |
|||
-- unzip :: [(a,b)] -> ([a],[b]) |
|||
on unzip(xys) |
|||
set xs to {} |
|||
set ys to {} |
|||
repeat with xy in xys |
|||
set end of xs to |1| of xy |
|||
set end of ys to |2| of xy |
|||
end repeat |
|||
return Tuple(xs, ys) |
|||
end unzip |
|||
-- zip :: [a] -> [b] -> [(a, b)] |
|||
on zip(xs, ys) |
|||
zipWith(Tuple, xs, ys) |
|||
end zip |
|||
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
on zipWith(f, xs, ys) |
|||
set lng to min(|length|(xs), |length|(ys)) |
|||
if 1 > lng then return {} |
|||
set xs_ to take(lng, xs) -- Allow for non-finite |
|||
set ys_ to take(lng, ys) -- generators like cycle etc |
|||
set lst to {} |
|||
tell mReturn(f) |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs_, item i of ys_) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end zipWith</syntaxhighlight> |
|||
{{Out}} |
|||
<syntaxhighlight lang="applescript">{7, 0, 5, 4, 3, 2, 1, 6}</syntaxhighlight> |
|||
===Idiomatic, vanilla=== |
|||
This works with Mac OS 10.9 or later, and with older systems if an earlier method's used to load the insertion sort handler or that handler's copied into the script. |
|||
<syntaxhighlight lang="applescript">use AppleScript version "2.3.1" -- Mac OS 10.9 (Mavericks) or later. |
|||
use sorter : script "Insertion sort" -- https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript. |
|||
on sortValuesAtIndices(values, indices) |
|||
set indexedValues to {} |
|||
repeat with thisIndex in indices |
|||
set end of indexedValues to item thisIndex of values |
|||
end repeat |
|||
set indexCount to (count indices) |
|||
tell sorter to sort(indexedValues, 1, indexCount) |
|||
tell sorter to sort(indices, 1, indexCount) |
|||
repeat with i from 1 to indexCount |
|||
set thisIndex to item i of indices |
|||
set item thisIndex of values to item i of indexedValues |
|||
end repeat |
|||
return |
|||
end sortValuesAtIndices |
|||
-- Test code: |
|||
set values to {7, 6, 5, 4, 3, 2, 1, 0} |
|||
set indices to {7, 2, 8} -- AppleScript indices are one-based. |
|||
sortValuesAtIndices(values, indices) |
|||
return values</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight lang="applescript">{7, 0, 5, 4, 3, 2, 1, 6}</syntaxhighlight> |
|||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<syntaxhighlight lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program sublistSort.s */ |
|||
/************************************/ |
|||
/* Constantes */ |
|||
/************************************/ |
|||
/* for constantes see task include a file in arm assembly */ |
|||
.include "../constantes.inc" |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessStart: .asciz "Program 32 bits start.\n" |
|||
sMessResult: .ascii "Value : " |
|||
sMessValeur: .fill 11, 1, ' ' @ size => 11 |
|||
szCarriageReturn: .asciz "\n" |
|||
.align 4 |
|||
ArrayNumber: .int 7, 6, 5, 4, 3, 2, 1, 0 |
|||
.equ NBELEMENTS, (. - ArrayNumber) / 4 |
|||
ArrayIndex: .int 6,1,7 |
|||
.equ NBELEMINDEX, (. - ArrayIndex) / 4 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
ArrayExtract: .skip 4 * NBELEMINDEX |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: |
|||
ldr r0,iAdrszMessStart |
|||
bl affichageMess |
|||
ldr r4,iAdrArrayNumber @ number array address |
|||
ldr r5,iAdrArrayIndex @ index array address |
|||
ldr r6,iAdrArrayExtract @ extract array address |
|||
mov r3,#0 @ index |
|||
1: |
|||
ldr r0,[r5,r3,lsl #2] @ load index |
|||
ldr r1,[r4,r0,lsl #2] @ load value of index |
|||
str r1,[r6,r3,lsl #2] @ store value in array extract |
|||
add r3,r3,#1 @ increment index |
|||
cmp r3,#NBELEMINDEX @ end array index ? |
|||
blt 1b @ no -> loop |
|||
mov r0,r5 @ index array address |
|||
mov r1,#0 @ first element |
|||
mov r2,#NBELEMINDEX @ array size |
|||
bl insertionSort |
|||
mov r0,r6 @ extract array address |
|||
mov r1,#0 @ first element |
|||
mov r2,#NBELEMINDEX @ array size |
|||
bl insertionSort |
|||
mov r3,#0 @ init index |
|||
2: |
|||
ldr r0,[r6,r3,lsl #2] @ load value of array extract |
|||
ldr r1,[r5,r3,lsl #2] @ load index |
|||
str r0,[r4,r1,lsl #2] @ store value in number array in index place |
|||
add r3,r3,#1 @ increment indice |
|||
cmp r3,#NBELEMINDEX |
|||
blt 2b |
|||
mov r0,r4 @ number array address |
|||
bl displayArray |
|||
100: @ standard end of the program |
|||
mov r0, #0 @ return code |
|||
mov r7, #EXIT @ request to exit program |
|||
svc #0 @ perform the system call |
|||
iAdrsMessValeur: .int sMessValeur |
|||
iAdrszMessStart: .int szMessStart |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrsMessResult: .int sMessResult |
|||
iAdrArrayNumber: .int ArrayNumber |
|||
iAdrArrayIndex: .int ArrayIndex |
|||
iAdrArrayExtract: .int ArrayExtract |
|||
/******************************************************************/ |
|||
/* insertion sort */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
/* r1 contains the first element */ |
|||
/* r2 contains the number of element */ |
|||
insertionSort: |
|||
push {r2-r6,lr} @ save registers |
|||
add r3,r1,#1 @ start index i |
|||
1: @ start loop |
|||
ldr r4,[r0,r3,lsl #2] @ load value A[i] |
|||
sub r5,r3,#1 @ index j |
|||
2: |
|||
ldr r6,[r0,r5,lsl #2] @ load value A[j] |
|||
cmp r6,r4 @ compare value |
|||
ble 3f |
|||
add r5,#1 @ increment index j |
|||
str r6,[r0,r5,lsl #2] @ store value A[j+1] |
|||
subs r5,#2 @ j = j - 1 |
|||
bge 2b @ loop if j >= 0 |
|||
3: |
|||
add r5,#1 @ increment index j |
|||
str r4,[r0,r5,lsl #2] @ store value A[i] in A[j+1] |
|||
add r3,#1 @ increment index i |
|||
cmp r3,r2 @ end ? |
|||
blt 1b @ no -> loop |
|||
100: |
|||
pop {r2-r6,pc} |
|||
/******************************************************************/ |
|||
/* Display table elements */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of table */ |
|||
displayArray: |
|||
push {r0-r3,lr} @ save registers |
|||
mov r2,r0 @ table address |
|||
mov r3,#0 |
|||
1: @ loop display table |
|||
ldr r0,[r2,r3,lsl #2] |
|||
ldr r1,iAdrsMessValeur @ display value |
|||
bl conversion10 @ call function |
|||
ldr r0,iAdrsMessResult |
|||
bl affichageMess @ display message |
|||
add r3,#1 |
|||
cmp r3,#NBELEMENTS |
|||
blt 1b |
|||
ldr r0,iAdrszCarriageReturn |
|||
bl affichageMess |
|||
100: |
|||
pop {r0-r3,lr} |
|||
bx lr |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
/* for this file see task include a file in language ARM assembly*/ |
|||
.include "../affichage.inc" |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Program 32 bits start. |
|||
Value : 7 |
|||
Value : 0 |
|||
Value : 5 |
|||
Value : 4 |
|||
Value : 3 |
|||
Value : 2 |
|||
Value : 1 |
|||
Value : 6 |
|||
</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">sortDisjoint: function [data, indices][ |
|||
result: new data |
|||
inds: new indices |
|||
sort 'inds |
|||
vals: new [] |
|||
loop inds 'i -> 'vals ++ result\[i] |
|||
sort 'vals |
|||
loop.with:'j inds 'i -> result\[i]: vals\[j] |
|||
return result |
|||
] |
|||
d: [7 6 5 4 3 2 1 0] |
|||
print sortDisjoint d [6 1 7]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7 0 5 4 3 2 1 6</pre> |
|||
=={{header|ATS}}== |
|||
Much of the code here is proofs, unfolding and re-folding of lists, necessary assertions, memory management enforced by the type system, etc. (Some might say I am somewhat lax in my handling of pointers, using the simplest type '''ptr''' instead of more elaborate types.) |
|||
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats" |
|||
staload UN = "prelude/SATS/unsafe.sats" |
|||
(* For simplicity, I implement this task only for sorting values of |
|||
non-linear type. That would include all the basic integer types, |
|||
garbage-collected strings, etc. |
|||
Also I freely create arrays as workspace, although the size of any |
|||
workspace array is equal only to the number of indices (not to the |
|||
number of values). *) |
|||
extern fn {a : t@ype} |
|||
sort_disjoint_sublist$cmp : (a, a) -<> int |
|||
fn {a : t@ype} |
|||
sort_disjoint_sublist |
|||
{m : int} |
|||
{n : int} |
|||
(values : &list_vt (a, m) >> _, |
|||
indices : list ([i : nat | i < m] int i, n)) |
|||
: void = |
|||
let |
|||
typedef index = [i : nat | i < m] int i |
|||
prval () = lemma_list_vt_param values |
|||
prval () = lemma_list_param indices |
|||
val num_values : size_t m = i2sz (list_vt_length values) |
|||
and num_indices : size_t n = i2sz (list_length indices) |
|||
(* Put the indices in ascending order. *) |
|||
val @(pf_ix, pfgc_ix | p_ix) = |
|||
array_ptr_alloc<index> num_indices |
|||
macdef ix = !p_ix |
|||
val () = array_initize_list<index> (ix, sz2i num_indices, indices) |
|||
implement |
|||
array_quicksort$cmp<index> (x, y) = |
|||
if x < y then ~1 else 1 |
|||
val () = array_quicksort<index> (ix, num_indices) |
|||
(* Initialize a "refs" array with pointers to the relevant list |
|||
nodes. The pointers will be in ascending index order. *) |
|||
val @(pf_refs, pfgc_refs | p_refs) = |
|||
array_ptr_alloc<ptr> num_indices |
|||
fun |
|||
init_refs {j : nat | j <= m} |
|||
{i : nat | i <= n} |
|||
{p_refs : addr} |
|||
.<m - j>. |
|||
(pf_refs : !array_v (ptr?, p_refs + (i * sizeof ptr), |
|||
n - i) |
|||
>> array_v (ptr, p_refs + (i * sizeof ptr), |
|||
n - i) | |
|||
ix : &array (index, n), |
|||
p_refs : ptr p_refs, |
|||
i : size_t i, |
|||
values : &list_vt (a, m - j), |
|||
j : size_t j) |
|||
:<!wrt> void = |
|||
if i < num_indices then |
|||
case+ values of |
|||
| list_vt_nil () => $effmask_exn assertloc (false) |
|||
| @ list_vt_cons (head, tail) => |
|||
if j = ix[i] then |
|||
let |
|||
prval @(pf_elem, pf_rest) = array_v_uncons pf_refs |
|||
val p = ptr_add<ptr> (p_refs, i) |
|||
val () = ptr_set<ptr> (pf_elem | p, addr@ values) |
|||
val () = init_refs (pf_rest | ix, p_refs, succ i, |
|||
tail, succ j) |
|||
prval () = pf_refs := array_v_cons (pf_elem, pf_rest) |
|||
prval () = fold@ values |
|||
in |
|||
end |
|||
else |
|||
let |
|||
val () = init_refs (pf_refs | ix, p_refs, i, |
|||
tail, succ j) |
|||
prval () = fold@ values |
|||
in |
|||
end |
|||
else |
|||
let |
|||
prval () = pf_refs := array_v_unnil_nil{ptr?, ptr} pf_refs |
|||
in |
|||
end |
|||
val () = init_refs (pf_refs | ix, p_refs, i2sz 0, values, i2sz 0) |
|||
(* Sort through the "refs" pointers. Here we will do that by |
|||
copying the values to an array, sorting the array, then writing |
|||
the sorted values back. One could also do the sort in place, |
|||
however. *) |
|||
val @(pf_vals, pfgc_vals | p_vals) = |
|||
array_ptr_alloc<a> num_indices |
|||
macdef vals = !p_vals |
|||
implement |
|||
array_initize$init<a> (i, x) = |
|||
let |
|||
val @(pf1, fpf1 | p1) = $UN.ptr_vtake{array (ptr, n)} p_refs |
|||
macdef refs = !p1 |
|||
val i1 = g1ofg0 i |
|||
prval () = lemma_g1uint_param i1 |
|||
val () = assertloc (i1 < num_indices) |
|||
val @(pf2, fpf2 | p2) = $UN.ptr_vtake{List1_vt a} (refs[i1]) |
|||
val+ @ list_vt_cons (head, tail) = !p2 |
|||
val () = x := head |
|||
prval () = fold@ (!p2) |
|||
prval () = fpf2 pf2 |
|||
prval () = fpf1 pf1 |
|||
in |
|||
end |
|||
val () = array_initize<a> (vals, num_indices) |
|||
implement |
|||
array_quicksort$cmp<a> (x, y) = |
|||
sort_disjoint_sublist$cmp<a> (x, y) |
|||
val () = array_quicksort<a> (vals, num_indices) |
|||
fun |
|||
write_back_values |
|||
{i : nat | i <= n} |
|||
{p_refs : addr} |
|||
(pf_refs : !array_v (ptr, p_refs, n) | |
|||
p_refs : ptr p_refs, |
|||
vals : &array (a, n), |
|||
i : size_t i) |
|||
: void = |
|||
if i <> num_indices then |
|||
let |
|||
macdef refs = !p_refs |
|||
val @(pf1, fpf1 | p1) = $UN.ptr_vtake{List1_vt a} (refs[i]) |
|||
val+ @ list_vt_cons (head, tail) = !p1 |
|||
val () = head := vals[i] |
|||
prval () = fold@ (!p1) |
|||
prval () = fpf1 pf1 |
|||
in |
|||
write_back_values (pf_refs | p_refs, vals, succ i) |
|||
end |
|||
val () = write_back_values (pf_refs | p_refs, vals, i2sz 0) |
|||
in |
|||
array_ptr_free (pf_ix, pfgc_ix | p_ix); |
|||
array_ptr_free (pf_refs, pfgc_refs | p_refs); |
|||
array_ptr_free (pf_vals, pfgc_vals | p_vals) |
|||
end |
|||
implement |
|||
sort_disjoint_sublist$cmp<int> (x, y) = |
|||
if x < y then |
|||
~1 |
|||
else if y < x then |
|||
1 |
|||
else |
|||
0 |
|||
implement |
|||
main0 () = |
|||
let |
|||
var values = $list_vt{int} (7, 6, 5, 4, 3, 2, 1, 0) |
|||
val indices = $list{[i : nat | i < 8] int i} (6, 1, 7) |
|||
in |
|||
println! values; |
|||
sort_disjoint_sublist<int> (values, indices); |
|||
println! values; |
|||
free values |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>$ patscc -DATS_MEMALLOC_GCBDW -O3 sort_disjoint_sublist_task.dats -lgc && ./a.out |
|||
7, 6, 5, 4, 3, 2, 1, 0 |
|||
7, 0, 5, 4, 3, 2, 1, 6</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">Sort_disjoint_sublist(Values, Indices){ |
|||
A := [], B:=[], C := [], D := [] |
|||
for k, v in Indices |
|||
A[v] := 1 , B[Values[v]] := v |
|||
for k, v in A |
|||
C.Push(k) |
|||
for k, v in B |
|||
D.Push(k) |
|||
for k, v in D |
|||
Values[C[A_Index]] := D[A_Index] |
|||
return Values |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">Values := [7, 6, 5, 4, 3, 2, 1, 0] |
|||
Indices := [7, 2, 8] |
|||
Values := Sort_disjoint_sublist(Values, Indices) |
|||
for k, v in Values |
|||
output .= v ", " |
|||
MsgBox % "[" Trim(output, ", ") "]" ; show output</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|Applesoft BASIC}}=== |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|BBC BASIC}}=== |
|||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> INSTALL @lib$+"SORTLIB" |
||
Sort% = FN_sortinit(0,0) : REM Ascending |
Sort% = FN_sortinit(0,0) : REM Ascending |
||
Line 103: | Line 1,099: | ||
o$ += STR$(l%(i%)) + ", " |
o$ += STR$(l%(i%)) + ", " |
||
NEXT |
NEXT |
||
= LEFT$(LEFT$(o$)) + "]"</ |
= LEFT$(LEFT$(o$)) + "]"</syntaxhighlight> |
||
{{out}} |
|||
'''Output:''' |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
<pre> |
|||
[7, 0, 5, 4, 3, 2, 1, 6] |
|||
==={{header|Chipmunk Basic}}=== |
|||
</pre> |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
<syntaxhighlight lang="qbasic">100 cls |
|||
110 dim values(7) |
|||
120 data 7,6,5,4,3,2,1,0 |
|||
130 for i = 0 to 7 |
|||
140 read values(i) |
|||
150 next |
|||
160 dim indices(2) |
|||
170 data 6,1,7 |
|||
180 for i = 0 to 2 |
|||
190 read indices(i) |
|||
200 next |
|||
210 print "Before sort:" |
|||
220 for i = 0 to ubound(values) |
|||
230 print values(i); |
|||
240 next i |
|||
250 print |
|||
260 print |
|||
270 print "After sort:" |
|||
280 for i = 0 to 1 |
|||
290 if values(indices(i)) > values(indices(i+1)) then |
|||
300 temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp |
|||
310 endif |
|||
320 next i |
|||
330 for i = 0 to ubound(values) |
|||
340 print values(i); |
|||
350 next i |
|||
360 print |
|||
370 end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|FreeBASIC}}=== |
|||
<syntaxhighlight lang="freebasic">dim as integer value(0 to 7) = {7, 6, 5, 4, 3, 2, 1, 0} |
|||
dim as integer index(0 to 2) = {6, 1, 7}, i |
|||
for i = 0 to 1 |
|||
if value(index(i))>value(index(i+1)) then |
|||
swap value(index(i)), value(index(i+1)) |
|||
end if |
|||
next i |
|||
for i = 0 to 7 |
|||
print value(i); |
|||
next i : print</syntaxhighlight> |
|||
{{out}}<pre> 7 0 5 4 3 2 1 6</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|Applesoft BASIC}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|PC-BASIC|any}} |
|||
{{works with|QBasic}} |
|||
{{works with|Quite BASIC}} |
|||
<syntaxhighlight lang="qbasic">100 CLS : rem 100 HOME for Applesoft BASIC |
|||
110 DIM V(7) |
|||
120 DATA 7,6,5,4,3,2,1,0 |
|||
130 FOR C = 0 TO 7 |
|||
140 READ V(C) |
|||
150 NEXT C |
|||
160 DIM I(2) |
|||
170 DATA 6,1,7 |
|||
180 FOR C = 0 TO 2 |
|||
190 READ I(C) |
|||
200 NEXT C |
|||
210 PRINT "Before sort:" |
|||
220 FOR C = 0 TO 7 |
|||
230 PRINT V(C); " "; |
|||
240 NEXT C |
|||
250 PRINT |
|||
260 PRINT |
|||
270 PRINT "After sort:" |
|||
280 FOR C = 0 TO 1 |
|||
290 IF V(I(C)) > V(I(C+1)) THEN LET T = V(I(C)) : LET V(I(C)) = V(I(C+1)) : LET V(I(C+1)) = T |
|||
300 NEXT C |
|||
310 FOR C = 0 TO 7 |
|||
320 PRINT V(C); " "; |
|||
330 NEXT C |
|||
340 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Minimal BASIC}}=== |
|||
{{works with|QBasic}} |
|||
{{works with|QuickBasic}} |
|||
{{works with|Applesoft BASIC}} |
|||
{{works with|BASICA}} |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|GW-BASIC}} |
|||
{{works with|MSX BASIC|any}} |
|||
<syntaxhighlight lang="qbasic">110 DIM V(7) |
|||
120 DATA 7,6,5,4,3,2,1,0 |
|||
130 FOR C = 0 TO 7 |
|||
140 READ V(C) |
|||
150 NEXT C |
|||
160 DIM I(2) |
|||
170 DATA 6,1,7 |
|||
180 FOR C = 0 TO 2 |
|||
190 READ I(C) |
|||
200 NEXT C |
|||
210 PRINT "BEFORE SORT:" |
|||
220 FOR C = 0 TO 7 |
|||
230 PRINT V(C);" "; |
|||
240 NEXT C |
|||
250 PRINT |
|||
260 PRINT |
|||
270 PRINT "AFTER SORT:" |
|||
280 FOR C = 0 TO 1 |
|||
290 IF V(I(C)) > V(I(C+1)) THEN 310 |
|||
300 GOTO 340 |
|||
310 LET T = V(I(C)) |
|||
320 LET V(I(C)) = V(I(C+1)) |
|||
330 LET V(I(C+1)) = T |
|||
340 NEXT C |
|||
350 FOR C = 0 TO 7 |
|||
360 PRINT V(C);" "; |
|||
370 NEXT C |
|||
380 END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|MSX Basic}}=== |
|||
{{works with|MSX BASIC|any}} |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|PureBasic}}=== |
|||
Based on the C implementation |
|||
<syntaxhighlight lang="purebasic">Procedure Bubble_sort(Array idx(1), n, Array buf(1)) |
|||
Protected i, j |
|||
SortArray(idx(),#PB_Sort_Ascending) |
|||
For i=0 To n |
|||
For j=i+1 To n |
|||
If buf(idx(j)) < buf(idx(i)) |
|||
Swap buf(idx(j)), buf(idx(i)) |
|||
EndIf |
|||
Next |
|||
Next |
|||
EndProcedure |
|||
Procedure main() |
|||
DataSection |
|||
values: Data.i 7, 6, 5, 4, 3, 2, 1, 0 |
|||
indices:Data.i 6, 1, 7 |
|||
EndDataSection |
|||
Dim values.i(7) :CopyMemory(?values, @values(), SizeOf(Integer)*8) |
|||
Dim indices.i(2):CopyMemory(?indices,@indices(),SizeOf(Integer)*3) |
|||
If OpenConsole() |
|||
Protected i |
|||
PrintN("Before sort:") |
|||
For i=0 To ArraySize(values()) |
|||
Print(Str(values(i))+" ") |
|||
Next |
|||
PrintN(#CRLF$+#CRLF$+"After sort:") |
|||
Bubble_sort(indices(), ArraySize(indices()), values()) |
|||
For i=0 To ArraySize(values()) |
|||
Print(Str(values(i))+" ") |
|||
Next |
|||
Print(#CRLF$+#CRLF$+"Press ENTER to exit") |
|||
Input() |
|||
EndIf |
|||
EndProcedure |
|||
main()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Before sort: |
|||
7 6 5 4 3 2 1 0 |
|||
After sort: |
|||
7 0 5 4 3 2 1 6</pre> |
|||
==={{header|Run BASIC}}=== |
|||
Normally we sort with SQLite in memory. Faster and less code |
|||
<syntaxhighlight lang="runbasic">sortData$ = "7, 6, 5, 4, 3, 2, 1, 0" |
|||
sortIdx$ = "7, 2, 8" |
|||
numSort = 8 |
|||
dim sortData(numSort) |
|||
for i = 1 to numSort |
|||
sortData(i) = val(word$(sortData$,i,",")) |
|||
next i |
|||
while word$(sortIdx$,s + 1) <> "" |
|||
s = s + 1 |
|||
idx = val(word$(sortIdx$,s)) |
|||
gosub [bubbleSort] |
|||
wend |
|||
end |
|||
[bubbleSort] |
|||
sortSw = 1 |
|||
while sortSw = 1 |
|||
sortSw = 0 |
|||
for i = idx to numSort - 1 ' start sorting at idx |
|||
if sortData(i) > sortData(i+1) then |
|||
sortSw = 1 |
|||
sortHold = sortData(i) |
|||
sortData(i) = sortData(i+1) |
|||
sortData(i+1) = sortHold |
|||
end if |
|||
next i |
|||
wend |
|||
RETURN</syntaxhighlight> |
|||
==={{header|True BASIC}}=== |
|||
<syntaxhighlight lang="qbasic">OPTION BASE 0 |
|||
SUB SWAP(vb1, vb2) |
|||
LET temp = vb1 |
|||
LET vb1 = vb2 |
|||
LET vb2 = temp |
|||
END SUB |
|||
DIM values(7) |
|||
DATA 7, 6, 5, 4, 3, 2, 1, 0 |
|||
FOR i = 0 TO 7 |
|||
READ values(i) |
|||
NEXT i |
|||
DIM indices(2) |
|||
DATA 6, 1, 7 |
|||
FOR i = 0 TO 2 |
|||
READ indices(i) |
|||
NEXT i |
|||
PRINT "Before sort:" |
|||
FOR i = 0 TO 7 !UBOUND(values) |
|||
PRINT values(i); |
|||
NEXT i |
|||
PRINT |
|||
PRINT |
|||
PRINT "After sort:" |
|||
FOR i = 0 TO 1 |
|||
IF values(indices(i)) > values(indices(i+1)) THEN CALL SWAP (values(indices(i)), values(indices(i+1))) |
|||
NEXT i |
|||
FOR i = 0 TO 7 !UBOUND(values) |
|||
PRINT values(i); |
|||
NEXT i |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as BASIC entry.</pre> |
|||
==={{header|Yabasic}}=== |
|||
<syntaxhighlight lang="vb">dim values(7) |
|||
values(0) = 7 : values(1) = 6 : values(2) = 5 |
|||
values(3) = 4 : values(4) = 3 : values(5) = 2 |
|||
values(6) = 1 : values(7) = 0 |
|||
dim indices(2) |
|||
indices(0) = 6 : indices(1) = 1 : indices(2) = 7 |
|||
print "Before sort:" |
|||
for i = 0 to arraysize(values(),1) |
|||
print values(i), " "; |
|||
next i |
|||
print "\n\nAfter sort:" |
|||
for i = 0 to 1 |
|||
if values(indices(i)) > values(indices(i + 1)) then |
|||
temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp |
|||
end if |
|||
next i |
|||
for i = 0 to arraysize(values(),1) |
|||
print values(i), " "; |
|||
next i |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as BASIC entry.</pre> |
|||
=={{header|Bracmat}}== |
|||
<syntaxhighlight lang="bracmat">7 6 5 4 3 2 1 0:?values |
|||
& 6 1 7:?indices |
|||
& 0:?sortedValues:?sortedIndices |
|||
& whl |
|||
' ( !indices:%?i ?indices |
|||
& !values:? [!i %@?value ? |
|||
& (!value.)+!sortedValues:?sortedValues |
|||
& (!i.)+!sortedIndices:?sortedIndices |
|||
) |
|||
& whl |
|||
' ( !sortedIndices:(?i.)+?sortedIndices |
|||
& !values:?A [!i %@? ?Z |
|||
& !sortedValues:(?value.)+?sortedValues |
|||
& !A !value !Z:?values |
|||
) |
|||
& out$!values;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7 0 5 4 3 2 1 6</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
/* yes, bubble sort */ |
/* yes, bubble sort */ |
||
Line 142: | Line 1,428: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp}}== |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Linq; |
|||
using System.Collections.Generic; |
|||
public class Test |
|||
{ |
|||
public static void Main() |
|||
{ |
|||
var list = new List<int>{ 7, 6, 5, 4, 3, 2, 1, 0 }; |
|||
list.SortSublist(6, 1, 7); |
|||
Console.WriteLine(string.Join(", ", list)); |
|||
} |
|||
} |
|||
public static class Extensions |
|||
{ |
|||
public static void SortSublist<T>(this List<T> list, params int[] indices) |
|||
where T : IComparable<T> |
|||
{ |
|||
var sublist = indices.OrderBy(i => i) |
|||
.Zip(indices.Select(i => list[i]).OrderBy(v => v), |
|||
(Index, Value) => new { Index, Value }); |
|||
foreach (var entry in sublist) { |
|||
list[entry.Index] = entry.Value; |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <iterator> |
#include <iterator> |
||
Line 178: | Line 1,495: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 186: | Line 1,503: | ||
{{trans|Go}} |
{{trans|Go}} |
||
Solution that sorts using a custom iterator that iterates a disjoint sublist. |
Solution that sorts using a custom iterator that iterates a disjoint sublist. |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <iterator> |
#include <iterator> |
||
Line 247: | Line 1,564: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
7 0 5 4 3 2 1 6 |
7 0 5 4 3 2 1 6 |
||
</pre> |
</pre> |
||
=={{header|Clojure}}== |
|||
<syntaxhighlight lang="clojure">(defn disjoint-sort [coll idxs] |
|||
(let [val-subset (keep-indexed #(when ((set idxs) %) %2) coll) |
|||
replacements (zipmap (set idxs) (sort val-subset))] |
|||
(apply assoc coll (flatten (seq replacements)))))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>user=> (disjoint-sort [7 6 5 4 3 2 1 0] #{6 1 7}) |
|||
[7 0 5 4 3 2 1 6]</pre> |
|||
=={{header|Common Lisp}}== |
|||
<syntaxhighlight lang="lisp">(defun disjoint-sort (values indices) |
|||
"Destructively perform a disjoin sublist sort on VALUES with INDICES." |
|||
(loop :for element :in |
|||
(sort (loop :for index :across indices |
|||
:collect (svref values index)) |
|||
'<) |
|||
:for index :across (sort indices '<) |
|||
:do (setf (svref values index) element)) |
|||
values)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>CL-USER> (disjoint-sort #(7 6 5 4 3 2 1 0) #(6 1 7)) |
|||
#(7 0 5 4 3 2 1 6)</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.algorithm, std.range, std.array; |
||
void main() { |
void main() { |
||
Line 260: | Line 1,601: | ||
auto indices = [6, 1, 7]; |
auto indices = [6, 1, 7]; |
||
data.indexed(indices.sort()).sort(); |
|||
data.indexed(idxSet).sort(); |
|||
assert(data == [7, 0, 5, 4, 3, 2, 1, 6]); |
assert(data == [7, 0, 5, 4, 3, 2, 1, 6]); |
||
}</ |
}</syntaxhighlight> |
||
===Lower Level version=== |
===Lower Level version=== |
||
< |
<syntaxhighlight lang="d">import std.algorithm: swap; |
||
void disjointSort(T, U)(T[] arr, U[] indexes) |
void disjointSort(T, U)(T[] arr, U[] indexes) |
||
Line 306: | Line 1,646: | ||
disjointSort(data, indexes); |
disjointSort(data, indexes); |
||
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]); |
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]); |
||
}</ |
}</syntaxhighlight> |
||
===Simple Alternative Version=== |
===Simple Alternative Version=== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm; |
||
void main() { |
void main() { |
||
Line 327: | Line 1,667: | ||
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]); |
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi">{Test values} |
|||
var Values: array [0..7] of integer = (7, 6, 5, 4, 3, 2, 1, 0); |
|||
var indices: array [0..2] of integer = (6, 1, 7); |
|||
function CompareValues(Item1, Item2: Pointer): Integer; |
|||
{Compare the values pointed to by the indices} |
|||
begin |
|||
Result:=Values[integer(Item1)]-Values[integer(Item2)]; |
|||
end; |
|||
function CompareIndices(Item1, Item2: Pointer): Integer; |
|||
{Compare the indices themselves} |
|||
begin |
|||
Result:=integer(Item1)-integer(Item2); |
|||
end; |
|||
procedure SortDisjointSublist(Memo: TMemo); |
|||
var L1,L2: TList; |
|||
var I,Inx1,Inx2: integer; |
|||
var OutList: TIntegerDynArray; |
|||
var S: string; |
|||
begin |
|||
L1:=TList.Create; |
|||
L2:=TList.Create; |
|||
try |
|||
{Copy values array to output array} |
|||
SetLength(OutList,Length(Values)); |
|||
for I:=0 to High(Values) do OutList[I]:=Values[I]; |
|||
{Load two lists with the indices} |
|||
for I:=0 to High(Indices) do |
|||
begin |
|||
L1.Add(Pointer(Indices[I])); |
|||
L2.Add(Pointer(Indices[I])); |
|||
end; |
|||
{Sort by index and by value} |
|||
L1.Sort(CompareValues); |
|||
L2.Sort(CompareIndices); |
|||
{Copy the sorted values through the sorted indices} |
|||
for I:=0 to L1.Count-1 do |
|||
OutList[Integer(L2[I])]:=Values[Integer(L1[I])]; |
|||
{Display the result} |
|||
S:='['; |
|||
for I:=0 to High(OutLIst) do |
|||
begin |
|||
if I>0 then S:=S+' '; |
|||
S:=S+IntToStr(OutList[I]); |
|||
end; |
|||
S:=S+']'; |
|||
Memo.Lines.Add(S); |
|||
finally |
|||
L1.Free; |
|||
L2.Free; |
|||
end; |
|||
end;</syntaxhighlight> |
|||
{{out}}<pre> |
|||
[7 0 5 4 3 2 1 6] |
|||
Elapsed Time: 0.626 ms.</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang=text> |
|||
val[] = [ 7 6 5 4 3 2 1 0 ] |
|||
ind[] = [ 7 2 8 ] |
|||
# |
|||
for i = 1 to len ind[] - 1 |
|||
for j = i + 1 to len ind[] |
|||
if ind[j] < ind[i] |
|||
swap ind[j] ind[i] |
|||
. |
|||
. |
|||
. |
|||
for i = 1 to len ind[] - 1 |
|||
for j = i + 1 to len ind[] |
|||
if val[ind[j]] < val[ind[i]] |
|||
swap val[ind[j]] val[ind[i]] |
|||
. |
|||
. |
|||
. |
|||
print val[] |
|||
</syntaxhighlight> |
|||
=={{header|EchoLisp}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
(define (sort-disjoint values indices) |
|||
(define sorted (list-sort < |
|||
(for/list [(v values) (i (in-naturals))] |
|||
#:when (member i indices) v))) |
|||
(for/list [(v values) (i (in-naturals))] |
|||
(if (not (member i indices)) v |
|||
(begin0 |
|||
(first sorted) |
|||
(set! sorted (rest sorted)))))) |
|||
(define (task) |
|||
(sort-disjoint '[7 6 5 4 3 2 1 0] {6 1 7})) |
|||
(task) |
|||
→ (7 0 5 4 3 2 1 6) |
|||
</syntaxhighlight> |
|||
=={{header|Elena}}== |
|||
ELENA 6.x : |
|||
<syntaxhighlight lang="elena">import extensions; |
|||
import system'routines; |
|||
import system'culture; |
|||
extension op |
|||
{ |
|||
sortSublist(indices) |
|||
{ |
|||
var subList := indices.orderBy::(x => x) |
|||
.zipBy(indices.selectBy::(i => self[i]) |
|||
.orderBy::(x => x), (index,val => new{ Index = index; Value = val; })) |
|||
.toArray(); |
|||
var list := self.clone(); |
|||
subList.forEach::(r) |
|||
{ |
|||
list[r.Index] := r.Value |
|||
}; |
|||
^ list |
|||
} |
|||
} |
|||
public program() |
|||
{ |
|||
var list := new int[]{ 7, 6, 5, 4, 3, 2, 1, 0 }; |
|||
console.printLine(list.sortSublist(new int[]{6, 1, 7}).asEnumerable()) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7,0,5,4,3,2,1,6</pre> |
|||
=={{header|Elixir}}== |
|||
<syntaxhighlight lang="elixir">defmodule Sort_disjoint do |
|||
def sublist(values, indices) when is_list(values) and is_list(indices) do |
|||
indices2 = Enum.sort(indices) |
|||
selected = select(values, indices2, 0, []) |> Enum.sort |
|||
replace(values, Enum.zip(indices2, selected), 0, []) |
|||
end |
|||
defp select(_, [], _, selected), do: selected |
|||
defp select([val|t], [i|rest], i, selected), do: select(t, rest, i+1, [val|selected]) |
|||
defp select([_|t], indices, i, selected), do: select(t, indices, i+1, selected) |
|||
defp replace(values, [], _, list), do: Enum.reverse(list, values) |
|||
defp replace([_|t], [{i,v}|rest], i, list), do: replace(t, rest, i+1, [v|list]) |
|||
defp replace([val|t], indices, i, list), do: replace(t, indices, i+1, [val|list]) |
|||
end |
|||
values = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
indices = [6, 1, 7] |
|||
IO.inspect Sort_disjoint.sublist(values, indices)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
-module( sort_disjoint ). |
-module( sort_disjoint ). |
||
Line 352: | Line 1,853: | ||
merge( Index, {[_H | Values], [{Index, Value} | Sorted_indices_values]} ) -> {Value, {Values, Sorted_indices_values}}; |
merge( Index, {[_H | Values], [{Index, Value} | Sorted_indices_values]} ) -> {Value, {Values, Sorted_indices_values}}; |
||
merge( _Index, {[H | Values], Sorted_indices_values} ) -> {H, {Values, Sorted_indices_values}}. |
merge( _Index, {[H | Values], Sorted_indices_values} ) -> {H, {Values, Sorted_indices_values}}. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>20> sort_disjoint:task(). |
|||
<pre> |
|||
[7,0,5,4,3,2,1,6]</pre> |
|||
20> sort_disjoint:task(). |
|||
[7,0,5,4,3,2,1,6] |
|||
=={{header|ERRE}}== |
|||
</pre> |
|||
<syntaxhighlight lang="erre">PROGRAM DISJOINT |
|||
DIM LST%[7],INDICES%[2] |
|||
DIM L%[7],I%[2],Z%[2] |
|||
PROCEDURE SHOWLIST(L%[]->O$) |
|||
LOCAL I% |
|||
O$="[" |
|||
FOR I%=0 TO UBOUND(L%,1) DO |
|||
O$=O$+STR$(L%[I%])+", " |
|||
END FOR |
|||
O$=LEFT$(O$,LEN(O$)-2)+"]" |
|||
END PROCEDURE |
|||
PROCEDURE SORT(Z%[]->Z%[]) |
|||
LOCAL N%,P%,FLIPS% |
|||
P%=UBOUND(Z%,1) |
|||
FLIPS%=TRUE |
|||
WHILE FLIPS% DO |
|||
FLIPS%=FALSE |
|||
FOR N%=0 TO P%-1 DO |
|||
IF Z%[N%]>Z%[N%+1] THEN SWAP(Z%[N%],Z%[N%+1]) FLIPS%=TRUE |
|||
END FOR |
|||
END WHILE |
|||
END PROCEDURE |
|||
PROCEDURE SortDisJoint(L%[],I%[]->L%[]) |
|||
LOCAL J%,N% |
|||
LOCAL DIM T%[2] |
|||
N%=UBOUND(I%,1) |
|||
FOR J%=0 TO N% DO |
|||
T%[J%]=L%[I%[J%]] |
|||
END FOR |
|||
SORT(I%[]->I%[]) |
|||
SORT(T%[]->T%[]) |
|||
FOR J%=0 TO N% DO |
|||
L%[I%[J%]]=T%[J%] |
|||
END FOR |
|||
END PROCEDURE |
|||
BEGIN |
|||
LST%[]=(7,6,5,4,3,2,1,0) |
|||
INDICES%[]=(6,1,7) |
|||
SortDisJoint(LST%[],INDICES%[]->LST%[]) |
|||
ShowList(LST%[]->O$) |
|||
PRINT(O$) |
|||
END PROGRAM</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
< |
<syntaxhighlight lang="euphoria">include sort.e |
||
function uniq(sequence s) |
function uniq(sequence s) |
||
Line 388: | Line 1,939: | ||
constant data = {7, 6, 5, 4, 3, 2, 1, 0} |
constant data = {7, 6, 5, 4, 3, 2, 1, 0} |
||
constant indexes = {7, 2, 8}</ |
constant indexes = {7, 2, 8}</syntaxhighlight> |
||
{{out}} |
|||
pre>{7,0,5,4,3,2,1,6}</pre> |
|||
Output: |
|||
<pre>{7,0,5,4,3,2,1,6} |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
Works with arrays instead of lists because this algorithm is more efficient with a random access collection type. Returns a copy of the array, as is usually preferred in F#. |
Works with arrays instead of lists because this algorithm is more efficient with a random access collection type. Returns a copy of the array, as is usually preferred in F#. |
||
< |
<syntaxhighlight lang="fsharp">let sortDisjointSubarray data indices = |
||
let indices = Set.toArray indices // creates a sorted array |
let indices = Set.toArray indices // creates a sorted array |
||
let result = Array.copy data |
let result = Array.copy data |
||
Line 406: | Line 1,955: | ||
printfn "%A" (sortDisjointSubarray [|7;6;5;4;3;2;1;0|] (set [6;1;7]))</ |
printfn "%A" (sortDisjointSubarray [|7;6;5;4;3;2;1;0|] (set [6;1;7]))</syntaxhighlight> |
||
=={{header|Factor}}== |
|||
<syntaxhighlight lang="factor">: disjoint-sort! ( values indices -- values' ) |
|||
over <enumerated> nths unzip swap [ natural-sort ] bi@ |
|||
pick [ set-nth ] curry 2each ;</syntaxhighlight> |
|||
{{out}} |
|||
<syntaxhighlight lang="factor">IN: scratchpad { 7 6 5 4 3 2 1 0 } { 6 1 7 } disjoint-sort! . |
|||
{ 7 0 5 4 3 2 1 6 }</syntaxhighlight> |
|||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
< |
<syntaxhighlight lang="fortran">program Example |
||
implicit none |
implicit none |
||
Line 445: | Line 2,002: | ||
end subroutine Isort |
end subroutine Isort |
||
end program Example</ |
end program Example</syntaxhighlight> |
||
{{out}} |
|||
Output |
|||
<pre> 7 0 5 4 3 2 1 6</pre> |
<pre> 7 0 5 4 3 2 1 6</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 486: | Line 2,043: | ||
} |
} |
||
fmt.Println("sorted: ", values) |
fmt.Println("sorted: ", values) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre>initial: [7 6 5 4 3 2 1 0] |
|||
<pre> |
|||
sorted: [7 0 5 4 3 2 1 6]</pre> |
|||
sorted: [7 0 5 4 3 2 1 6] |
|||
</pre> |
|||
Alternative algorithm, sorting in place through the extra level of indirection. |
Alternative algorithm, sorting in place through the extra level of indirection. |
||
Compared to the strategy of extract-sort-replace, this strategy avoids the space overhead of the work area and the time overhead of extracting and reinserting elements. At some point however, the cost of indirection multiplied by O(log n) would dominate, and extract-sort-replace would become preferable. |
Compared to the strategy of extract-sort-replace, this strategy avoids the space overhead of the work area and the time overhead of extracting and reinserting elements. At some point however, the cost of indirection multiplied by O(log n) would dominate, and extract-sort-replace would become preferable. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 551: | Line 2,106: | ||
sort.Sort(s) |
sort.Sort(s) |
||
fmt.Println("sorted: ", s.values) |
fmt.Println("sorted: ", s.values) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Groovy allows List-valued indexing to "gather" and "scatter" arbitrary sublists, making the solution almost trivial. |
Groovy allows List-valued indexing to "gather" and "scatter" arbitrary sublists, making the solution almost trivial. |
||
< |
<syntaxhighlight lang="groovy">def sparseSort = { a, indices = ([] + (0..<(a.size()))) -> |
||
indices.sort().unique() |
indices.sort().unique() |
||
a[indices] = a[indices].sort() |
a[indices] = a[indices].sort() |
||
a |
a |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">def a = [7, 6, 5, 4, 3, 2, 1, 0] |
||
println a |
println a |
||
Line 570: | Line 2,125: | ||
println a |
println a |
||
println sparseSort(a) // default == sort all |
println sparseSort(a) // default == sort all |
||
println a</ |
println a</syntaxhighlight> |
||
Output: |
Output: |
||
Line 584: | Line 2,139: | ||
Here are three variations on the solution: using ordinary lists, immutable "boxed" arrays, and mutable "unboxed" arrays. |
Here are three variations on the solution: using ordinary lists, immutable "boxed" arrays, and mutable "unboxed" arrays. |
||
<syntaxhighlight lang="haskell">import Control.Monad |
|||
<lang haskell> |
|||
import Control.Monad |
|||
import qualified Data.Array as A |
import qualified Data.Array as A |
||
import Data.Array.IArray |
import Data.Array.IArray |
||
Line 593: | Line 2,147: | ||
-- Partition 'xs' according to whether their element indices are in 'is'. Sort |
-- Partition 'xs' according to whether their element indices are in 'is'. Sort |
||
-- the sublist corresponding to 'is', merging the result with the remainder of |
-- the sublist corresponding to 'is', merging the result with the remainder of |
||
-- the list. |
-- the list. |
||
disSort1 |
|||
disSort1 :: (Ord a, Num a, Enum a, Ord b) => [b] -> [a] -> [b] |
|||
:: (Ord a, Num a, Enum a, Ord b) |
|||
disSort1 xs is = let is' = sort is |
|||
=> [b] -> [a] -> [b] |
|||
(sub, rest) = partition ((`elem` is') . fst) $ zip [0..] xs |
|||
disSort1 xs is = |
|||
in map snd . merge rest . zip is' . sort $ map snd sub |
|||
let is_ = sort is |
|||
(sub, rest) = partition ((`elem` is_) . fst) $ zip [0 ..] xs |
|||
in map snd . merge rest . zip is_ . sort $ map snd sub |
|||
-- Convert the list to an array. Extract the sublist corresponding to the |
-- Convert the list to an array. Extract the sublist corresponding to the |
||
-- indices 'is'. Sort the sublist, replacing those elments in the array. |
-- indices 'is'. Sort the sublist, replacing those elments in the array. |
||
disSort2 |
|||
disSort2 :: (Ord a) => [a] -> [Int] -> [a] |
|||
:: (Ord a) |
|||
disSort2 xs is = let as = A.listArray (0, length xs - 1) xs |
|||
=> [a] -> [Int] -> [a] |
|||
sub = zip (sort is) . sort $ map (as !) is |
|||
disSort2 xs is = |
|||
in elems $ as // sub |
|||
let as = A.listArray (0, length xs - 1) xs |
|||
sub = zip (sort is) . sort $ map (as !) is |
|||
in elems $ as // sub |
|||
-- Similar to disSort2, but using mutable arrays. The sublist is updated |
-- Similar to disSort2, but using mutable arrays. The sublist is updated |
||
Line 611: | Line 2,171: | ||
-- to a caller. |
-- to a caller. |
||
disSort3 :: [Int] -> [Int] -> [Int] |
disSort3 :: [Int] -> [Int] -> [Int] |
||
disSort3 xs is = |
disSort3 xs is = |
||
elems . runSTUArray $ |
|||
as <- newListArray (0, length xs - 1) xs |
|||
do as <- newListArray (0, length xs - 1) xs |
|||
sub <- liftM (zip (sort is) . sort) $ mapM (readArray as) is |
|||
sub <- (zip (sort is) . sort) Control.Applicative.<$> mapM (readArray as) is |
|||
mapM_ (uncurry (writeArray as)) sub |
|||
mapM_ (uncurry (writeArray as)) sub |
|||
return as |
|||
return as |
|||
main :: IO () |
|||
main = do |
main = do |
||
let xs = [7, 6, 5, 4, 3, 2, 1, 0] |
let xs = [7, 6, 5, 4, 3, 2, 1, 0] |
||
Line 622: | Line 2,184: | ||
print $ disSort1 xs is |
print $ disSort1 xs is |
||
print $ disSort2 xs is |
print $ disSort2 xs is |
||
print $ disSort3 xs is |
print $ disSort3 xs is</syntaxhighlight> |
||
</lang> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
|||
Or, in terms of Data.Map: |
|||
<syntaxhighlight lang="haskell">import Data.Map as M (fromList, keys, lookup) |
|||
import Control.Applicative ((<|>)) |
|||
import Data.Maybe (mapMaybe) |
|||
import Data.List (sort) |
|||
disjointSort :: [Int] -> [Int] -> [Int] |
|||
disjointSort ixs xs = |
|||
let ks = sort ixs |
|||
dctAll = fromList $ zip xs [0 ..] |
|||
dctIx = fromList $ zip ks $ sort (mapMaybe (`M.lookup` dctAll) ks) |
|||
in mapMaybe |
|||
((<|>) <$> (`M.lookup` dctIx) <*> (`M.lookup` dctAll)) |
|||
(keys dctAll) |
|||
main :: IO () |
|||
main = print $ disjointSort [6, 1, 7] [7, 6, 5, 4, 3, 2, 1, 0]</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[7,0,5,4,3,2,1,6]</pre> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
|||
Icon's lists are 1-based, so the example uses (7, 2, 8) as the indices, not (6, 1 7). |
Icon's lists are 1-based, so the example uses (7, 2, 8) as the indices, not (6, 1 7). |
||
<syntaxhighlight lang="icon">link sort # get the 'isort' procedure for sorting a list |
|||
<lang icon> |
|||
link sort # get the 'isort' procedure for sorting a list |
|||
procedure sortDisjoint (items, indices) |
procedure sortDisjoint (items, indices) |
||
Line 654: | Line 2,234: | ||
every writes (!result || " ") |
every writes (!result || " ") |
||
write () |
write () |
||
end</syntaxhighlight> |
|||
end |
|||
{{out}}<pre>7 6 5 4 3 2 1 0 |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
7 6 5 4 3 2 1 0 |
|||
2 7 8 |
2 7 8 |
||
7 0 5 4 3 2 1 6 |
7 0 5 4 3 2 1 6</pre> |
||
</pre> |
|||
The expression <code>!indices</code> generates the value of each index in turn, so the line <syntaxhighlight lang="icon">every put (values, result[!indices])</syntaxhighlight> effectively loops through each index, putting <code>result[index]</code> into the list 'values'. |
|||
=={{header|Io}}== |
|||
Io does not come with a set type. |
|||
<syntaxhighlight lang="io">List disjointSort := method(indices, |
|||
sortedIndices := indices unique sortInPlace |
|||
sortedValues := sortedIndices map(idx,at(idx)) sortInPlace |
|||
sortedValues foreach(i,v,atPut(sortedIndices at(i),v)) |
|||
self |
|||
) |
|||
list(7,6,5,4,3,2,1,0) disjointSort(list(6,1,7)) println</syntaxhighlight> |
|||
The expression <code>!indices</code> generates the value of each index in turn, so the line <lang icon>every put (values, result[!indices])</lang> effectively loops through each index, putting <code>result[index]</code> into the list 'values'. |
|||
{{output}} |
|||
<pre>list(7, 0, 5, 4, 3, 2, 1, 6)</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Note that the task requires us to ignore the order of the indices. |
Note that the task requires us to ignore the order of the indices. |
||
< |
<syntaxhighlight lang="j"> 7 6 5 4 3 2 1 0 (/:~@:{`[`]}~ /:~@~.) 6 1 7 |
||
7 0 5 4 3 2 1 6</ |
7 0 5 4 3 2 1 6</syntaxhighlight> |
||
Compare this with: |
Compare this with: |
||
< |
<syntaxhighlight lang="j"> 6 1 7 /:~@:{`[`]} 7 6 5 4 3 2 1 0 |
||
7 1 5 4 3 2 0 6</ |
7 1 5 4 3 2 0 6</syntaxhighlight> |
||
Here, the order of the indices specifies the order we want the selected items to be sorted in: 7 '''''1''''' 5 4 3 2 '''''0 6''''' |
Here, the order of the indices specifies the order we want the selected items to be sorted in: 7 '''''1''''' 5 4 3 2 '''''0 6''''' |
||
Line 681: | Line 2,269: | ||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
This function will modify the index array and the values list. |
This function will modify the index array and the values list. |
||
< |
<syntaxhighlight lang="java5">import java.util.ArrayList; |
||
import java.util.Arrays; |
import java.util.Arrays; |
||
import java.util.Collections; |
import java.util.Collections; |
||
Line 708: | Line 2,296: | ||
System.out.println(list); |
System.out.println(list); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[7, 6, 5, 4, 3, 2, 1, 0] |
<pre>[7, 6, 5, 4, 3, 2, 1, 0] |
||
Line 716: | Line 2,304: | ||
{{trans|Go}} |
{{trans|Go}} |
||
Shorter solution that sorts a list "wrapper" which represents a "view" into the disjoint sublist of the list. |
Shorter solution that sorts a list "wrapper" which represents a "view" into the disjoint sublist of the list. |
||
< |
<syntaxhighlight lang="java5">import java.util.Arrays; |
||
import java.util.Collections; |
import java.util.Collections; |
||
import java.util.List; |
import java.util.List; |
||
Line 739: | Line 2,327: | ||
System.out.println(list); |
System.out.println(list); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[7, 6, 5, 4, 3, 2, 1, 0] |
<pre>[7, 6, 5, 4, 3, 2, 1, 0] |
||
Line 745: | Line 2,333: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
===ES5=== |
|||
====Iterative==== |
|||
Does not check for duplicate indices. |
Does not check for duplicate indices. |
||
< |
<syntaxhighlight lang="javascript">function sort_disjoint(values, indices) { |
||
var sublist = []; |
var sublist = []; |
||
indices.sort(function(a, b) { return a > b; }); |
indices.sort(function(a, b) { return a > b; }); |
||
Line 761: | Line 2,351: | ||
return values; |
return values; |
||
}</ |
}</syntaxhighlight> |
||
====Functional==== |
|||
<syntaxhighlight lang="javascript">(function () { |
|||
'use strict'; |
|||
// disjointSort :: [a] -> [Int] -> [a] |
|||
function disjointSort(xs, indices) { |
|||
// Sequence of indices discarded |
|||
var indicesSorted = indices.sort(), |
|||
subsetSorted = indicesSorted |
|||
.map(function (i) { |
|||
return xs[i]; |
|||
}) |
|||
.sort(); |
|||
return xs |
|||
.map(function (x, i) { |
|||
var iIndex = indicesSorted.indexOf(i); |
|||
return iIndex !== -1 ? ( |
|||
subsetSorted[iIndex] |
|||
) : x; |
|||
}); |
|||
} |
|||
return disjointSort([7, 6, 5, 4, 3, 2, 1, 0], [6, 1, 7]) |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
===ES6=== |
|||
<syntaxhighlight lang="javascript">(() => { |
|||
'use strict'; |
|||
// disjointSort :: [Int] -> [Int] -> [Int] |
|||
const disjointSort = (indices, xs) => { |
|||
const |
|||
ks = sort(indices), |
|||
dct = mapFromList( |
|||
zip(ks, sort(map(k => xs[k], ks))) |
|||
); |
|||
return map( |
|||
(x, i) => { |
|||
const v = dct[i.toString()]; |
|||
return undefined !== v ? v : x; |
|||
}, |
|||
xs |
|||
); |
|||
}; |
|||
// main :: IO () |
|||
const main = () => |
|||
showLog( |
|||
disjointSort( |
|||
[6, 1, 7], |
|||
[7, 6, 5, 4, 3, 2, 1, 0] |
|||
) |
|||
); |
|||
// GENERIC FUNCTIONS ---------------------------- |
|||
// length :: [a] -> Int |
|||
const length = xs => xs.length || Infinity; |
|||
// map :: (a -> b) -> [a] -> [b] |
|||
const map = (f, xs) => xs.map(f); |
|||
// mapFromList :: [(k, v)] -> Dict |
|||
const mapFromList = kvs => |
|||
kvs.reduce( |
|||
(a, kv) => { |
|||
const k = kv[0]; |
|||
return Object.assign(a, { |
|||
[(('string' === typeof k) && k) || showJSON(k)]: kv[1] |
|||
}); |
|||
}, {} |
|||
); |
|||
// showJSON :: a -> String |
|||
const showJSON = x => JSON.stringify(x); |
|||
// showLog :: a -> IO () |
|||
const showLog = (...args) => |
|||
console.log( |
|||
args |
|||
.map(JSON.stringify) |
|||
.join(' -> ') |
|||
); |
|||
// sort :: Ord a => [a] -> [a] |
|||
const sort = xs => xs.slice() |
|||
.sort((a, b) => a < b ? -1 : (a > b ? 1 : 0)); |
|||
// take :: Int -> [a] -> [a] |
|||
// take :: Int -> String -> String |
|||
const take = (n, xs) => |
|||
xs.constructor.constructor.name !== 'GeneratorFunction' ? ( |
|||
xs.slice(0, n) |
|||
) : [].concat.apply([], Array.from({ |
|||
length: n |
|||
}, () => { |
|||
const x = xs.next(); |
|||
return x.done ? [] : [x.value]; |
|||
})); |
|||
// Tuple (,) :: a -> b -> (a, b) |
|||
const Tuple = (a, b) => ({ |
|||
type: 'Tuple', |
|||
'0': a, |
|||
'1': b, |
|||
length: 2 |
|||
}); |
|||
// Use of `take` and `length` here allows for zipping with non-finite |
|||
// lists - i.e. generators like cycle, repeat, iterate. |
|||
// zip :: [a] -> [b] -> [(a, b)] |
|||
const zip = (xs, ys) => { |
|||
const lng = Math.min(length(xs), length(ys)); |
|||
return Infinity !== lng ? (() => { |
|||
const bs = take(lng, ys); |
|||
return take(lng, xs).map((x, i) => Tuple(x, bs[i])); |
|||
})() : zipGen(xs, ys); |
|||
}; |
|||
// MAIN --- |
|||
return main(); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|jq}}== |
|||
We define a jq function, disjointSort, that accepts the array of values as input, |
|||
but for clarity we first define a utility function for updating an array at multiple places: |
|||
<syntaxhighlight lang="jq">def setpaths(indices; values): |
|||
reduce range(0; indices|length) as $i |
|||
(.; .[indices[$i]] = values[$i]); |
|||
def disjointSort(indices): |
|||
(indices|unique) as $ix # "unique" sorts |
|||
# Set $sorted to the sorted array of values at $ix: |
|||
| ([ .[ $ix[] ] ] | sort) as $sorted |
|||
| setpaths( $ix; $sorted) ;</syntaxhighlight> |
|||
Example:<syntaxhighlight lang="jq"> |
|||
[7, 6, 5, 4, 3, 2, 1, 0] | disjointSort( [6, 1, 7] )</syntaxhighlight>produces: |
|||
[7,0,5,4,3,2,1,6] |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
<syntaxhighlight lang="julia">function sortselected(a::AbstractVector{<:Real}, s::AbstractVector{<:Integer}) |
|||
sel = unique(sort(s)) |
|||
if sel[1] < 1 || length(a) < sel[end] |
|||
throw(BoundsError()) |
|||
end |
|||
b = collect(copy(a)) |
|||
b[sel] = sort(b[sel]) |
|||
return b |
|||
end |
|||
a = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
sel = [7, 2, 8] |
|||
b = sortselected(a, sel) |
|||
println("Original: $a\n\tsorted on $sel\n -> sorted array: $b")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Original: [7, 6, 5, 4, 3, 2, 1, 0] |
|||
sorted on [7, 2, 8] |
|||
-> sorted array: [7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|K}}== |
=={{header|K}}== |
||
<syntaxhighlight lang="k"> |
|||
<lang K> |
|||
{@[x;y@<y;:;a@<a:x@y]}[7 6 5 4 3 2 1 0;6 1 7] |
{@[x;y@<y;:;a@<a:x@y]}[7 6 5 4 3 2 1 0;6 1 7] |
||
7 0 5 4 3 2 1 6 |
7 0 5 4 3 2 1 6 |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Another way=== |
|||
<syntaxhighlight lang="k">sort : {x[<x]} |
|||
nums : 7 6 5 4 3 2 1 0 |
|||
i : sort 6 1 7 |
|||
nums[i] : sort nums[i] |
|||
nums |
|||
7 0 5 4 3 2 1 6</syntaxhighlight> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.1.51 |
|||
/* in place sort */ |
|||
fun IntArray.sortDisjoint(indices: Set<Int>) { |
|||
val sortedSubset = this.filterIndexed { index, _ -> index in indices }.sorted() |
|||
if (sortedSubset.size < indices.size) |
|||
throw IllegalArgumentException("Argument set contains out of range indices") |
|||
indices.sorted().forEachIndexed { index, value -> this[value] = sortedSubset[index] } |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val values = intArrayOf(7, 6, 5, 4, 3, 2, 1, 0) |
|||
val indices = setOf(6, 1, 7) |
|||
println("Original array : ${values.asList()} sorted on indices $indices") |
|||
values.sortDisjoint(indices) |
|||
println("Sorted array : ${values.asList()}") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Original array : [7, 6, 5, 4, 3, 2, 1, 0] sorted on indices [6, 1, 7] |
|||
Sorted array : [7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Ksh}}== |
|||
<syntaxhighlight lang="ksh"> |
|||
#!/bin/ksh |
|||
# Sort disjoint sublist |
|||
# # Variables: |
|||
# |
|||
typeset -a arr_Val=( 7 6 5 4 3 2 1 0 ) |
|||
typeset -a arr_Ind=( 6 1 7 ) |
|||
integer i |
|||
# # Functions: |
|||
# |
|||
# # Function _insertionSort(array) - Insertion sort of array of integers |
|||
# |
|||
function _insertionSort { |
|||
typeset _arr ; nameref _arr="$1" |
|||
typeset _i _j _val ; integer _i _j _val |
|||
for (( _i=1; _i<${#_arr[*]}; _i++ )); do |
|||
_val=${_arr[_i]} |
|||
(( _j = _i - 1 )) |
|||
while (( _j>=0 && _arr[_j]>_val )); do |
|||
_arr[_j+1]=${_arr[_j]} |
|||
(( _j-- )) |
|||
done |
|||
_arr[_j+1]=${_val} |
|||
done |
|||
} |
|||
###### |
|||
# main # |
|||
###### |
|||
print "Before sort: ${arr_Val[*]}" |
|||
typeset -a arr_2sort |
|||
for ((i=0; i<${#arr_Ind[*]}; i++)); do |
|||
arr_2sort+=( ${arr_Val[${arr_Ind[i]}]} ) |
|||
done |
|||
_insertionSort arr_2sort # Sort the chosen values |
|||
_insertionSort arr_Ind # Sort the indices |
|||
for ((i=0; i<${#arr_Ind[*]}; i++)); do |
|||
arr_Val[${arr_Ind[i]}]=${arr_2sort[i]} |
|||
done |
|||
print "After sort: ${arr_Val[*]}"</syntaxhighlight> |
|||
{{out}}<pre> |
|||
Before sort: 7 6 5 4 3 2 1 0 |
|||
After sort: 7 0 5 4 3 2 1 6</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">values = { 7, 6, 5, 4, 3, 2, 1, 0 } |
||
indices = { 6, 1, 7 } |
indices = { 6, 1, 7 } |
||
Line 802: | Line 2,647: | ||
for i = 1, #values do |
for i = 1, #values do |
||
io.write( values[i], " " ) |
io.write( values[i], " " ) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
|||
<pre>7 0 5 4 3 2 1 6</pre> |
<pre>7 0 5 4 3 2 1 6</pre> |
||
=={{header| |
=={{header|Maple}}== |
||
<syntaxhighlight lang="maple">sortDisjoint := proc(values, indices::set) |
|||
<lang Mathematica>Values = { 7, 6, 5, 4, 3, 2, 1, 0} ; Indices = { 7, 2, 8 }; |
|||
local vals,inds,i: |
|||
vals := sort([seq(values[i], i in indices)]): |
|||
inds := sort(convert(indices, Array)): |
|||
for i to numelems(vals) do |
|||
values(inds[i]) := vals[i]: |
|||
od: |
|||
end proc: |
|||
tst := Array([7,6,5,4,3,2,1,0]): |
|||
sortDisjoint(tst,{7,2,8});</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7 0 5 4 3 2 1 6]</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">Values = { 7, 6, 5, 4, 3, 2, 1, 0} ; Indices = { 7, 2, 8 }; |
|||
Values[[Sort[Indices]]] = Sort[Values[[Indices]]]; |
Values[[Sort[Indices]]] = Sort[Values[[Indices]]]; |
||
Values</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{ 7, 0, 5, 4, 3, 2, 1, 6 }</pre> |
|||
=={{header|MiniScript}}== |
|||
Values |
|||
<syntaxhighlight lang="miniscript"> |
|||
-> { 7, 0, 5, 4, 3, 2, 1, 6 }</lang> |
|||
sortDisjointSublist = function(arr, indexes) |
|||
indexes.sort |
|||
newArr = arr[:] |
|||
sublist = [] |
|||
for i in indexes |
|||
sublist.push(arr[i]) |
|||
end for |
|||
sublist.sort |
|||
for i in range(0, indexes.len - 1) |
|||
arrIx = indexes[i] |
|||
newArr[arrIx] = sublist[i] |
|||
end for |
|||
return newArr |
|||
end function |
|||
print sortDisjointSublist([7,6,5,4,3,2,1,0], [6,1,7]) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[7, 0, 5, 4, 3, 2, 1, 6] |
|||
</pre> |
|||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 856: | Line 2,740: | ||
say 'Idx:' iList.space |
say 'Idx:' iList.space |
||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>In: 7 6 5 4 3 2 1 0 |
|||
<pre> |
|||
In: 7 6 5 4 3 2 1 0 |
|||
Out: 7 0 5 4 3 2 1 6 |
Out: 7 0 5 4 3 2 1 6 |
||
Idx: 7 2 8 |
Idx: 7 2 8</pre> |
||
</pre> |
|||
=={{header|Nial}}== |
|||
{{works with|Q'Nial Version 6.3}} |
|||
<syntaxhighlight lang="nial"> |
|||
values := [7, 6, 5, 4, 3, 2, 1, 0] |
|||
indices := sortup [6, 1, 7] |
|||
values#indices := sortup values#indices |
|||
7 0 5 4 3 2 1 6 |
|||
</syntaxhighlight> |
|||
=={{header| |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import algorithm |
||
proc sortDisjoinSublist[T](data: var seq[T], indices: seq[int]) = |
proc sortDisjoinSublist[T](data: var seq[T], indices: seq[int]) = |
||
Line 879: | Line 2,770: | ||
var d = @[7, 6, 5, 4, 3, 2, 1, 0] |
var d = @[7, 6, 5, 4, 3, 2, 1, 0] |
||
sortDisjoinSublist(d, @[6, 1, 7]) |
sortDisjoinSublist(d, @[6, 1, 7]) |
||
echo d</ |
echo d</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre>@[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
<pre>@[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
||
Line 886: | Line 2,777: | ||
{{trans|Go}} |
{{trans|Go}} |
||
Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array. |
Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array. |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
@interface DisjointSublistView : NSMutableArray { |
@interface DisjointSublistView : NSMutableArray { |
||
Line 936: | Line 2,827: | ||
} |
} |
||
return 0; |
return 0; |
||
}</syntaxhighlight> |
|||
} |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>( |
<pre>( |
||
Line 951: | Line 2,841: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
===With arrays:=== |
|||
<syntaxhighlight lang="ocaml">let disjoint_sort cmp values indices = |
|||
With arrays: |
|||
<lang ocaml>let disjoint_sort cmp values indices = |
|||
let temp = Array.map (Array.get values) indices in |
let temp = Array.map (Array.get values) indices in |
||
Array.sort cmp temp; |
Array.sort cmp temp; |
||
Line 965: | Line 2,853: | ||
disjoint_sort compare values indices; |
disjoint_sort compare values indices; |
||
Array.iter (Printf.printf " %d") values; |
Array.iter (Printf.printf " %d") values; |
||
print_newline()</ |
print_newline()</syntaxhighlight> |
||
With lists: |
===With lists:=== |
||
<syntaxhighlight lang="ocaml">let disjoint_sort cmp values indices = |
|||
<lang ocaml>let disjoint_sort cmp values indices = |
|||
let indices = List.sort compare indices in |
let indices = List.sort compare indices in |
||
let rec aux acc j = function |
let rec aux acc j = function |
||
Line 999: | Line 2,886: | ||
let res = disjoint_sort compare values indices in |
let res = disjoint_sort compare values indices in |
||
List.iter (Printf.printf " %d") res; |
List.iter (Printf.printf " %d") res; |
||
print_newline()</ |
print_newline()</syntaxhighlight> |
||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
<syntaxhighlight lang="oorexx">data = .array~of(7, 6, 5, 4, 3, 2, 1, 0) |
|||
<lang ooRexx> |
|||
data = .array~of(7, 6, 5, 4, 3, 2, 1, 0) |
|||
-- this could be a list, array, or queue as well because of polymorphism |
-- this could be a list, array, or queue as well because of polymorphism |
||
-- also, ooRexx arrays are 1-based, so using the alternate index set for the |
-- also, ooRexx arrays are 1-based, so using the alternate index set for the |
||
Line 1,039: | Line 2,925: | ||
-- the two and returning the sign, we give the expected |
-- the two and returning the sign, we give the expected |
||
-- results for the compares |
-- results for the compares |
||
return (left - right)~sign |
return (left - right)~sign</syntaxhighlight> |
||
{{out}} |
|||
</lang> |
|||
<pre>Sorted data is: [7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Order}}== |
=={{header|Order}}== |
||
< |
<syntaxhighlight lang="c">#include <order/interpreter.h> |
||
#define ORDER_PP_DEF_8sort_disjoint_sublist ORDER_PP_FN( \ |
#define ORDER_PP_DEF_8sort_disjoint_sublist ORDER_PP_FN( \ |
||
Line 1,061: | Line 2,948: | ||
ORDER_PP( |
ORDER_PP( |
||
8sort_disjoint_sublist(8seq(7, 6, 5, 4, 3, 2, 1, 0), 8tuple(6, 1, 7)) |
8sort_disjoint_sublist(8seq(7, 6, 5, 4, 3, 2, 1, 0), 8tuple(6, 1, 7)) |
||
)</ |
)</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">sortsome(v,which)={ |
||
my(x=sum(i=1,#which,1<<(which[i]-1)),u=vecextract(v,x)); |
my(x=sum(i=1,#which,1<<(which[i]-1)),u=vecextract(v,x)); |
||
u=vecsort(u); |
u=vecsort(u); |
||
Line 1,070: | Line 2,957: | ||
for(i=1,#which,v[which[i]]=u[i]); |
for(i=1,#which,v[which[i]]=u[i]); |
||
v |
v |
||
};</ |
};</syntaxhighlight> |
||
=={{header|pascal}}== |
|||
Tested free pascal. |
|||
<syntaxhighlight lang="pascal"> |
|||
program disjointsort; |
|||
procedure swap(var a, b: Integer); |
|||
var |
|||
temp: Integer; |
|||
begin |
|||
temp := a; |
|||
a := b; |
|||
b := temp; |
|||
end; |
|||
procedure d_sort(var index,arr:array of integer); |
|||
var |
|||
n,i,j,num:integer; |
|||
begin |
|||
num:=length(index); |
|||
for n:=1 to 2 do |
|||
begin |
|||
for i:=0 to num-1 do |
|||
begin |
|||
for j:=i+1 to num-1 do |
|||
begin |
|||
if n=1 then if index[j]<index[i] then swap(index[j],index[i]); |
|||
if n=2 then if arr[index[j]]<arr[index[i]] then swap(arr[index[j]],arr[index[i]]); |
|||
end; |
|||
end; |
|||
end; |
|||
end; |
|||
var |
|||
i:integer; |
|||
arr :array[0 .. 7] of integer =(7, 6, 5, 4, 3, 2, 1, 0); |
|||
index:array[0 .. 2] of integer =(6, 1, 7); |
|||
begin |
|||
writeln('Before'); |
|||
for i:=0 to 7 do write(arr[i],' '); |
|||
writeln; |
|||
d_sort(index,arr); |
|||
writeln('After'); |
|||
for i:=0 to 7 do write(arr[i],' '); |
|||
writeln; |
|||
readln; |
|||
end. |
|||
</syntaxhighlight> |
|||
<pre>Before |
|||
7 6 5 4 3 2 1 0 |
|||
After |
|||
7 0 5 4 3 2 1 6</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl -w |
||
use strict ; |
use strict ; |
||
Line 1,086: | Line 3,028: | ||
my @indices = ( 6 , 1 , 7 ) ; |
my @indices = ( 6 , 1 , 7 ) ; |
||
disjointSort( \@values , @indices ) ; |
disjointSort( \@values , @indices ) ; |
||
print "[@values]\n" ;</ |
print "[@values]\n" ;</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre>[7 0 5 4 3 2 1 6]</pre> |
<pre>[7 0 5 4 3 2 1 6]</pre> |
||
=={{header| |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
===Inline=== |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
Using L-value slice of the array, and `sort` as a mutating method: |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span> |
|||
<lang perl6>my @values = 7, 6, 5, 4, 3, 2, 1, 0; |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span> |
|||
my @indices = 6, 1, 7; |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">copies</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">copies</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">copies</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">copies</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">copies</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre>{7,0,5,4,3,2,1,6}</pre> |
|||
=== Shorter Alternative Version === |
|||
@values[ @indices.sort ] .= sort; |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
@values.perl.say;</lang> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span> |
|||
Output:<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unique</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">reinstate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">)))</span> |
|||
===Iterative=== |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<lang Perl 6>sub disjointSort( @values is rw , @indices is rw --> List ) { |
|||
my @sortedValues = @values[ @indices ].sort ; |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span> |
|||
for @indices.sort -> $insert { |
|||
<!--</syntaxhighlight>--> |
|||
@values[ $insert ] = @sortedValues.shift ; |
|||
{{out}} |
|||
} |
|||
<pre>same output.</pre> |
|||
return @values ; |
|||
} |
|||
my @values = ( 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ) ; |
|||
my @indices = ( 6 , 1 , 7 ) ; |
|||
my @sortedValues = disjointSort( @values , @indices ) ; |
|||
@sortedValues.perl.say ;</lang> |
|||
Output: |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
The indices are incremented here, as PicoLisp is 1-based |
The indices are incremented here, as PicoLisp is 1-based |
||
< |
<syntaxhighlight lang="picolisp">(let (Values (7 6 5 4 3 2 1 0) Indices (7 2 8)) |
||
(mapc |
(mapc |
||
'((V I) (set (nth Values I) V)) |
'((V I) (set (nth Values I) V)) |
||
(sort (mapcar '((N) (get Values N)) Indices)) |
(sort (mapcar '((N) (get Values N)) Indices)) |
||
(sort Indices) ) |
(sort Indices) ) |
||
Values )</ |
Values )</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre>-> (7 0 5 4 3 2 1 6)</pre> |
<pre>-> (7 0 5 4 3 2 1 6)</pre> |
||
=={{header| |
=={{header|Prolog}}== |
||
=== Using only predicates marked as "builtin" === |
|||
Based on the C implementation |
|||
<syntaxhighlight lang="prolog"> |
|||
<lang PureBasic>Procedure Bubble_sort(Array idx(1), n, Array buf(1)) |
|||
% === |
|||
Protected i, j |
|||
% Problem description |
|||
SortArray(idx(),#PB_Sort_Ascending) |
|||
% === |
|||
For i=0 To n |
|||
% http://rosettacode.org/wiki/Sort_disjoint_sublist |
|||
For j=i+1 To n |
|||
% |
|||
If buf(idx(j)) < buf(idx(i)) |
|||
% Given a list of values and a set of integer indices into that value list, |
|||
Swap buf(idx(j)), buf(idx(i)) |
|||
% the task is to sort the values at the given indices, while preserving the |
|||
EndIf |
|||
% values at indices outside the set of those to be sorted. |
|||
Next |
|||
% |
|||
Next |
|||
% Make your example work with the following list of values and set of indices: |
|||
EndProcedure |
|||
% |
|||
% Values: [7, 6, 5, 4, 3, 2, 1, 0] |
|||
% |
|||
% Indices: {6, 1, 7} |
|||
% |
|||
% Where the correct result would be: |
|||
% |
|||
% [7, 0, 5, 4, 3, 2, 1, 6]. |
|||
% |
|||
% In case of one-based indexing, rather than the zero-based indexing above, |
|||
% you would use the indices {7, 2, 8} instead. |
|||
% |
|||
% The indices are described as a set rather than a list but any collection-type |
|||
% of those indices without duplication may be used as long as the example is |
|||
% insensitive to the order of indices given. |
|||
Procedure main() |
|||
DataSection |
|||
values: Data.i 7, 6, 5, 4, 3, 2, 1, 0 |
|||
indices:Data.i 6, 1, 7 |
|||
EndDataSection |
|||
Dim values.i(7) :CopyMemory(?values, @values(), SizeOf(Integer)*8) |
|||
Dim indices.i(2):CopyMemory(?indices,@indices(),SizeOf(Integer)*3) |
|||
If OpenConsole() |
|||
Protected i |
|||
PrintN("Before sort:") |
|||
For i=0 To ArraySize(values()) |
|||
Print(Str(values(i))+" ") |
|||
Next |
|||
PrintN(#CRLF$+#CRLF$+"After sort:") |
|||
Bubble_sort(indices(), ArraySize(indices()), values()) |
|||
For i=0 To ArraySize(values()) |
|||
Print(Str(values(i))+" ") |
|||
Next |
|||
Print(#CRLF$+#CRLF$+"Press ENTER to exit") |
|||
Input() |
|||
EndIf |
|||
EndProcedure |
|||
% === |
|||
main()</lang> |
|||
% Notes |
|||
<pre>Before sort: |
|||
% === |
|||
7 6 5 4 3 2 1 0 |
|||
% For predicate descriptions, see https://www.swi-prolog.org/pldoc/man?section=preddesc |
|||
% |
|||
% Solution using only predicates marked "builtin". |
|||
% |
|||
% - sort/2 is a built-in predicate. When called as sort(A,B) then |
|||
% it sorts A to B according to the "standard order of terms", |
|||
% (for integers, this means ascending order). It does remove |
|||
% duplicates. |
|||
% - msort/2 is the same as sort/2 but does not remove duplicates. |
|||
% |
|||
% Everything is a list as there is no "set" datatype in Prolog. |
|||
After sort: |
|||
% === |
|||
7 0 5 4 3 2 1 6</pre> |
|||
% Main predicate (the one that would be exported from a Module) |
|||
% sort_disjoint_sublist(+Values,+Indexes,?ValuesSorted) |
|||
% === |
|||
sort_disjoint_sublist(Values,Indexes,ValuesSorted) :- |
|||
sort(Indexes,IndexesSorted), |
|||
insert_fresh_vars(0,IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened), |
|||
msort(ValsToSort,ValsSorted), % this is the "sorting of values" |
|||
% The next two lines could be left out with suitable naming, |
|||
% but they make explicit what happens: |
|||
FreshVars = ValsSorted, % fresh variables are unified with sorted variables |
|||
ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output |
|||
% === |
|||
% Helper predicate (would not be exported from a Module) |
|||
% === |
|||
% insert_fresh_vars(+CurIdx,+[I|Is],+[V|Vs],-FreshVars,-ValsToSort,-ValsFreshy) |
|||
% |
|||
% CurIdx: Monotonically increasing index into the list of values by |
|||
% which we iterate. |
|||
% [I|Is]: Sorted list of indexes of interest. The smallest (leftmost) |
|||
% element is removed on every "index hit", leaving eventually |
|||
% an empty list, which gives us the base case. |
|||
% [V|Vs]: The list of values of interest with the leftmost element the |
|||
% element with index CurIdx, all elements with lower index |
|||
% having been discarded. Leftmost element is popped off on |
|||
% each call. |
|||
% FreshVars: Constructed as output. If there was an "index hit", the |
|||
% fresh variable pushed on FreshVars is also pushed on Vars. |
|||
% ValsToSort: Constructed as output. If there was an "index hit", the |
|||
% leftmost value from [V|Vs] is pushed on. |
|||
% ValsFreshy: Constructed as output. If there was an "index hit", a fresh |
|||
% variable is pushed on. If there was no "index hit", the actual |
|||
% value from [V|Vs] is pushed on instead. |
|||
insert_fresh_vars(CurIdx,[I|Is],[V|Vs],FreshVars,ValsToSort,[V|ValsFreshy]) :- |
|||
CurIdx<I, % no index hit, CurIdx is still too small, iterate over value |
|||
!, |
|||
succ(CurIdx,NextIdx), |
|||
insert_fresh_vars(NextIdx,[I|Is],Vs,FreshVars,ValsToSort,ValsFreshy). |
|||
insert_fresh_vars(CurIdx,[I|Is],[V|Vs],[Fresh|FreshVars],[V|ValsToSort],[Fresh|ValsFreshy]) :- |
|||
CurIdx=I, % index hit, replace value by fresh variable |
|||
!, |
|||
succ(CurIdx,NextIdx), |
|||
insert_fresh_vars(NextIdx,Is,Vs,FreshVars,ValsToSort,ValsFreshy). |
|||
insert_fresh_vars(_,[],V,[],[],V). |
|||
</syntaxhighlight> |
|||
=== Alternatively, using predicates from <code>library(list)</code> === |
|||
Using <code>append/3</code> from SWi-Prolog's [https://eu.swi-prolog.org/pldoc/man?section=lists library(list)] |
|||
<syntaxhighlight lang="prolog"> |
|||
% === |
|||
% Main predicate |
|||
% === |
|||
sort_disjoint_sublist(Values,Indexes,ValuesSorted) :- |
|||
sort(Indexes,IndexesSorted), |
|||
insert_fresh_vars_by_splintering(IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened), |
|||
msort(ValsToSort,ValsSorted), % this is the "sorting of values" |
|||
% The next two lines could be left out with suitable naming, |
|||
% but they make explicit what happens: |
|||
FreshVars = ValsSorted, % fresh variables are unified with sorted variables |
|||
ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output |
|||
% === |
|||
% Helpers |
|||
% === |
|||
insert_fresh_vars_by_splintering([I|Is],Values,[Fresh|FreshVars],[ValAtI|ValsToSort],ValsFreshyFinal) :- |
|||
splinter(Values,I,ValAtI,ValsFront,ValsBack), % splinter Values --> ValsFront + ValAtI + ValsBack |
|||
append([ValsFront,[Fresh],ValsBack],ValsFreshyNext), % recompose ValsFront + Fresh + ValsBack --> ValuesFreshyNext |
|||
insert_fresh_vars_by_splintering(Is,ValsFreshyNext,FreshVars,ValsToSort,ValsFreshyFinal). |
|||
insert_fresh_vars_by_splintering([],V,[],[],V). |
|||
% "splinter" a list into a frontlist, the element at position N and a backlist |
|||
splinter(List, N, Elem, Front, Back) :- |
|||
length(Front, N), |
|||
append(Front, [Elem|Back], List). |
|||
</syntaxhighlight> |
|||
=== Unit Tests === |
|||
Test code using the [https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/plunit.html%27) Unit Testing framework of SWI Prolog]. |
|||
<syntaxhighlight lang="prolog"> |
|||
% We use the "R" intermediate var to decouple processing by the predicate |
|||
% from subsequent checking against expected result. |
|||
:- begin_tests(sort_disjoint_sublist). |
|||
test(rosetta) :- sort_disjoint_sublist([7,6,5,4,3,2,1,0],[6,1,7],R), R = [7,0,5,4,3,2,1,6]. |
|||
test(another1) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[3,4,5,6,7],R), R = [4,2,1,0,0,4,5,5]. |
|||
test(another2) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,1,2,3,4],R), R = [1,2,4,4,5,5,0,0]. |
|||
test(another3) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,2,4,6],R), R = [0,2,1,4,4,5,5,0]. |
|||
test(another4) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[1,3,5,7],R), R = [4,0,1,2,5,4,0,5]. |
|||
test(edge1) :- sort_disjoint_sublist([],[],R), R = []. |
|||
test(edge2) :- sort_disjoint_sublist([3,2,1],[],R), R = [3,2,1]. |
|||
test(edge3) :- sort_disjoint_sublist([3,2,1],[0],R), R = [3,2,1]. |
|||
test(edge4) :- sort_disjoint_sublist([3,2,1],[1],R), R = [3,2,1]. |
|||
test(edge5) :- sort_disjoint_sublist([3,2,1],[2],R), R = [3,2,1]. |
|||
test(x1) :- sort_disjoint_sublist([3,2,1],[0,1,2],R), R = [1,2,3]. |
|||
test(x2) :- sort_disjoint_sublist([1,2,3],[0,1,2],R), R = [1,2,3]. |
|||
test(dups1) :- sort_disjoint_sublist([3,2,1],[1,1,1],R), R = [3,2,1]. |
|||
test(dups2) :- sort_disjoint_sublist([3,2,1],[2,1,2],R), R = [3,1,2]. |
|||
test(fail1,[fail]) :- sort_disjoint_sublist([1,2],[0,1,2],_). |
|||
test(fail2,[fail]) :- sort_disjoint_sublist([],[0,1],_). |
|||
:- end_tests(sort_disjoint_sublist). |
|||
% --- |
|||
% Run unit tests. |
|||
% --- |
|||
rt :- run_tests(sort_disjoint_sublist). |
|||
</syntaxhighlight> |
|||
=={{header|PowerShell}}== |
|||
{{works with|PowerShell|4.0}} |
|||
<syntaxhighlight lang="powershell"> |
|||
function sublistsort($values, $indices) { |
|||
$indices = $indices | sort |
|||
$sub, $i = ($values[$indices] | sort), 0 |
|||
$indices | foreach { $values[$_] = $sub[$i++] } |
|||
$values |
|||
} |
|||
$values = 7, 6, 5, 4, 3, 2, 1, 0 |
|||
$indices = 6, 1, 7 |
|||
"$(sublistsort $values $indices)" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7 0 5 4 3 2 1 6</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
The function modifies the input data list in-place and follows the Python convention of returning None in such cases. |
The function modifies the input data list in-place and follows the Python convention of returning None in such cases. |
||
< |
<syntaxhighlight lang="python">>>> def sort_disjoint_sublist(data, indices): |
||
indices = sorted(indices) |
indices = sorted(indices) |
||
values = sorted(data[i] for i in indices) |
values = sorted(data[i] for i in indices) |
||
Line 1,196: | Line 3,284: | ||
>>> </ |
>>> </syntaxhighlight> |
||
Or, checking a dictionary for sublist indices, and returning a new (rather than mutated) list: |
|||
<syntaxhighlight lang="python">'''Disjoint sublist sorting''' |
|||
# --------------------- DISJOINT SORT ---------------------- |
|||
# disjointSort :: [Int] -> [Int] -> [Int] |
|||
def disjointSort(ixs): |
|||
'''A copy of the list xs, in which the disjoint sublist |
|||
of items at zero-based indexes ixs is sorted in a |
|||
default numeric or lexical order.''' |
|||
def go(xs): |
|||
ks = sorted(ixs) |
|||
dct = dict(zip(ks, sorted(xs[k] for k in ks))) |
|||
return [ |
|||
dct[i] if i in dct else x |
|||
for i, x in enumerate(xs) |
|||
] |
|||
return go |
|||
# -------------------------- TEST -------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''Disjoint sublist at three indices.''' |
|||
print( |
|||
tabulated( |
|||
'Disjoint sublist at indices [6, 1, 7] sorted:\n' |
|||
) |
|||
(str)(str)( |
|||
disjointSort([6, 1, 7]) |
|||
)([ |
|||
[7, 6, 5, 4, 3, 2, 1, 0], |
|||
['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'] |
|||
]) |
|||
) |
|||
# ------------------------ DISPLAY ------------------------- |
|||
# tabulated :: String -> (a -> String) -> |
|||
# (b -> String) -> |
|||
# (a -> b) -> [a] -> String |
|||
def tabulated(s): |
|||
'''Heading -> x display function -> fx display function -> |
|||
f -> value list -> tabular string.''' |
|||
def go(xShow, fxShow, f, xs): |
|||
w = max(map(compose(len)(xShow), xs)) |
|||
return s + '\n' + '\n'.join( |
|||
xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs |
|||
) |
|||
return lambda xShow: lambda fxShow: lambda f: lambda xs: go( |
|||
xShow, fxShow, f, xs |
|||
) |
|||
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c |
|||
def compose(g): |
|||
'''Function composition.''' |
|||
return lambda f: lambda x: g(f(x)) |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>Disjoint sublists at indices [6, 1, 7] sorted: |
|||
[7, 6, 5, 4, 3, 2, 1, 0] -> [7, 0, 5, 4, 3, 2, 1, 6] |
|||
['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'] -> ['h', 'a', 'f', 'e', 'd', 'c', 'b', 'g']</pre> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> [ sort tuck [] unrot |
|||
witheach |
|||
[ dip dup peek |
|||
rot join swap ] |
|||
swap sort |
|||
dip swap witheach |
|||
[ over i^ peek |
|||
dip rot poke |
|||
swap ] |
|||
drop ] is sortdisjointsublist ( [ [ --> [ ) |
|||
' [ 7 6 5 4 3 2 1 0 ] ' [ 6 1 7 ] sortdisjointsublist echo |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[ 7 0 5 4 3 2 1 6 ]</pre> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
R lets you access elements of vectors with a vector of indices. |
R lets you access elements of vectors with a vector of indices. |
||
< |
<syntaxhighlight lang="r"> values=c(7,6,5,4,3,2,1,0) |
||
indices=c(7,2,8) |
indices=c(7,2,8) |
||
values[sort(indices)]=sort(values[indices]) |
values[sort(indices)]=sort(values[indices]) |
||
print(values)</ |
print(values)</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> 7 0 5 4 3 2 1 6</pre> |
<pre> 7 0 5 4 3 2 1 6</pre> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket">#lang racket |
|||
<lang Racket> |
|||
#lang racket |
|||
(define (sort-disjoint l is) |
(define (sort-disjoint l is) |
||
Line 1,221: | Line 3,398: | ||
(sort-disjoint '(7 6 5 4 3 2 1 0) '(6 1 7)) |
(sort-disjoint '(7 6 5 4 3 2 1 0) '(6 1 7)) |
||
;; --> '(7 0 5 4 3 2 1 6) |
;; --> '(7 0 5 4 3 2 1 6)</syntaxhighlight> |
||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2020.08.1}} |
|||
===Inline=== |
|||
Using L-value slice of the array, and `sort` as a mutating method: |
|||
<syntaxhighlight lang="raku" line>my @values = 7, 6, 5, 4, 3, 2, 1, 0; |
|||
my @indices = 6, 1, 7; |
|||
@values[ @indices.sort ] .= sort; |
|||
say @values;</syntaxhighlight> |
|||
Output:<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
===Iterative=== |
|||
<syntaxhighlight lang="raku" line>sub disjointSort( @values, @indices --> List ) { |
|||
my @sortedValues = @values[ @indices ].sort ; |
|||
for @indices.sort -> $insert { |
|||
@values[ $insert ] = @sortedValues.shift ; |
|||
} |
|||
return @values ; |
|||
} |
|||
my @values = ( 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ) ; |
|||
my @indices = ( 6 , 1 , 7 ) ; |
|||
my @sortedValues = disjointSort( @values , @indices ) ; |
|||
say @sortedValues ;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Duplicate entries in the index list aren't destructive or illegal. |
Duplicate entries in the index list aren't destructive or illegal. |
||
<br><br>Note that the list may contain numbers in any form (integer, floating point, exponentationed), |
<br><br>Note that the list may contain numbers in any form (integer, floating point, exponentationed), |
||
<br>as well as alphabetic/alphanumeric/non-displayable characters. |
<br>as well as alphabetic/alphanumeric/non-displayable characters. |
||
<lang rexx>/*REXX program uses a strand sort to sort a random list of words | nums.*/ |
|||
parse arg old ',' idx /*get options from command line. */ |
|||
if old='' then old=7 6 5 4 3 2 1 0 /*no list? Then use the default.*/ |
|||
if idx='' then idx=7 2 8 /*no idxs? " " " " */ |
|||
old=space(old) /*remove any extraneous blanks. */ |
|||
say 'list of indices:' idx |
|||
idx=sortL(idx) /*ensure the index list is sorted*/ |
|||
say |
|||
say ' unsorted list:' old |
|||
new=disjoint_sort(old,idx) /*sort it.*/ |
|||
say ' sorted list:' new |
|||
exit /*stick a fork in it, we're done.*/ |
|||
/*──────────────────────────────────DISJOINT_SORT subroutine────────────*/ |
|||
disjoint_sort: procedure; parse arg x,indL; y=; z=; p=0 |
|||
do i=1 for words(indL) /*extract indexed values from X.*/ |
|||
z=z word(x,word(indL,i)) |
|||
end /*j*/ |
|||
z=sortL(z) /*sort extracted (indexed) values*/ |
|||
do m=1 for words(x) /*re-build (re-populate) X list.*/ |
|||
if wordpos(m,indL)==0 then y=y word(x,m) /*same | new?*/ |
|||
else do; p=p+1; y=y word(z,p); end |
|||
end /*m*/ |
|||
return strip(y) |
|||
/*──────────────────────────────────SORTL subroutine────────────────────*/ |
|||
sortL: procedure; parse arg L; n=words(L); do j=1 for n; @.j=word(L,j); end |
|||
do k=1 to n-1 /*sort index list the slow way. */ |
|||
do m=k+1 to n; if @.m<@.k then parse value @.k @.m with @.m @.k; end |
|||
end /*k*/ |
|||
s=@.1; do j=2 to n; s=s @.j; end; return s</lang> |
|||
'''output''' when using the default input: |
|||
<pre style="overflow:scroll"> |
|||
list of indices: 7 2 8 |
|||
The REXX language normally uses a one-based index. |
|||
unsorted list: 7 6 5 4 3 2 1 0 |
|||
<syntaxhighlight lang="rexx">/*REXX program uses a disjointed sublist to sort a random list of values. */ |
|||
sorted list: 7 0 5 4 3 2 1 6 |
|||
parse arg old ',' idx /*obtain the optional lists from the CL*/ |
|||
</pre> |
|||
if old='' then old= 7 6 5 4 3 2 1 0 /*Not specified: Then use the default.*/ |
|||
if idx='' then idx= 7 2 8 /* " " " " " " */ |
|||
say ' list of indices:' idx; say /* [↑] is for one─based lists. */ |
|||
say ' unsorted list:' old /*display the old list of numbers. */ |
|||
say ' sorted list:' disjoint_sort(old,idx) /*sort 1st list using 2nd list indices.*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
disjoint_sort: procedure; parse arg x,ix; y=; z=; p= 0 |
|||
ix= sortL(ix) /*ensure the index list is sorted*/ |
|||
do i=1 for words(ix) /*extract indexed values from X.*/ |
|||
z= z word(x, word(ix, i) ) /*pick the correct value from X.*/ |
|||
end /*j*/ |
|||
z= sortL(z) /*sort extracted (indexed) values*/ |
|||
do m=1 for words(x) /*re─build (re-populate) X list.*/ |
|||
if wordpos(m, ix)==0 then y=y word(x,m) /*is the same or new?*/ |
|||
else do; p= p + 1; y= y word(z, p) |
|||
end |
|||
end /*m*/ |
|||
return strip(y) |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
sortL: procedure; parse arg L; n= words(L); do j=1 for n; @.j= word(L,j) |
|||
end /*j*/ |
|||
do k=1 for n-1 /*sort a list using a slow method*/ |
|||
do m=k+1 to n; if @.m<@.k then parse value @.k @.m with @.m @.k |
|||
end /*m*/ |
|||
end /*k*/ /* [↑] use PARSE for swapping.*/ |
|||
$= @.1; do j=2 to n; $= $ @.j |
|||
end /*j*/ |
|||
return $</syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
|||
<pre> list of indices: 7 2 8 |
|||
unsorted list: 7 6 5 4 3 2 1 0 |
|||
sorted list: 7 0 5 4 3 2 1 6</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
aList = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
indList = [7, 2, 8] |
|||
bList = [] |
|||
for n = 1 to len(indList) |
|||
add(bList,[indList[n],aList[indList[n]]]) |
|||
next |
|||
bList1 = sort(bList,1) |
|||
bList2 = sort(bList,2) |
|||
for n = 1 to len(bList) |
|||
aList[bList1[n][1]] = bList2[n][2] |
|||
next |
|||
showarray(aList) |
|||
func showarray vect |
|||
svect = "" |
|||
for n in vect |
|||
svect += " " + n + "," |
|||
next |
|||
? "[" + left(svect, len(svect) - 1) + "]" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|RPL}}== |
|||
≪ SORT → set |
|||
≪ { } 1 set SIZE '''FOR''' j |
|||
OVER set j GET GET + '''NEXT''' |
|||
SORT SWAP |
|||
1 set SIZE '''FOR''' j |
|||
set j GET 3 PICK j GET PUT '''NEXT''' |
|||
SWAP DROP |
|||
≫ ≫ '<span style="color:blue">'''SUBSORT'''</span>' STO |
|||
HP-28 models shall use their homemade version of the SORT instruction, or use the one defined in [[Sorting algorithms/Bubble sort#RPL|Sorting algorithms/Bubble sort]] |
|||
{ 7 6 5 4 3 2 1 0 } { 6 1 7 } <span style="color:blue">'''SUBSORT'''</span> |
|||
{{out}} |
|||
<pre>1: { 7 0 5 4 3 2 1 6 }</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
By convention, the exlamation mark in the method name indicates that something potentially dangerous can happen. (In this case, the in place modification). |
By convention, the exlamation mark in the method name indicates that something potentially dangerous can happen. (In this case, the in place modification). |
||
< |
<syntaxhighlight lang="ruby">def sort_disjoint_sublist!(ar, indices) |
||
values = ar.values_at(*indices).sort |
values = ar.values_at(*indices).sort |
||
indices.sort.zip(values).each{ |i,v| ar[i] = v } |
indices.sort.zip(values).each{ |i,v| ar[i] = v } |
||
Line 1,275: | Line 3,521: | ||
values = [7, 6, 5, 4, 3, 2, 1, 0] |
values = [7, 6, 5, 4, 3, 2, 1, 0] |
||
indices = [6, 1, 7] |
indices = [6, 1, 7] |
||
p sort_disjoint_sublist!(values, indices)</ |
p sort_disjoint_sublist!(values, indices)</syntaxhighlight> |
||
{{out}} |
|||
Output |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">use std::collections::BTreeSet; |
|||
fn disjoint_sort(array: &mut [impl Ord], indices: &[usize]) { |
|||
=={{header|Run BASIC}}== |
|||
let mut sorted = indices.to_owned(); |
|||
Normally we sort with SQLite in memory. Faster and less code |
|||
sorted.sort_unstable_by_key(|k| &array[*k]); |
|||
<lang runbasic>sortData$ = "7, 6, 5, 4, 3, 2, 1, 0" |
|||
indices |
|||
sortIdx$ = "7, 2, 8" |
|||
.iter() |
|||
.zip(sorted.iter()) |
|||
.map(|(&a, &b)| if a > b { (b, a) } else { (a, b) }) |
|||
.collect::<BTreeSet<_>>() |
|||
.iter() |
|||
.for_each(|(a, b)| array.swap(*a, *b)) |
|||
} |
|||
fn main() { |
|||
numSort = 8 |
|||
let mut array = [7, 6, 5, 4, 3, 2, 1, 0]; |
|||
dim sortData(numSort) |
|||
let indices = [6, 1, 7]; |
|||
for i = 1 to numSort |
|||
disjoint_sort(&mut array, &indices); |
|||
sortData(i) = val(word$(sortData$,i,",")) |
|||
println!("{:?}", array); |
|||
next i |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Scala}}== |
|||
while word$(sortIdx$,s + 1) <> "" |
|||
{{libheader|Scala}}<syntaxhighlight lang="scala">import scala.compat.Platform |
|||
s = s + 1 |
|||
idx = val(word$(sortIdx$,s)) |
|||
gosub [bubbleSort] |
|||
wend |
|||
end |
|||
object SortedDisjointSubList extends App { |
|||
[bubbleSort] |
|||
val (list, subListIndex) = (List(7, 6, 5, 4, 3, 2, 1, 0), List(6, 1, 7)) |
|||
sortSw = 1 |
|||
while sortSw = 1 |
|||
def sortSubList[T: Ordering](indexList: List[Int], list: List[T]) = { |
|||
sortSw = 0 |
|||
val subListIndex = indexList.sorted |
|||
for i = idx to numSort - 1 ' start sorting at idx |
|||
val sortedSubListMap = subListIndex.zip(subListIndex.map(list(_)).sorted).toMap |
|||
if sortData(i) > sortData(i+1) then |
|||
sortSw = 1 |
|||
list.zipWithIndex.map { case (value, index) => |
|||
sortHold = sortData(i) |
|||
if (sortedSubListMap.isDefinedAt(index)) sortedSubListMap(index) else value |
|||
sortData(i) = sortData(i+1) |
|||
} |
|||
sortData(i+1) = sortHold |
|||
} |
|||
next i |
|||
assert(sortSubList(subListIndex, list) == List(7, 0, 5, 4, 3, 2, 1, 6), "Incorrect sort") |
|||
wend |
|||
println(s"List in sorted order.\nSuccessfully completed without errors. [total ${Platform.currentTime - executionStart} ms]") |
|||
RETURN</lang> |
|||
}</syntaxhighlight> |
|||
=={{header|Scheme}}== |
|||
{{works with|Gauche Scheme}} |
|||
<syntaxhighlight lang="scheme">(use gauche.sequence) |
|||
(define num-list '(7 6 5 4 3 2 1 0)) |
|||
(define indices '(6 1 7)) |
|||
(define table |
|||
(alist->hash-table |
|||
(map cons |
|||
(sort indices) |
|||
(sort indices < (lambda (x) (~ num-list x)))))) |
|||
(map last |
|||
(sort |
|||
(map-with-index |
|||
(lambda (i x) (list (hash-table-get table i i) x)) |
|||
num-list) |
|||
< |
|||
car))</syntaxhighlight> |
|||
{{output}} |
|||
<pre>(7 0 5 4 3 2 1 6)</pre> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func disjointSort(values, indices) { |
|||
values[indices.sort] = [values[indices]].sort... |
|||
} |
|||
var values = [7, 6, 5, 4, 3, 2, 1, 0]; |
|||
var indices = [6, 1, 7]; |
|||
disjointSort(values, indices); |
|||
say values;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
{{works with|SML/NJ}} |
{{works with|SML/NJ}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="sml">functor SortDisjointFn (A : MONO_ARRAY) : sig |
||
val sort : (A.elem * A.elem -> order) -> (A.array * int array) -> unit |
val sort : (A.elem * A.elem -> order) -> (A.array * int array) -> unit |
||
end = struct |
end = struct |
||
Line 1,357: | Line 3,646: | ||
DisjointViewSort.sort cmp (arr, indices) |
DisjointViewSort.sort cmp (arr, indices) |
||
) |
) |
||
end</ |
end</syntaxhighlight> |
||
Usage: |
Usage: |
||
<pre>- structure IntArray = struct |
<pre>- structure IntArray = struct |
||
Line 1,379: | Line 3,668: | ||
- a; |
- a; |
||
val it = [|7,0,5,4,3,2,1,6|] : int array</pre> |
val it = [|7,0,5,4,3,2,1,6|] : int array</pre> |
||
=={{header|Swift}}== |
|||
{{trans|Go}} |
|||
Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array. |
|||
<syntaxhighlight lang="swift">struct DisjointSublistView<T> : MutableCollectionType { |
|||
let array : UnsafeMutablePointer<T> |
|||
let indexes : [Int] |
|||
subscript (position: Int) -> T { |
|||
get { |
|||
return array[indexes[position]] |
|||
} |
|||
set { |
|||
array[indexes[position]] = newValue |
|||
} |
|||
} |
|||
var startIndex : Int { return 0 } |
|||
var endIndex : Int { return indexes.count } |
|||
func generate() -> IndexingGenerator<DisjointSublistView<T>> { return IndexingGenerator(self) } |
|||
} |
|||
func sortDisjointSublist<T : Comparable>(inout array: [T], indexes: [Int]) { |
|||
var d = DisjointSublistView(array: &array, indexes: sorted(indexes)) |
|||
sort(&d) |
|||
} |
|||
var a = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
let ind = [6, 1, 7] |
|||
sortDisjointSublist(&a, ind) |
|||
println(a)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
This returns the sorted copy of the list; this is idiomatic for Tcl programs where values are immutable. |
This returns the sorted copy of the list; this is idiomatic for Tcl programs where values are immutable. |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc disjointSort {values indices args} { |
proc disjointSort {values indices args} { |
||
# Ensure that we have a unique list of integers, in order |
# Ensure that we have a unique list of integers, in order |
||
Line 1,396: | Line 3,717: | ||
# The updated list is the result |
# The updated list is the result |
||
return $values |
return $values |
||
}</ |
}</syntaxhighlight> |
||
Demonstration: |
Demonstration: |
||
< |
<syntaxhighlight lang="tcl">set values {7 6 5 4 3 2 1 0} |
||
set indices {6 1 7} |
set indices {6 1 7} |
||
puts \[[join [disjointSort $values $indices] ", "]\]</ |
puts \[[join [disjointSort $values $indices] ", "]\]</syntaxhighlight> |
||
{{out}} |
|||
Output: |
|||
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre> |
||
=={{header|TUSCRIPT}}== |
=={{header|TUSCRIPT}}== |
||
TUSCRIPT indexing is one based |
TUSCRIPT indexing is one based |
||
< |
<syntaxhighlight lang="tuscript">$$ MODE TUSCRIPT |
||
$$ MODE TUSCRIPT |
|||
values="7'6'5'4'3'2'1'0" |
values="7'6'5'4'3'2'1'0" |
||
indices="7'2'8" |
indices="7'2'8" |
||
Line 1,415: | Line 3,736: | ||
values=REPLACE (values,#i,v) |
values=REPLACE (values,#i,v) |
||
ENDLOOP |
ENDLOOP |
||
PRINT values |
PRINT values</syntaxhighlight> |
||
{{out}} |
|||
</lang> |
|||
<pre>7'0'5'4'3'2'1'6 </pre> |
|||
Output: |
|||
=={{header|Uiua}}== |
|||
{{works with|Uiua|0.11.1}} |
|||
<syntaxhighlight lang="uiua"> |
|||
⍜▽(⊏⍏.)°⊚ 6_1_7 [7 6 5 4 3 2 1 0] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
<pre> |
||
7 |
[7 0 5 4 3 2 1 6] |
||
</pre> |
</pre> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#import nat |
#import nat |
||
Line 1,430: | Line 3,758: | ||
#cast %nL |
#cast %nL |
||
t = disjoint_sort({6,1,7},<7,6,5,4,3,2,1,0>)</ |
t = disjoint_sort({6,1,7},<7,6,5,4,3,2,1,0>)</syntaxhighlight> |
||
{{out}} |
|||
output: |
|||
<pre><7,0,5,4,3,2,1,6></pre> |
<pre><7,0,5,4,3,2,1,6></pre> |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-sort}} |
|||
<syntaxhighlight lang="wren">import "./sort" for Sort |
|||
// sorts values in place, leaves indices unsorted |
|||
var sortDisjoint = Fn.new { |values, indices| |
|||
var sublist = [] |
|||
for (ix in indices) sublist.add(values[ix]) |
|||
Sort.quick(sublist) |
|||
var i = 0 |
|||
var indices2 = Sort.merge(indices) |
|||
for (ix in indices2) { |
|||
values[ix] = sublist[i] |
|||
i = i + 1 |
|||
} |
|||
} |
|||
var values = [7, 6, 5, 4, 3, 2, 1, 0] |
|||
var indices = [6, 1, 7] |
|||
System.print("Initial: %(values)") |
|||
sortDisjoint.call(values, indices) |
|||
System.print("Sorted : %(values)")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Initial: [7, 6, 5, 4, 3, 2, 1, 0] |
|||
Sorted : [7, 0, 5, 4, 3, 2, 1, 6]</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="xpl0">include xpllib; \for Sort routine |
|||
int Values, Indices, J, I, T; |
|||
[Values:= [7, 6, 5, 4, 3, 2, 1, 0]; |
|||
Indices:= [6, 1, 7]; |
|||
Sort(Indices, 3); |
|||
for J:= 3-1 downto 0 do \bubble sort values at Indices |
|||
for I:= 0 to J-1 do |
|||
if Values(Indices(I)) > Values(Indices(I+1)) then |
|||
[T:= Values(Indices(I)); |
|||
Values(Indices(I)):= Values(Indices(I+1)); |
|||
Values(Indices(I+1)):= T; |
|||
]; |
|||
for I:= 0 to 8-1 do |
|||
[IntOut(0, Values(I)); ChOut(0, ^ )]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>7 0 5 4 3 2 1 6 </pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">values :=T(7, 6, 5, 4, 3, 2, 1, 0); |
||
indices:=T(6, 1, 7); |
indices:=T(6, 1, 7); |
||
indices.apply(values. |
indices.apply(values.get).sort() // a.get(0) == a[0] |
||
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7)) |
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7)) |
||
.reduce(fcn(newList,[(v,i)]){ newList[i]=v; newList },values.copy()) |
.reduce(fcn(newList,[(v,i)]){ newList[i]=v; newList },values.copy()) |
||
.println(); // new list</ |
.println(); // new list</syntaxhighlight> |
||
This is an create-new-object version. An in place version is almost identical: |
This is an create-new-object version. An in place version is almost identical: |
||
< |
<syntaxhighlight lang="zkl">values :=L(7, 6, 5, 4, 3, 2, 1, 0); |
||
indices.apply(values. |
indices.apply(values.get).sort() // a.get(0) == a[0] |
||
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7)) |
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7)) |
||
.apply2(fcn([(v,i)],list){ list[i]=v },values); |
.apply2(fcn([(v,i)],list){ list[i]=v },values); |
||
values.println(); // modified list</ |
values.println(); // modified list</syntaxhighlight> |
||
{{out}} |
|||
{{out}}<pre>L(7,0,5,4,3,2,1,6)</pre> |
|||
<pre>L(7,0,5,4,3,2,1,6)</pre> |
Latest revision as of 08:45, 23 July 2024
You are encouraged to solve this task according to the task description, using any language you may know.
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
Given a list of values and a set of integer indices into that value list, the task is to sort the values at the given indices, while preserving the values at indices outside the set of those to be sorted.
Make your example work with the following list of values and set of indices:
- Values:
[7, 6, 5, 4, 3, 2, 1, 0]
- Values:
- Indices:
{6, 1, 7}
- Indices:
Where the correct result would be:
[7, 0, 5, 4, 3, 2, 1, 6]
.
In case of one-based indexing, rather than the zero-based indexing above, you would use the indices {7, 2, 8}
instead.
The indices are described as a set rather than a list but any collection-type of those indices without duplication may be used as long as the example is insensitive to the order of indices given.
- Cf.
11l
F sort_disjoint_sublist(&data, indices)
V sindices = sorted(indices)
V values = sorted(sindices.map(i -> @data[i]))
L(index, value) zip(sindices, values)
data[index] = value
V d = [7, 6, 5, 4, 3, 2, 1, 0]
V i = [6, 1, 7]
sort_disjoint_sublist(&d, i)
print(d)
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
AArch64 Assembly
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program sublistSort64.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessStart: .asciz "Program 64 bits start.\n"
sMessResult: .ascii "Value : "
sMessValeur: .fill 11, 1, ' ' // size => 11
szCarriageReturn: .asciz "\n"
.align 4
ArrayNumber: .quad 7, 6, 5, 4, 3, 2, 1, 0
.equ NBELEMENTS, (. - ArrayNumber) / 8
ArrayIndex: .quad 6,1,7
.equ NBELEMINDEX, (. - ArrayIndex) / 8
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
ArrayExtract: .skip 8 * NBELEMINDEX
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr x0,qAdrszMessStart
bl affichageMess
ldr x4,qAdrArrayNumber // number array address
ldr x5,qAdrArrayIndex // index array address
ldr x6,qAdrArrayExtract // extract array address
mov x3,#0 // index
1:
ldr x0,[x5,x3,lsl #3] // load index
ldr x1,[x4,x0,lsl #3] // load value of index
str x1,[x6,x3,lsl #3] // store value in array extract
add x3,x3,#1 // increment index
cmp x3,#NBELEMINDEX // end array index ?
blt 1b // no -> loop
mov x0,x5 // index array address
mov x1,#0 // first element
mov x2,#NBELEMINDEX // array size
bl insertionSort
mov x0,x6 // extract array address
mov x1,#0 // first element
mov x2,#NBELEMINDEX // array size
bl insertionSort
mov x3,#0 // init index
2:
ldr x0,[x6,x3,lsl #3] // load value of array extract
ldr x1,[x5,x3,lsl #3] // load index
str x0,[x4,x1,lsl #3] // store value in number array in index place
add x3,x3,#1 // increment indice
cmp x3,#NBELEMINDEX
blt 2b
mov x0,x4 // number array address
bl displayArray
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
qAdrsMessValeur: .quad sMessValeur
qAdrszMessStart: .quad szMessStart
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrsMessResult: .quad sMessResult
qAdrArrayNumber: .quad ArrayNumber
qAdrArrayIndex: .quad ArrayIndex
qAdrArrayExtract: .quad ArrayExtract
/******************************************************************/
/* insertion sort */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element */
/* x2 contains the number of element */
insertionSort:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]!
stp x4,x5,[sp,-16]!
stp x6,x7,[sp,-16]!
add x3,x1,#1 // start index i
1: // start loop
ldr x4,[x0,x3,lsl #3] // load value A[i]
sub x5,x3,#1 // index j
2:
ldr x6,[x0,x5,lsl #3] // load value A[j]
cmp x6,x4 // compare value
ble 3f
add x5,x5,#1 // increment index j
str x6,[x0,x5,lsl #3] // store value A[j+1]
subs x5,x5,#2 // j = j - 1
bge 2b // loop if j >= 0
3:
add x5,x5,#1 // increment index j
str x4,[x0,x5,lsl #3] // store value A[i] in A[j+1]
add x3,x3,#1 // increment index i
cmp x3,x2 // end ?
blt 1b // no -> loop
100:
ldp x6,x7,[sp],16
ldp x4,x5,[sp],16
ldp x2,x3,[sp],16
ldp x1,lr,[sp],16
ret
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* x0 contains the address of array */
displayArray:
stp x1,lr,[sp,-16]!
stp x2,x3,[sp,-16]!
mov x2,x0 // table address
mov x3,#0
1: // loop display table
ldr x0,[x2,x3,lsl #3]
ldr x1,qAdrsMessValeur // display value
bl conversion10 // call function
ldr x0,qAdrsMessResult
bl affichageMess // display message
ldr x0,qAdrszCarriageReturn
bl affichageMess
add x3,x3,#1
cmp x3,#NBELEMENTS
blt 1b
ldr x0,qAdrszCarriageReturn
bl affichageMess
100:
ldp x2,x3,[sp],16
ldp x1,lr,[sp],16
ret
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
- Output:
Program 64 bits start. Value : 7 Value : 0 Value : 5 Value : 4 Value : 3 Value : 2 Value : 1 Value : 6
Action!
PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
BYTE FUNC InSet(INT ARRAY s INT size INT v)
INT i
FOR i=0 TO size-1
DO
IF s(i)=v THEN
RETURN (1)
FI
OD
RETURN (0)
PROC Sort(INT ARRAY arr INT arrSize
INT ARRAY ind INT indSize)
INT i,j,minpos,tmp
FOR i=0 TO arrSize-2
DO
IF InSet(ind,indSize,i) THEN
minpos=i
FOR j=i+1 TO arrSize-1
DO
IF InSet(ind,indSize,j)=1 AND arr(minpos)>arr(j) THEN
minpos=j
FI
OD
IF minpos#i THEN
tmp=arr(i)
arr(i)=arr(minpos)
arr(minpos)=tmp
FI
FI
OD
RETURN
PROC Test(INT ARRAY arr INT arrSize
INT ARRAY ind INT indSize)
PrintE("Array before sort:")
PrintArray(arr,arrSize)
PrintE("Indices:")
PrintArray(ind,indSize)
Sort(arr,arrSize,ind,indSize)
PrintE("Array after sort:")
PrintArray(arr,arrSize)
RETURN
PROC Main()
INT ARRAY
arr(8)=[7 6 5 4 3 2 1 0],
ind(3)=[6 1 7]
Test(arr,8,ind,3)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Array before sort: [7 6 5 4 3 2 1 0] Indices: [6 1 7] Array after sort: [7 0 5 4 3 2 1 6]
Ada
with Ada.Text_IO, GNAT.Bubble_Sort;
use Ada.Text_IO;
procedure DisjointSort is
package Int_Io is new Integer_IO (Integer);
subtype Index_Range is Natural range 1 .. 8;
Input_Array : array (Index_Range) of Integer := (7, 6, 5, 4, 3, 2, 1, 0);
subtype Subindex_Range is Natural range 1 .. 3;
type Sub_Arrays is array (Subindex_Range) of Integer;
Sub_Index : Sub_Arrays := (7, 2, 8);
Sub_Array : Sub_Arrays;
-- reuse of the somehow generic GNAT.Bubble_Sort (for Ada05)
procedure Sort (Work_Array : in out Sub_Arrays) is
procedure Exchange (Op1, Op2 : Natural) is
Temp : Integer;
begin
Temp := Work_Array (Op1);
Work_Array (Op1) := Work_Array (Op2);
Work_Array (Op2) := Temp;
end Exchange;
function Lt (Op1, Op2 : Natural) return Boolean is
begin
return (Work_Array (Op1) < Work_Array (Op2));
end Lt;
begin
GNAT.Bubble_Sort.Sort
(N => Subindex_Range'Last,
Xchg => Exchange'Unrestricted_Access,
Lt => Lt'Unrestricted_Access);
end Sort;
begin
-- as the positions are not ordered, first sort the positions
Sort (Sub_Index);
-- extract the values to be sorted
for I in Subindex_Range loop
Sub_Array (I) := Input_Array (Sub_Index (I));
end loop;
Sort (Sub_Array);
-- put the sorted values at the right place
for I in Subindex_Range loop
Input_Array (Sub_Index (I)) := Sub_Array (I);
end loop;
for I in Index_Range loop
Int_Io.Put (Input_Array (I), Width => 2);
end loop;
New_Line;
end DisjointSort;
ALGOL W
Uses the quicksort procedure from the Sorting Algorithms/Quicksort task and a variant for indexed sorting.
begin % sort a disjoint sub-set of a list %
% Quicksorts in-place the array of integers v, from lb to ub %
procedure quicksort ( integer array v( * )
; integer value lb, ub
) ;
if ub > lb then begin
% more than one element, so must sort %
integer left, right, pivot;
left := lb;
right := ub;
% choosing the middle element of the array as the pivot %
pivot := v( left + ( ( right + 1 ) - left ) div 2 );
while begin
while left <= ub and v( left ) < pivot do left := left + 1;
while right >= lb and v( right ) > pivot do right := right - 1;
left <= right
end do begin
integer swap;
swap := v( left );
v( left ) := v( right );
v( right ) := swap;
left := left + 1;
right := right - 1
end while_left_le_right ;
quicksort( v, lb, right );
quicksort( v, left, ub )
end quicksort ;
% Quicksorts in-place the array of integers v, using %
% the indxexes in unsortedIndexes which has bounds lb to ub %
% it is assumed all elements of unsortedIndexes are in the %
% range for subscripts of v %
procedure indexedQuicksort ( integer array v, unsortedIndexes ( * )
; integer value lb, ub
) ;
if ub > lb then begin
% more than one element, so must sort %
integer array indexes ( lb :: ub );
integer left, right, pivot, p;
% sort the indexes %
for i := lb until ub do indexes( i ) := unsortedIndexes( i );
quicksort( indexes, lb, ub );
% sort the indexed items of the v array %
left := lb;
right := ub;
% choosing the middle element of the array as the pivot %
p := left + ( ( ( right + 1 ) - left ) div 2 );
pivot := v( indexes( p ) );
while begin
while left <= ub and v( indexes( left ) ) < pivot do left := left + 1;
while right >= lb and v( indexes( right ) ) > pivot do right := right - 1;
left <= right
end do begin
integer swap;
swap := v( indexes( left ) );
v( indexes( left ) ) := v( indexes( right ) );
v( indexes( right ) ) := swap;
left := left + 1;
right := right - 1
end while_left_le_right ;
indexedQuicksort( v, indexes, lb, right );
indexedQuicksort( v, indexes, left, ub )
end indexedQuicksort ;
begin % task %
integer array indexes ( 0 :: 2 );
integer array values ( 0 :: 7 );
integer aPos;
aPos := 0;
for v := 7, 6, 5, 4, 3, 2, 1, 0 do begin
values( aPos ) := v;
aPos := aPos + 1
end for_v ;
indexes( 0 ) := 6;
indexes( 1 ) := 1;
indexes( 2 ) := 7;
i_w := 1; s_w := 0; % set output formatting %
write( "[" );
for v := 0 until 7 do writeon( " ", values( v ) );
writeon( " ]" );
indexedQuicksort( values, indexes, 0, 2 );
writeon( " -> [" );
for v := 0 until 7 do writeon( " ", values( v ) );
writeon( " ]" )
end
end.
- Output:
[ 7 6 5 4 3 2 1 0 ] -> [ 7 0 5 4 3 2 1 6 ]
APL
∇SDS[⎕]∇
∇
[0] Z←I SDS L
[1] L[I[⍋I]]←Z[⍋Z←L[I←∪I]]
[2] Z←L
∇
- Output:
⎕IO←0 6 1 7 SDS ⎕←⌽⍳8 7 6 5 4 3 2 1 0 7 0 5 4 3 2 1 6
AppleScript
Functional
Uses Foundation framework (through the ObjC interface), and works with versions of AppleScript from OS X 10.10 onwards.
use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
-- disjointSort :: [Int] -> [Int] -> [Int]
on disjointSort(ixs, xs)
set ks to sort(ixs)
script nth -- 1-based index
on |λ|(k)
item (succ(k)) of xs
end |λ|
end script
set dct to mapFromList(zip(ks, sort(map(nth, ks))))
script build
on |λ|(x, i)
set mb to lookupDict(pred(i) as string, dct)
if Nothing of mb then
x
else
|Just| of mb
end if
end |λ|
end script
map(build, xs)
end disjointSort
on run
disjointSort({6, 1, 7}, {7, 6, 5, 4, 3, 2, 1, 0})
end run
-- GENERIC FUNCTIONS ----------------------------------------------------
-- Just :: a -> Maybe a
on Just(x)
{type:"Maybe", Nothing:false, Just:x}
end Just
-- Nothing :: Maybe a
on Nothing()
{type:"Maybe", Nothing:true}
end Nothing
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
-- lookupDict :: a -> Dict -> Maybe b
on lookupDict(k, dct)
set ca to current application
set v to (ca's NSDictionary's dictionaryWithDictionary:dct)'s objectForKey:k
if v ≠ missing value then
Just(item 1 of ((ca's NSArray's arrayWithObject:v) as list))
else
Nothing()
end if
end lookupDict
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mapFromList :: [(k, v)] -> Dict
on mapFromList(kvs)
set tpl to unzip(kvs)
script
on |λ|(x)
x as string
end |λ|
end script
(current application's NSDictionary's ¬
dictionaryWithObjects:(|2| of tpl) ¬
forKeys:map(result, |1| of tpl)) as record
end mapFromList
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- pred :: Enum a => a -> a
on pred(x)
x - 1
end pred
-- sort :: Ord a => [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬
sortedArrayUsingSelector:"compare:") as list
end sort
-- succ :: Enum a => a -> a
on succ(x)
1 + x
end succ
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
if 0 < n then
items 1 thru min(n, length of xs) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to xs's |λ|()
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take
-- Tuple (,) :: a -> b -> (a, b)
on Tuple(a, b)
{type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple
-- unzip :: [(a,b)] -> ([a],[b])
on unzip(xys)
set xs to {}
set ys to {}
repeat with xy in xys
set end of xs to |1| of xy
set end of ys to |2| of xy
end repeat
return Tuple(xs, ys)
end unzip
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
zipWith(Tuple, xs, ys)
end zip
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on zipWith(f, xs, ys)
set lng to min(|length|(xs), |length|(ys))
if 1 > lng then return {}
set xs_ to take(lng, xs) -- Allow for non-finite
set ys_ to take(lng, ys) -- generators like cycle etc
set lst to {}
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs_, item i of ys_)
end repeat
return lst
end tell
end zipWith
- Output:
{7, 0, 5, 4, 3, 2, 1, 6}
Idiomatic, vanilla
This works with Mac OS 10.9 or later, and with older systems if an earlier method's used to load the insertion sort handler or that handler's copied into the script.
use AppleScript version "2.3.1" -- Mac OS 10.9 (Mavericks) or later.
use sorter : script "Insertion sort" -- https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript.
on sortValuesAtIndices(values, indices)
set indexedValues to {}
repeat with thisIndex in indices
set end of indexedValues to item thisIndex of values
end repeat
set indexCount to (count indices)
tell sorter to sort(indexedValues, 1, indexCount)
tell sorter to sort(indices, 1, indexCount)
repeat with i from 1 to indexCount
set thisIndex to item i of indices
set item thisIndex of values to item i of indexedValues
end repeat
return
end sortValuesAtIndices
-- Test code:
set values to {7, 6, 5, 4, 3, 2, 1, 0}
set indices to {7, 2, 8} -- AppleScript indices are one-based.
sortValuesAtIndices(values, indices)
return values
- Output:
{7, 0, 5, 4, 3, 2, 1, 6}
ARM Assembly
/* ARM assembly Raspberry PI */
/* program sublistSort.s */
/************************************/
/* Constantes */
/************************************/
/* for constantes see task include a file in arm assembly */
.include "../constantes.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessStart: .asciz "Program 32 bits start.\n"
sMessResult: .ascii "Value : "
sMessValeur: .fill 11, 1, ' ' @ size => 11
szCarriageReturn: .asciz "\n"
.align 4
ArrayNumber: .int 7, 6, 5, 4, 3, 2, 1, 0
.equ NBELEMENTS, (. - ArrayNumber) / 4
ArrayIndex: .int 6,1,7
.equ NBELEMINDEX, (. - ArrayIndex) / 4
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
ArrayExtract: .skip 4 * NBELEMINDEX
/*********************************/
/* code section */
/*********************************/
.text
.global main
main:
ldr r0,iAdrszMessStart
bl affichageMess
ldr r4,iAdrArrayNumber @ number array address
ldr r5,iAdrArrayIndex @ index array address
ldr r6,iAdrArrayExtract @ extract array address
mov r3,#0 @ index
1:
ldr r0,[r5,r3,lsl #2] @ load index
ldr r1,[r4,r0,lsl #2] @ load value of index
str r1,[r6,r3,lsl #2] @ store value in array extract
add r3,r3,#1 @ increment index
cmp r3,#NBELEMINDEX @ end array index ?
blt 1b @ no -> loop
mov r0,r5 @ index array address
mov r1,#0 @ first element
mov r2,#NBELEMINDEX @ array size
bl insertionSort
mov r0,r6 @ extract array address
mov r1,#0 @ first element
mov r2,#NBELEMINDEX @ array size
bl insertionSort
mov r3,#0 @ init index
2:
ldr r0,[r6,r3,lsl #2] @ load value of array extract
ldr r1,[r5,r3,lsl #2] @ load index
str r0,[r4,r1,lsl #2] @ store value in number array in index place
add r3,r3,#1 @ increment indice
cmp r3,#NBELEMINDEX
blt 2b
mov r0,r4 @ number array address
bl displayArray
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrszMessStart: .int szMessStart
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessResult: .int sMessResult
iAdrArrayNumber: .int ArrayNumber
iAdrArrayIndex: .int ArrayIndex
iAdrArrayExtract: .int ArrayExtract
/******************************************************************/
/* insertion sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element */
/* r2 contains the number of element */
insertionSort:
push {r2-r6,lr} @ save registers
add r3,r1,#1 @ start index i
1: @ start loop
ldr r4,[r0,r3,lsl #2] @ load value A[i]
sub r5,r3,#1 @ index j
2:
ldr r6,[r0,r5,lsl #2] @ load value A[j]
cmp r6,r4 @ compare value
ble 3f
add r5,#1 @ increment index j
str r6,[r0,r5,lsl #2] @ store value A[j+1]
subs r5,#2 @ j = j - 1
bge 2b @ loop if j >= 0
3:
add r5,#1 @ increment index j
str r4,[r0,r5,lsl #2] @ store value A[i] in A[j+1]
add r3,#1 @ increment index i
cmp r3,r2 @ end ?
blt 1b @ no -> loop
100:
pop {r2-r6,pc}
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayArray:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsMessValeur @ display value
bl conversion10 @ call function
ldr r0,iAdrsMessResult
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS
blt 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
100:
pop {r0-r3,lr}
bx lr
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"
- Output:
Program 32 bits start. Value : 7 Value : 0 Value : 5 Value : 4 Value : 3 Value : 2 Value : 1 Value : 6
Arturo
sortDisjoint: function [data, indices][
result: new data
inds: new indices
sort 'inds
vals: new []
loop inds 'i -> 'vals ++ result\[i]
sort 'vals
loop.with:'j inds 'i -> result\[i]: vals\[j]
return result
]
d: [7 6 5 4 3 2 1 0]
print sortDisjoint d [6 1 7]
- Output:
7 0 5 4 3 2 1 6
ATS
Much of the code here is proofs, unfolding and re-folding of lists, necessary assertions, memory management enforced by the type system, etc. (Some might say I am somewhat lax in my handling of pointers, using the simplest type ptr instead of more elaborate types.)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
(* For simplicity, I implement this task only for sorting values of
non-linear type. That would include all the basic integer types,
garbage-collected strings, etc.
Also I freely create arrays as workspace, although the size of any
workspace array is equal only to the number of indices (not to the
number of values). *)
extern fn {a : t@ype}
sort_disjoint_sublist$cmp : (a, a) -<> int
fn {a : t@ype}
sort_disjoint_sublist
{m : int}
{n : int}
(values : &list_vt (a, m) >> _,
indices : list ([i : nat | i < m] int i, n))
: void =
let
typedef index = [i : nat | i < m] int i
prval () = lemma_list_vt_param values
prval () = lemma_list_param indices
val num_values : size_t m = i2sz (list_vt_length values)
and num_indices : size_t n = i2sz (list_length indices)
(* Put the indices in ascending order. *)
val @(pf_ix, pfgc_ix | p_ix) =
array_ptr_alloc<index> num_indices
macdef ix = !p_ix
val () = array_initize_list<index> (ix, sz2i num_indices, indices)
implement
array_quicksort$cmp<index> (x, y) =
if x < y then ~1 else 1
val () = array_quicksort<index> (ix, num_indices)
(* Initialize a "refs" array with pointers to the relevant list
nodes. The pointers will be in ascending index order. *)
val @(pf_refs, pfgc_refs | p_refs) =
array_ptr_alloc<ptr> num_indices
fun
init_refs {j : nat | j <= m}
{i : nat | i <= n}
{p_refs : addr}
.<m - j>.
(pf_refs : !array_v (ptr?, p_refs + (i * sizeof ptr),
n - i)
>> array_v (ptr, p_refs + (i * sizeof ptr),
n - i) |
ix : &array (index, n),
p_refs : ptr p_refs,
i : size_t i,
values : &list_vt (a, m - j),
j : size_t j)
:<!wrt> void =
if i < num_indices then
case+ values of
| list_vt_nil () => $effmask_exn assertloc (false)
| @ list_vt_cons (head, tail) =>
if j = ix[i] then
let
prval @(pf_elem, pf_rest) = array_v_uncons pf_refs
val p = ptr_add<ptr> (p_refs, i)
val () = ptr_set<ptr> (pf_elem | p, addr@ values)
val () = init_refs (pf_rest | ix, p_refs, succ i,
tail, succ j)
prval () = pf_refs := array_v_cons (pf_elem, pf_rest)
prval () = fold@ values
in
end
else
let
val () = init_refs (pf_refs | ix, p_refs, i,
tail, succ j)
prval () = fold@ values
in
end
else
let
prval () = pf_refs := array_v_unnil_nil{ptr?, ptr} pf_refs
in
end
val () = init_refs (pf_refs | ix, p_refs, i2sz 0, values, i2sz 0)
(* Sort through the "refs" pointers. Here we will do that by
copying the values to an array, sorting the array, then writing
the sorted values back. One could also do the sort in place,
however. *)
val @(pf_vals, pfgc_vals | p_vals) =
array_ptr_alloc<a> num_indices
macdef vals = !p_vals
implement
array_initize$init<a> (i, x) =
let
val @(pf1, fpf1 | p1) = $UN.ptr_vtake{array (ptr, n)} p_refs
macdef refs = !p1
val i1 = g1ofg0 i
prval () = lemma_g1uint_param i1
val () = assertloc (i1 < num_indices)
val @(pf2, fpf2 | p2) = $UN.ptr_vtake{List1_vt a} (refs[i1])
val+ @ list_vt_cons (head, tail) = !p2
val () = x := head
prval () = fold@ (!p2)
prval () = fpf2 pf2
prval () = fpf1 pf1
in
end
val () = array_initize<a> (vals, num_indices)
implement
array_quicksort$cmp<a> (x, y) =
sort_disjoint_sublist$cmp<a> (x, y)
val () = array_quicksort<a> (vals, num_indices)
fun
write_back_values
{i : nat | i <= n}
{p_refs : addr}
(pf_refs : !array_v (ptr, p_refs, n) |
p_refs : ptr p_refs,
vals : &array (a, n),
i : size_t i)
: void =
if i <> num_indices then
let
macdef refs = !p_refs
val @(pf1, fpf1 | p1) = $UN.ptr_vtake{List1_vt a} (refs[i])
val+ @ list_vt_cons (head, tail) = !p1
val () = head := vals[i]
prval () = fold@ (!p1)
prval () = fpf1 pf1
in
write_back_values (pf_refs | p_refs, vals, succ i)
end
val () = write_back_values (pf_refs | p_refs, vals, i2sz 0)
in
array_ptr_free (pf_ix, pfgc_ix | p_ix);
array_ptr_free (pf_refs, pfgc_refs | p_refs);
array_ptr_free (pf_vals, pfgc_vals | p_vals)
end
implement
sort_disjoint_sublist$cmp<int> (x, y) =
if x < y then
~1
else if y < x then
1
else
0
implement
main0 () =
let
var values = $list_vt{int} (7, 6, 5, 4, 3, 2, 1, 0)
val indices = $list{[i : nat | i < 8] int i} (6, 1, 7)
in
println! values;
sort_disjoint_sublist<int> (values, indices);
println! values;
free values
end
- Output:
$ patscc -DATS_MEMALLOC_GCBDW -O3 sort_disjoint_sublist_task.dats -lgc && ./a.out 7, 6, 5, 4, 3, 2, 1, 0 7, 0, 5, 4, 3, 2, 1, 6
AutoHotkey
Sort_disjoint_sublist(Values, Indices){
A := [], B:=[], C := [], D := []
for k, v in Indices
A[v] := 1 , B[Values[v]] := v
for k, v in A
C.Push(k)
for k, v in B
D.Push(k)
for k, v in D
Values[C[A_Index]] := D[A_Index]
return Values
}
Examples:
Values := [7, 6, 5, 4, 3, 2, 1, 0]
Indices := [7, 2, 8]
Values := Sort_disjoint_sublist(Values, Indices)
for k, v in Values
output .= v ", "
MsgBox % "[" Trim(output, ", ") "]" ; show output
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
BASIC
Applesoft BASIC
The GW-BASIC solution works without any changes.
BBC BASIC
INSTALL @lib$+"SORTLIB"
Sort% = FN_sortinit(0,0) : REM Ascending
DIM list%(7) : list%() = 7, 6, 5, 4, 3, 2, 1, 0
DIM indices%(2) : indices%() = 6, 1, 7
PROCsortdisjoint(list%(), indices%())
PRINT FNshowlist(list%())
END
DEF PROCsortdisjoint(l%(), i%())
LOCAL C%, i%, n%, t%()
n% = DIM(i%(),1)
DIM t%(n%)
FOR i% = 0 TO n%
t%(i%) = l%(i%(i%))
NEXT
C% = n% + 1
CALL Sort%, i%(0)
CALL Sort%, t%(0)
FOR i% = 0 TO n%
l%(i%(i%)) = t%(i%)
NEXT
ENDPROC
DEF FNshowlist(l%())
LOCAL i%, o$
o$ = "["
FOR i% = 0 TO DIM(l%(),1)
o$ += STR$(l%(i%)) + ", "
NEXT
= LEFT$(LEFT$(o$)) + "]"
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Chipmunk Basic
The GW-BASIC solution works without any changes.
100 cls
110 dim values(7)
120 data 7,6,5,4,3,2,1,0
130 for i = 0 to 7
140 read values(i)
150 next
160 dim indices(2)
170 data 6,1,7
180 for i = 0 to 2
190 read indices(i)
200 next
210 print "Before sort:"
220 for i = 0 to ubound(values)
230 print values(i);
240 next i
250 print
260 print
270 print "After sort:"
280 for i = 0 to 1
290 if values(indices(i)) > values(indices(i+1)) then
300 temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp
310 endif
320 next i
330 for i = 0 to ubound(values)
340 print values(i);
350 next i
360 print
370 end
- Output:
Same as FreeBASIC entry.
FreeBASIC
dim as integer value(0 to 7) = {7, 6, 5, 4, 3, 2, 1, 0}
dim as integer index(0 to 2) = {6, 1, 7}, i
for i = 0 to 1
if value(index(i))>value(index(i+1)) then
swap value(index(i)), value(index(i+1))
end if
next i
for i = 0 to 7
print value(i);
next i : print
- Output:
7 0 5 4 3 2 1 6
GW-BASIC
100 CLS : rem 100 HOME for Applesoft BASIC
110 DIM V(7)
120 DATA 7,6,5,4,3,2,1,0
130 FOR C = 0 TO 7
140 READ V(C)
150 NEXT C
160 DIM I(2)
170 DATA 6,1,7
180 FOR C = 0 TO 2
190 READ I(C)
200 NEXT C
210 PRINT "Before sort:"
220 FOR C = 0 TO 7
230 PRINT V(C); " ";
240 NEXT C
250 PRINT
260 PRINT
270 PRINT "After sort:"
280 FOR C = 0 TO 1
290 IF V(I(C)) > V(I(C+1)) THEN LET T = V(I(C)) : LET V(I(C)) = V(I(C+1)) : LET V(I(C+1)) = T
300 NEXT C
310 FOR C = 0 TO 7
320 PRINT V(C); " ";
330 NEXT C
340 END
- Output:
Same as FreeBASIC entry.
Minimal BASIC
110 DIM V(7)
120 DATA 7,6,5,4,3,2,1,0
130 FOR C = 0 TO 7
140 READ V(C)
150 NEXT C
160 DIM I(2)
170 DATA 6,1,7
180 FOR C = 0 TO 2
190 READ I(C)
200 NEXT C
210 PRINT "BEFORE SORT:"
220 FOR C = 0 TO 7
230 PRINT V(C);" ";
240 NEXT C
250 PRINT
260 PRINT
270 PRINT "AFTER SORT:"
280 FOR C = 0 TO 1
290 IF V(I(C)) > V(I(C+1)) THEN 310
300 GOTO 340
310 LET T = V(I(C))
320 LET V(I(C)) = V(I(C+1))
330 LET V(I(C+1)) = T
340 NEXT C
350 FOR C = 0 TO 7
360 PRINT V(C);" ";
370 NEXT C
380 END
- Output:
Same as FreeBASIC entry.
MSX Basic
The GW-BASIC solution works without any changes.
PureBasic
Based on the C implementation
Procedure Bubble_sort(Array idx(1), n, Array buf(1))
Protected i, j
SortArray(idx(),#PB_Sort_Ascending)
For i=0 To n
For j=i+1 To n
If buf(idx(j)) < buf(idx(i))
Swap buf(idx(j)), buf(idx(i))
EndIf
Next
Next
EndProcedure
Procedure main()
DataSection
values: Data.i 7, 6, 5, 4, 3, 2, 1, 0
indices:Data.i 6, 1, 7
EndDataSection
Dim values.i(7) :CopyMemory(?values, @values(), SizeOf(Integer)*8)
Dim indices.i(2):CopyMemory(?indices,@indices(),SizeOf(Integer)*3)
If OpenConsole()
Protected i
PrintN("Before sort:")
For i=0 To ArraySize(values())
Print(Str(values(i))+" ")
Next
PrintN(#CRLF$+#CRLF$+"After sort:")
Bubble_sort(indices(), ArraySize(indices()), values())
For i=0 To ArraySize(values())
Print(Str(values(i))+" ")
Next
Print(#CRLF$+#CRLF$+"Press ENTER to exit")
Input()
EndIf
EndProcedure
main()
- Output:
Before sort: 7 6 5 4 3 2 1 0 After sort: 7 0 5 4 3 2 1 6
Run BASIC
Normally we sort with SQLite in memory. Faster and less code
sortData$ = "7, 6, 5, 4, 3, 2, 1, 0"
sortIdx$ = "7, 2, 8"
numSort = 8
dim sortData(numSort)
for i = 1 to numSort
sortData(i) = val(word$(sortData$,i,","))
next i
while word$(sortIdx$,s + 1) <> ""
s = s + 1
idx = val(word$(sortIdx$,s))
gosub [bubbleSort]
wend
end
[bubbleSort]
sortSw = 1
while sortSw = 1
sortSw = 0
for i = idx to numSort - 1 ' start sorting at idx
if sortData(i) > sortData(i+1) then
sortSw = 1
sortHold = sortData(i)
sortData(i) = sortData(i+1)
sortData(i+1) = sortHold
end if
next i
wend
RETURN
True BASIC
OPTION BASE 0
SUB SWAP(vb1, vb2)
LET temp = vb1
LET vb1 = vb2
LET vb2 = temp
END SUB
DIM values(7)
DATA 7, 6, 5, 4, 3, 2, 1, 0
FOR i = 0 TO 7
READ values(i)
NEXT i
DIM indices(2)
DATA 6, 1, 7
FOR i = 0 TO 2
READ indices(i)
NEXT i
PRINT "Before sort:"
FOR i = 0 TO 7 !UBOUND(values)
PRINT values(i);
NEXT i
PRINT
PRINT
PRINT "After sort:"
FOR i = 0 TO 1
IF values(indices(i)) > values(indices(i+1)) THEN CALL SWAP (values(indices(i)), values(indices(i+1)))
NEXT i
FOR i = 0 TO 7 !UBOUND(values)
PRINT values(i);
NEXT i
END
- Output:
Same as BASIC entry.
Yabasic
dim values(7)
values(0) = 7 : values(1) = 6 : values(2) = 5
values(3) = 4 : values(4) = 3 : values(5) = 2
values(6) = 1 : values(7) = 0
dim indices(2)
indices(0) = 6 : indices(1) = 1 : indices(2) = 7
print "Before sort:"
for i = 0 to arraysize(values(),1)
print values(i), " ";
next i
print "\n\nAfter sort:"
for i = 0 to 1
if values(indices(i)) > values(indices(i + 1)) then
temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp
end if
next i
for i = 0 to arraysize(values(),1)
print values(i), " ";
next i
end
- Output:
Same as BASIC entry.
Bracmat
7 6 5 4 3 2 1 0:?values
& 6 1 7:?indices
& 0:?sortedValues:?sortedIndices
& whl
' ( !indices:%?i ?indices
& !values:? [!i %@?value ?
& (!value.)+!sortedValues:?sortedValues
& (!i.)+!sortedIndices:?sortedIndices
)
& whl
' ( !sortedIndices:(?i.)+?sortedIndices
& !values:?A [!i %@? ?Z
& !sortedValues:(?value.)+?sortedValues
& !A !value !Z:?values
)
& out$!values;
- Output:
7 0 5 4 3 2 1 6
C
#include <stdio.h>
/* yes, bubble sort */
void bubble_sort(int *idx, int n_idx, int *buf)
{
int i, j, tmp;
#define for_ij for (i = 0; i < n_idx; i++) for (j = i + 1; j < n_idx; j++)
#define sort(a, b) if (a < b) { tmp = a; a = b; b = tmp;}
for_ij { sort(idx[j], idx[i]); }
for_ij { sort(buf[idx[j]], buf[idx[i]]);}
#undef for_ij
#undef sort
}
int main()
{
int values[] = {7, 6, 5, 4, 3, 2, 1, 0};
int idx[] = {6, 1, 7};
int i;
printf("before sort:\n");
for (i = 0; i < 8; i++)
printf("%d ", values[i]);
printf("\n\nafter sort:\n");
bubble_sort(idx, 3, values);
for (i = 0; i < 8; i++)
printf("%d ", values[i]);
printf("\n");
return 0;
}
C#
using System;
using System.Linq;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
var list = new List<int>{ 7, 6, 5, 4, 3, 2, 1, 0 };
list.SortSublist(6, 1, 7);
Console.WriteLine(string.Join(", ", list));
}
}
public static class Extensions
{
public static void SortSublist<T>(this List<T> list, params int[] indices)
where T : IComparable<T>
{
var sublist = indices.OrderBy(i => i)
.Zip(indices.Select(i => list[i]).OrderBy(v => v),
(Index, Value) => new { Index, Value });
foreach (var entry in sublist) {
list[entry.Index] = entry.Value;
}
}
}
C++
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
template <typename ValueIterator, typename IndicesIterator>
void sortDisjoint(ValueIterator valsBegin, IndicesIterator indicesBegin,
IndicesIterator indicesEnd) {
std::vector<int> temp;
for (IndicesIterator i = indicesBegin; i != indicesEnd; ++i)
temp.push_back(valsBegin[*i]); // extract
std::sort(indicesBegin, indicesEnd); // sort
std::sort(temp.begin(), temp.end()); // sort a C++ container
std::vector<int>::const_iterator j = temp.begin();
for (IndicesIterator i = indicesBegin; i != indicesEnd; ++i, ++j)
valsBegin[*i] = *j; // replace
}
int main()
{
int values[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
int indices[] = { 6, 1, 7 };
sortDisjoint(values, indices, indices+3);
std::copy(values, values + 8, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
return 0;
}
- Output:
7 0 5 4 3 2 1 6
Solution that sorts using a custom iterator that iterates a disjoint sublist.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
template <typename ValueIterator, typename IndicesIterator>
struct DisjointSubsetIterator :
public std::iterator<std::random_access_iterator_tag,
typename std::iterator_traits<ValueIterator>::value_type> {
typedef typename std::iterator_traits<ValueIterator>::value_type V;
ValueIterator valsBegin;
IndicesIterator i;
DisjointSubsetIterator() { }
DisjointSubsetIterator(const ValueIterator &_v, IndicesIterator _i) :
valsBegin(_v), i(_i) { }
DisjointSubsetIterator& operator++() { ++i; return *this; }
DisjointSubsetIterator operator++(int) {
DisjointSubsetIterator tmp = *this; ++(*this); return tmp; }
bool operator==(const DisjointSubsetIterator& y) { return i == y.i; }
bool operator!=(const DisjointSubsetIterator& y) { return i != y.i; }
V &operator*() { return valsBegin[*i]; }
DisjointSubsetIterator& operator--() { --i; return *this; }
DisjointSubsetIterator operator--(int) {
DisjointSubsetIterator tmp = *this; --(*this); return tmp; }
DisjointSubsetIterator& operator+=(int n) { i += n; return *this; }
DisjointSubsetIterator& operator-=(int n) { i -= n; return *this; }
DisjointSubsetIterator operator+(int n) {
DisjointSubsetIterator tmp = *this; return tmp += n; }
DisjointSubsetIterator operator-(int n) {
DisjointSubsetIterator tmp = *this; return tmp -= n; }
int operator-(const DisjointSubsetIterator &y) { return i - y.i; }
V &operator[](int n) { return *(*this + n); }
bool operator<(const DisjointSubsetIterator &y) { return i < y.i; }
bool operator>(const DisjointSubsetIterator &y) { return i > y.i; }
bool operator<=(const DisjointSubsetIterator &y) { return i <= y.i; }
bool operator>=(const DisjointSubsetIterator &y) { return i >= y.i; }
};
template <typename ValueIterator, typename IndicesIterator>
DisjointSubsetIterator<ValueIterator, IndicesIterator>
operator+(int n, const DisjointSubsetIterator<ValueIterator, IndicesIterator> &i) {
return i + n; }
template <typename ValueIterator, typename IndicesIterator>
void sortDisjoint(ValueIterator valsBegin, IndicesIterator indicesBegin,
IndicesIterator indicesEnd) {
std::sort(DisjointSubsetIterator<ValueIterator, IndicesIterator>(valsBegin, indicesBegin),
DisjointSubsetIterator<ValueIterator, IndicesIterator>(valsBegin, indicesEnd));
}
int main()
{
int values[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
int indices[] = { 6, 1, 7 };
sortDisjoint(values, indices, indices+3);
std::copy(values, values + 8, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
return 0;
}
- Output:
7 0 5 4 3 2 1 6
Clojure
(defn disjoint-sort [coll idxs]
(let [val-subset (keep-indexed #(when ((set idxs) %) %2) coll)
replacements (zipmap (set idxs) (sort val-subset))]
(apply assoc coll (flatten (seq replacements)))))
- Output:
user=> (disjoint-sort [7 6 5 4 3 2 1 0] #{6 1 7}) [7 0 5 4 3 2 1 6]
Common Lisp
(defun disjoint-sort (values indices)
"Destructively perform a disjoin sublist sort on VALUES with INDICES."
(loop :for element :in
(sort (loop :for index :across indices
:collect (svref values index))
'<)
:for index :across (sort indices '<)
:do (setf (svref values index) element))
values)
- Output:
CL-USER> (disjoint-sort #(7 6 5 4 3 2 1 0) #(6 1 7)) #(7 0 5 4 3 2 1 6)
D
import std.algorithm, std.range, std.array;
void main() {
auto data = [7, 6, 5, 4, 3, 2, 1, 0];
auto indices = [6, 1, 7];
data.indexed(indices.sort()).sort();
assert(data == [7, 0, 5, 4, 3, 2, 1, 6]);
}
Lower Level version
import std.algorithm: swap;
void disjointSort(T, U)(T[] arr, U[] indexes)
in {
if (arr.length == 0)
assert(indexes.length == 0);
else {
foreach (idx; indexes)
assert(idx >= 0 && idx < arr.length);
}
} body {
void quickSort(U* left, U* right) {
if (right > left) {
auto pivot = arr[left[(right - left) / 2]];
auto r = right, l = left;
do {
while (arr[*l] < pivot) l++;
while (arr[*r] > pivot) r--;
if (l <= r) {
swap(arr[*l], arr[*r]);
swap(l, r);
l++;
r--;
}
} while (l <= r);
quickSort(left, r);
quickSort(l, right);
}
}
if (arr.length == 0 || indexes.length == 0)
return;
quickSort(&indexes[0], &indexes[$-1]);
}
void main() {
auto data = [7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0];
auto indexes = [6, 1, 1, 7];
disjointSort(data, indexes);
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]);
}
Simple Alternative Version
import std.stdio, std.algorithm;
void main() {
auto data = [7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0, 0.0];
auto indexes = [6, 1, 1, 7]; // One duplicated added to test.
// Remove duplicates, in place:
indexes.length -= indexes.sort().uniq().copy(indexes).length;
foreach (i, idx; indexes)
swap(data[i], data[idx]);
data[0 .. indexes.length].sort();
foreach_reverse (i, idx; indexes)
swap(data[idx], data[i]);
assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]);
}
Delphi
{Test values}
var Values: array [0..7] of integer = (7, 6, 5, 4, 3, 2, 1, 0);
var indices: array [0..2] of integer = (6, 1, 7);
function CompareValues(Item1, Item2: Pointer): Integer;
{Compare the values pointed to by the indices}
begin
Result:=Values[integer(Item1)]-Values[integer(Item2)];
end;
function CompareIndices(Item1, Item2: Pointer): Integer;
{Compare the indices themselves}
begin
Result:=integer(Item1)-integer(Item2);
end;
procedure SortDisjointSublist(Memo: TMemo);
var L1,L2: TList;
var I,Inx1,Inx2: integer;
var OutList: TIntegerDynArray;
var S: string;
begin
L1:=TList.Create;
L2:=TList.Create;
try
{Copy values array to output array}
SetLength(OutList,Length(Values));
for I:=0 to High(Values) do OutList[I]:=Values[I];
{Load two lists with the indices}
for I:=0 to High(Indices) do
begin
L1.Add(Pointer(Indices[I]));
L2.Add(Pointer(Indices[I]));
end;
{Sort by index and by value}
L1.Sort(CompareValues);
L2.Sort(CompareIndices);
{Copy the sorted values through the sorted indices}
for I:=0 to L1.Count-1 do
OutList[Integer(L2[I])]:=Values[Integer(L1[I])];
{Display the result}
S:='[';
for I:=0 to High(OutLIst) do
begin
if I>0 then S:=S+' ';
S:=S+IntToStr(OutList[I]);
end;
S:=S+']';
Memo.Lines.Add(S);
finally
L1.Free;
L2.Free;
end;
end;
- Output:
[7 0 5 4 3 2 1 6]
Elapsed Time: 0.626 ms.
EasyLang
val[] = [ 7 6 5 4 3 2 1 0 ]
ind[] = [ 7 2 8 ]
#
for i = 1 to len ind[] - 1
for j = i + 1 to len ind[]
if ind[j] < ind[i]
swap ind[j] ind[i]
.
.
.
for i = 1 to len ind[] - 1
for j = i + 1 to len ind[]
if val[ind[j]] < val[ind[i]]
swap val[ind[j]] val[ind[i]]
.
.
.
print val[]
EchoLisp
(define (sort-disjoint values indices)
(define sorted (list-sort <
(for/list [(v values) (i (in-naturals))]
#:when (member i indices) v)))
(for/list [(v values) (i (in-naturals))]
(if (not (member i indices)) v
(begin0
(first sorted)
(set! sorted (rest sorted))))))
(define (task)
(sort-disjoint '[7 6 5 4 3 2 1 0] {6 1 7}))
(task)
→ (7 0 5 4 3 2 1 6)
Elena
ELENA 6.x :
import extensions;
import system'routines;
import system'culture;
extension op
{
sortSublist(indices)
{
var subList := indices.orderBy::(x => x)
.zipBy(indices.selectBy::(i => self[i])
.orderBy::(x => x), (index,val => new{ Index = index; Value = val; }))
.toArray();
var list := self.clone();
subList.forEach::(r)
{
list[r.Index] := r.Value
};
^ list
}
}
public program()
{
var list := new int[]{ 7, 6, 5, 4, 3, 2, 1, 0 };
console.printLine(list.sortSublist(new int[]{6, 1, 7}).asEnumerable())
}
- Output:
7,0,5,4,3,2,1,6
Elixir
defmodule Sort_disjoint do
def sublist(values, indices) when is_list(values) and is_list(indices) do
indices2 = Enum.sort(indices)
selected = select(values, indices2, 0, []) |> Enum.sort
replace(values, Enum.zip(indices2, selected), 0, [])
end
defp select(_, [], _, selected), do: selected
defp select([val|t], [i|rest], i, selected), do: select(t, rest, i+1, [val|selected])
defp select([_|t], indices, i, selected), do: select(t, indices, i+1, selected)
defp replace(values, [], _, list), do: Enum.reverse(list, values)
defp replace([_|t], [{i,v}|rest], i, list), do: replace(t, rest, i+1, [v|list])
defp replace([val|t], indices, i, list), do: replace(t, indices, i+1, [val|list])
end
values = [7, 6, 5, 4, 3, 2, 1, 0]
indices = [6, 1, 7]
IO.inspect Sort_disjoint.sublist(values, indices)
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Erlang
-module( sort_disjoint ).
-export( [sublist/2, task/0] ).
sublist( Values, Indices ) ->
Sorted_indices = lists:sort( Indices ),
Values_indexes = lists:seq( 1, erlang:length(Values) ),
{[], [], Indices_values} = lists:foldl( fun indices_values/2, {Values, Sorted_indices, []}, Values_indexes ),
Sorted_indices_values = lists:zip( Sorted_indices, lists:sort(Indices_values) ),
{Sorted_values, {[], []}} = lists:mapfoldl( fun merge/2, {Values, Sorted_indices_values}, Values_indexes ),
Sorted_values.
task() -> sublist( [7, 6, 5, 4, 3, 2, 1, 0], [7, 2, 8] ).
indices_values( Index, {[H | Values], [Index | Indices], Indices_values} ) -> {Values, Indices, [H | Indices_values]};
indices_values( _Index, {[_H | Values], Indices, Indices_values} ) -> {Values, Indices, Indices_values}.
merge( Index, {[_H | Values], [{Index, Value} | Sorted_indices_values]} ) -> {Value, {Values, Sorted_indices_values}};
merge( _Index, {[H | Values], Sorted_indices_values} ) -> {H, {Values, Sorted_indices_values}}.
- Output:
20> sort_disjoint:task(). [7,0,5,4,3,2,1,6]
ERRE
PROGRAM DISJOINT
DIM LST%[7],INDICES%[2]
DIM L%[7],I%[2],Z%[2]
PROCEDURE SHOWLIST(L%[]->O$)
LOCAL I%
O$="["
FOR I%=0 TO UBOUND(L%,1) DO
O$=O$+STR$(L%[I%])+", "
END FOR
O$=LEFT$(O$,LEN(O$)-2)+"]"
END PROCEDURE
PROCEDURE SORT(Z%[]->Z%[])
LOCAL N%,P%,FLIPS%
P%=UBOUND(Z%,1)
FLIPS%=TRUE
WHILE FLIPS% DO
FLIPS%=FALSE
FOR N%=0 TO P%-1 DO
IF Z%[N%]>Z%[N%+1] THEN SWAP(Z%[N%],Z%[N%+1]) FLIPS%=TRUE
END FOR
END WHILE
END PROCEDURE
PROCEDURE SortDisJoint(L%[],I%[]->L%[])
LOCAL J%,N%
LOCAL DIM T%[2]
N%=UBOUND(I%,1)
FOR J%=0 TO N% DO
T%[J%]=L%[I%[J%]]
END FOR
SORT(I%[]->I%[])
SORT(T%[]->T%[])
FOR J%=0 TO N% DO
L%[I%[J%]]=T%[J%]
END FOR
END PROCEDURE
BEGIN
LST%[]=(7,6,5,4,3,2,1,0)
INDICES%[]=(6,1,7)
SortDisJoint(LST%[],INDICES%[]->LST%[])
ShowList(LST%[]->O$)
PRINT(O$)
END PROGRAM
- Output:
[ 7, 0, 5, 4, 3, 2, 1, 6]
Euphoria
include sort.e
function uniq(sequence s)
sequence out
out = s[1..1]
for i = 2 to length(s) do
if not find(s[i], out) then
out = append(out, s[i])
end if
end for
return out
end function
function disjointSort(sequence s, sequence idx)
sequence values
idx = uniq(sort(idx))
values = repeat(0, length(idx))
for i = 1 to length(idx) do
values[i] = s[idx[i]]
end for
values = sort(values)
for i = 1 to length(idx) do
s[idx[i]] = values[i]
end for
return s
end function
constant data = {7, 6, 5, 4, 3, 2, 1, 0}
constant indexes = {7, 2, 8}
- Output:
pre>{7,0,5,4,3,2,1,6}
F#
Works with arrays instead of lists because this algorithm is more efficient with a random access collection type. Returns a copy of the array, as is usually preferred in F#.
let sortDisjointSubarray data indices =
let indices = Set.toArray indices // creates a sorted array
let result = Array.copy data
Array.map (Array.get data) indices
|> Array.sort
|> Array.iter2 (Array.set result) indices
result
printfn "%A" (sortDisjointSubarray [|7;6;5;4;3;2;1;0|] (set [6;1;7]))
Factor
: disjoint-sort! ( values indices -- values' )
over <enumerated> nths unzip swap [ natural-sort ] bi@
pick [ set-nth ] curry 2each ;
- Output:
IN: scratchpad { 7 6 5 4 3 2 1 0 } { 6 1 7 } disjoint-sort! .
{ 7 0 5 4 3 2 1 6 }
Fortran
program Example
implicit none
integer :: array(8) = (/ 7, 6, 5, 4, 3, 2, 1, 0 /)
integer :: indices(3) = (/ 7, 2, 8 /)
! In order to make the output insensitive to index order
! we need to sort the indices first
call Isort(indices)
! Should work with any sort routine as long as the dummy
! argument array has been declared as an assumed shape array
! Standard insertion sort used in this example
call Isort(array(indices))
write(*,*) array
contains
subroutine Isort(a)
integer, intent(in out) :: a(:)
integer :: temp
integer :: i, j
do i = 2, size(a)
j = i - 1
temp = a(i)
do while (j>=1 .and. a(j)>temp)
a(j+1) = a(j)
j = j - 1
end do
a(j+1) = temp
end do
end subroutine Isort
end program Example
- Output:
7 0 5 4 3 2 1 6
Go
package main
import (
"fmt"
"sort"
)
func main() {
// givens
values := []int{7, 6, 5, 4, 3, 2, 1, 0}
indices := map[int]int{6: 0, 1: 0, 7: 0}
orderedValues := make([]int, len(indices))
orderedIndices := make([]int, len(indices))
i := 0
for j := range indices {
// validate that indices are within list boundaries
if j < 0 || j >= len(values) {
fmt.Println("Invalid index: ", j)
return
}
// extract elements to sort
orderedValues[i] = values[j]
orderedIndices[i] = j
i++
}
// sort
sort.Ints(orderedValues)
sort.Ints(orderedIndices)
fmt.Println("initial:", values)
// replace sorted values
for i, v := range orderedValues {
values[orderedIndices[i]] = v
}
fmt.Println("sorted: ", values)
}
- Output:
initial: [7 6 5 4 3 2 1 0] sorted: [7 0 5 4 3 2 1 6]
Alternative algorithm, sorting in place through the extra level of indirection.
Compared to the strategy of extract-sort-replace, this strategy avoids the space overhead of the work area and the time overhead of extracting and reinserting elements. At some point however, the cost of indirection multiplied by O(log n) would dominate, and extract-sort-replace would become preferable.
package main
import (
"fmt"
"sort"
)
// type and methods satisfying sort.Interface
type subListSortable struct {
values sort.Interface
indices []int
}
func (s subListSortable) Len() int {
return len(s.indices)
}
func (s subListSortable) Swap(i, j int) {
s.values.Swap(s.indices[i], s.indices[j])
}
func (s subListSortable) Less(i, j int) bool {
return s.values.Less(s.indices[i], s.indices[j])
}
func main() {
// givens
values := []int{7, 6, 5, 4, 3, 2, 1, 0}
indices := map[int]int{6: 0, 1: 0, 7: 0}
// make ordered list of indices for sort methods
ordered := make([]int, len(indices))
if len(indices) > 0 {
i := 0
for j := range indices {
ordered[i] = j
i++
}
sort.Ints(ordered)
// validate that indices are within list boundaries
if ordered[0] < 0 {
fmt.Println("Invalid index: ", ordered[0])
return
}
if ordered[len(ordered)-1] >= len(values) {
fmt.Println("Invalid index: ", ordered[len(ordered)-1])
return
}
}
// instantiate sortable type and sort
s := subListSortable{sort.IntSlice(values), ordered}
fmt.Println("initial:", s.values)
sort.Sort(s)
fmt.Println("sorted: ", s.values)
}
Groovy
Groovy allows List-valued indexing to "gather" and "scatter" arbitrary sublists, making the solution almost trivial.
def sparseSort = { a, indices = ([] + (0..<(a.size()))) ->
indices.sort().unique()
a[indices] = a[indices].sort()
a
}
Test:
def a = [7, 6, 5, 4, 3, 2, 1, 0]
println a
println sparseSort(a, []) // no indices to sort
println a
println sparseSort(a, [6,1,7]) // suggested sample indices
println a
println sparseSort(a) // default == sort all
println a
Output:
[7, 6, 5, 4, 3, 2, 1, 0] [7, 6, 5, 4, 3, 2, 1, 0] [7, 6, 5, 4, 3, 2, 1, 0] [7, 0, 5, 4, 3, 2, 1, 6] [7, 0, 5, 4, 3, 2, 1, 6] [0, 1, 2, 3, 4, 5, 6, 7] [0, 1, 2, 3, 4, 5, 6, 7]
Haskell
Here are three variations on the solution: using ordinary lists, immutable "boxed" arrays, and mutable "unboxed" arrays.
import Control.Monad
import qualified Data.Array as A
import Data.Array.IArray
import Data.Array.ST
import Data.List
import Data.List.Utils
-- Partition 'xs' according to whether their element indices are in 'is'. Sort
-- the sublist corresponding to 'is', merging the result with the remainder of
-- the list.
disSort1
:: (Ord a, Num a, Enum a, Ord b)
=> [b] -> [a] -> [b]
disSort1 xs is =
let is_ = sort is
(sub, rest) = partition ((`elem` is_) . fst) $ zip [0 ..] xs
in map snd . merge rest . zip is_ . sort $ map snd sub
-- Convert the list to an array. Extract the sublist corresponding to the
-- indices 'is'. Sort the sublist, replacing those elments in the array.
disSort2
:: (Ord a)
=> [a] -> [Int] -> [a]
disSort2 xs is =
let as = A.listArray (0, length xs - 1) xs
sub = zip (sort is) . sort $ map (as !) is
in elems $ as // sub
-- Similar to disSort2, but using mutable arrays. The sublist is updated
-- "in place", rather than creating a new array. However, this is not visible
-- to a caller.
disSort3 :: [Int] -> [Int] -> [Int]
disSort3 xs is =
elems . runSTUArray $
do as <- newListArray (0, length xs - 1) xs
sub <- (zip (sort is) . sort) Control.Applicative.<$> mapM (readArray as) is
mapM_ (uncurry (writeArray as)) sub
return as
main :: IO ()
main = do
let xs = [7, 6, 5, 4, 3, 2, 1, 0]
is = [6, 1, 7]
print $ disSort1 xs is
print $ disSort2 xs is
print $ disSort3 xs is
Or, in terms of Data.Map:
import Data.Map as M (fromList, keys, lookup)
import Control.Applicative ((<|>))
import Data.Maybe (mapMaybe)
import Data.List (sort)
disjointSort :: [Int] -> [Int] -> [Int]
disjointSort ixs xs =
let ks = sort ixs
dctAll = fromList $ zip xs [0 ..]
dctIx = fromList $ zip ks $ sort (mapMaybe (`M.lookup` dctAll) ks)
in mapMaybe
((<|>) <$> (`M.lookup` dctIx) <*> (`M.lookup` dctAll))
(keys dctAll)
main :: IO ()
main = print $ disjointSort [6, 1, 7] [7, 6, 5, 4, 3, 2, 1, 0]
- Output:
[7,0,5,4,3,2,1,6]
Icon and Unicon
Icon's lists are 1-based, so the example uses (7, 2, 8) as the indices, not (6, 1 7).
- Output:
7 6 5 4 3 2 1 02 7 8
7 0 5 4 3 2 1 6
The expression !indices
generates the value of each index in turn, so the line
effectively loops through each index, putting result[index]
into the list 'values'.
Io
Io does not come with a set type.
List disjointSort := method(indices,
sortedIndices := indices unique sortInPlace
sortedValues := sortedIndices map(idx,at(idx)) sortInPlace
sortedValues foreach(i,v,atPut(sortedIndices at(i),v))
self
)
list(7,6,5,4,3,2,1,0) disjointSort(list(6,1,7)) println
- Output:
list(7, 0, 5, 4, 3, 2, 1, 6)
J
Note that the task requires us to ignore the order of the indices.
7 6 5 4 3 2 1 0 (/:~@:{`[`]}~ /:~@~.) 6 1 7
7 0 5 4 3 2 1 6
Compare this with:
6 1 7 /:~@:{`[`]} 7 6 5 4 3 2 1 0
7 1 5 4 3 2 0 6
Here, the order of the indices specifies the order we want the selected items to be sorted in: 7 1 5 4 3 2 0 6
Java
This function will modify the index array and the values list.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Disjoint {
public static <T extends Comparable<? super T>> void sortDisjoint(
List<T> array, int[] idxs) {
Arrays.sort(idxs);
List<T> disjoint = new ArrayList<T>();
for (int idx : idxs) {
disjoint.add(array.get(idx));
}
Collections.sort(disjoint);
int i = 0;
for (int idx : idxs) {
array.set(idx, disjoint.get(i++));
}
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0);
int[] indices = {6, 1, 7};
System.out.println(list);
sortDisjoint(list, indices);
System.out.println(list);
}
}
- Output:
[7, 6, 5, 4, 3, 2, 1, 0] [7, 0, 5, 4, 3, 2, 1, 6]
Shorter solution that sorts a list "wrapper" which represents a "view" into the disjoint sublist of the list.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.AbstractList;
public class Disjoint {
public static <T extends Comparable<? super T>> void sortDisjoint(
final List<T> array, final int[] idxs) {
Arrays.sort(idxs);
Collections.sort(new AbstractList<T>() {
public int size() { return idxs.length; }
public T get(int i) { return array.get(idxs[i]); }
public T set(int i, T x) { return array.set(idxs[i], x); }
});
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0);
int[] indices = {6, 1, 7};
System.out.println(list);
sortDisjoint(list, indices);
System.out.println(list);
}
}
- Output:
[7, 6, 5, 4, 3, 2, 1, 0] [7, 0, 5, 4, 3, 2, 1, 6]
JavaScript
ES5
Iterative
Does not check for duplicate indices.
function sort_disjoint(values, indices) {
var sublist = [];
indices.sort(function(a, b) { return a > b; });
for (var i = 0; i < indices.length; i += 1) {
sublist.push(values[indices[i]]);
}
sublist.sort(function(a, b) { return a < b; });
for (var i = 0; i < indices.length; i += 1) {
values[indices[i]] = sublist.pop();
}
return values;
}
Functional
(function () {
'use strict';
// disjointSort :: [a] -> [Int] -> [a]
function disjointSort(xs, indices) {
// Sequence of indices discarded
var indicesSorted = indices.sort(),
subsetSorted = indicesSorted
.map(function (i) {
return xs[i];
})
.sort();
return xs
.map(function (x, i) {
var iIndex = indicesSorted.indexOf(i);
return iIndex !== -1 ? (
subsetSorted[iIndex]
) : x;
});
}
return disjointSort([7, 6, 5, 4, 3, 2, 1, 0], [6, 1, 7])
})();
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
ES6
(() => {
'use strict';
// disjointSort :: [Int] -> [Int] -> [Int]
const disjointSort = (indices, xs) => {
const
ks = sort(indices),
dct = mapFromList(
zip(ks, sort(map(k => xs[k], ks)))
);
return map(
(x, i) => {
const v = dct[i.toString()];
return undefined !== v ? v : x;
},
xs
);
};
// main :: IO ()
const main = () =>
showLog(
disjointSort(
[6, 1, 7],
[7, 6, 5, 4, 3, 2, 1, 0]
)
);
// GENERIC FUNCTIONS ----------------------------
// length :: [a] -> Int
const length = xs => xs.length || Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
// mapFromList :: [(k, v)] -> Dict
const mapFromList = kvs =>
kvs.reduce(
(a, kv) => {
const k = kv[0];
return Object.assign(a, {
[(('string' === typeof k) && k) || showJSON(k)]: kv[1]
});
}, {}
);
// showJSON :: a -> String
const showJSON = x => JSON.stringify(x);
// showLog :: a -> IO ()
const showLog = (...args) =>
console.log(
args
.map(JSON.stringify)
.join(' -> ')
);
// sort :: Ord a => [a] -> [a]
const sort = xs => xs.slice()
.sort((a, b) => a < b ? -1 : (a > b ? 1 : 0));
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = (n, xs) =>
xs.constructor.constructor.name !== 'GeneratorFunction' ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// Tuple (,) :: a -> b -> (a, b)
const Tuple = (a, b) => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// Use of `take` and `length` here allows for zipping with non-finite
// lists - i.e. generators like cycle, repeat, iterate.
// zip :: [a] -> [b] -> [(a, b)]
const zip = (xs, ys) => {
const lng = Math.min(length(xs), length(ys));
return Infinity !== lng ? (() => {
const bs = take(lng, ys);
return take(lng, xs).map((x, i) => Tuple(x, bs[i]));
})() : zipGen(xs, ys);
};
// MAIN ---
return main();
})();
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
jq
We define a jq function, disjointSort, that accepts the array of values as input, but for clarity we first define a utility function for updating an array at multiple places:
def setpaths(indices; values):
reduce range(0; indices|length) as $i
(.; .[indices[$i]] = values[$i]);
def disjointSort(indices):
(indices|unique) as $ix # "unique" sorts
# Set $sorted to the sorted array of values at $ix:
| ([ .[ $ix[] ] ] | sort) as $sorted
| setpaths( $ix; $sorted) ;
Example:
[7, 6, 5, 4, 3, 2, 1, 0] | disjointSort( [6, 1, 7] )
produces:
[7,0,5,4,3,2,1,6]
Julia
function sortselected(a::AbstractVector{<:Real}, s::AbstractVector{<:Integer})
sel = unique(sort(s))
if sel[1] < 1 || length(a) < sel[end]
throw(BoundsError())
end
b = collect(copy(a))
b[sel] = sort(b[sel])
return b
end
a = [7, 6, 5, 4, 3, 2, 1, 0]
sel = [7, 2, 8]
b = sortselected(a, sel)
println("Original: $a\n\tsorted on $sel\n -> sorted array: $b")
- Output:
Original: [7, 6, 5, 4, 3, 2, 1, 0] sorted on [7, 2, 8] -> sorted array: [7, 0, 5, 4, 3, 2, 1, 6]
K
{@[x;y@<y;:;a@<a:x@y]}[7 6 5 4 3 2 1 0;6 1 7]
7 0 5 4 3 2 1 6
Another way
sort : {x[<x]}
nums : 7 6 5 4 3 2 1 0
i : sort 6 1 7
nums[i] : sort nums[i]
nums
7 0 5 4 3 2 1 6
Kotlin
// version 1.1.51
/* in place sort */
fun IntArray.sortDisjoint(indices: Set<Int>) {
val sortedSubset = this.filterIndexed { index, _ -> index in indices }.sorted()
if (sortedSubset.size < indices.size)
throw IllegalArgumentException("Argument set contains out of range indices")
indices.sorted().forEachIndexed { index, value -> this[value] = sortedSubset[index] }
}
fun main(args: Array<String>) {
val values = intArrayOf(7, 6, 5, 4, 3, 2, 1, 0)
val indices = setOf(6, 1, 7)
println("Original array : ${values.asList()} sorted on indices $indices")
values.sortDisjoint(indices)
println("Sorted array : ${values.asList()}")
}
- Output:
Original array : [7, 6, 5, 4, 3, 2, 1, 0] sorted on indices [6, 1, 7] Sorted array : [7, 0, 5, 4, 3, 2, 1, 6]
Ksh
#!/bin/ksh
# Sort disjoint sublist
# # Variables:
#
typeset -a arr_Val=( 7 6 5 4 3 2 1 0 )
typeset -a arr_Ind=( 6 1 7 )
integer i
# # Functions:
#
# # Function _insertionSort(array) - Insertion sort of array of integers
#
function _insertionSort {
typeset _arr ; nameref _arr="$1"
typeset _i _j _val ; integer _i _j _val
for (( _i=1; _i<${#_arr[*]}; _i++ )); do
_val=${_arr[_i]}
(( _j = _i - 1 ))
while (( _j>=0 && _arr[_j]>_val )); do
_arr[_j+1]=${_arr[_j]}
(( _j-- ))
done
_arr[_j+1]=${_val}
done
}
######
# main #
######
print "Before sort: ${arr_Val[*]}"
typeset -a arr_2sort
for ((i=0; i<${#arr_Ind[*]}; i++)); do
arr_2sort+=( ${arr_Val[${arr_Ind[i]}]} )
done
_insertionSort arr_2sort # Sort the chosen values
_insertionSort arr_Ind # Sort the indices
for ((i=0; i<${#arr_Ind[*]}; i++)); do
arr_Val[${arr_Ind[i]}]=${arr_2sort[i]}
done
print "After sort: ${arr_Val[*]}"
- Output:
Before sort: 7 6 5 4 3 2 1 0
After sort: 7 0 5 4 3 2 1 6
Lua
values = { 7, 6, 5, 4, 3, 2, 1, 0 }
indices = { 6, 1, 7 }
i = 1 -- discard duplicates
while i < #indices do
j = i + 1
while j < #indices do
if indices[i] == indices[j] then
table.remove( indices[j] )
end
j = j + 1
end
i = i + 1
end
for i = 1, #indices do
indices[i] = indices[i] + 1 -- the tables of lua are one-based
end
vals = {}
for i = 1, #indices do
vals[i] = values[ indices[i] ]
end
table.sort( vals )
table.sort( indices )
for i = 1, #indices do
values[ indices[i] ] = vals[i]
end
for i = 1, #values do
io.write( values[i], " " )
end
- Output:
7 0 5 4 3 2 1 6
Maple
sortDisjoint := proc(values, indices::set)
local vals,inds,i:
vals := sort([seq(values[i], i in indices)]):
inds := sort(convert(indices, Array)):
for i to numelems(vals) do
values(inds[i]) := vals[i]:
od:
end proc:
tst := Array([7,6,5,4,3,2,1,0]):
sortDisjoint(tst,{7,2,8});
- Output:
[7 0 5 4 3 2 1 6]
Mathematica /Wolfram Language
Values = { 7, 6, 5, 4, 3, 2, 1, 0} ; Indices = { 7, 2, 8 };
Values[[Sort[Indices]]] = Sort[Values[[Indices]]];
Values
- Output:
{ 7, 0, 5, 4, 3, 2, 1, 6 }
MiniScript
sortDisjointSublist = function(arr, indexes)
indexes.sort
newArr = arr[:]
sublist = []
for i in indexes
sublist.push(arr[i])
end for
sublist.sort
for i in range(0, indexes.len - 1)
arrIx = indexes[i]
newArr[arrIx] = sublist[i]
end for
return newArr
end function
print sortDisjointSublist([7,6,5,4,3,2,1,0], [6,1,7])
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
NetRexx
/* NetRexx */
options replace format comments java crossref symbols nobinary
runSample(arg)
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method sortDisjoint(oldList, indices) public static
newList = oldList.space()
if indices.words() > 1 then do -- only do work if we need to
subList = ArrayList()
idxList = ArrayList()
-- pick the input list apart
loop ix = 1 to indices.words()
iw = indices.word(ix)
nw = oldList.word(iw)
-- protect against bad outcomes...
if iw > oldList.words() then signal ArrayIndexOutOfBoundsException()
if iw < 1 then signal ArrayIndexOutOfBoundsException()
subList.add(nw)
idxList.add(iw)
end ix
Collections.sort(subList) -- sort sublist
Collections.sort(idxList) -- sort indices
-- put it all back together
loop kx = 0 to subList.size() - 1
kk = Rexx subList.get(kx)
ii = Rexx idxList.get(kx)
newList = newList.subword(1, ii - 1) kk newList.subword(ii + 1)
end kx
end
return newList
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
parse arg vList ',' iList
if vList = '' then vList = 7 6 5 4 3 2 1 0
if iList = '' then iList = 7 2 8
rList = sortDisjoint(vList, iList)
say 'In: ' vList.space
say 'Out:' rList.space
say 'Idx:' iList.space
return
- Output:
In: 7 6 5 4 3 2 1 0 Out: 7 0 5 4 3 2 1 6 Idx: 7 2 8
Nial
values := [7, 6, 5, 4, 3, 2, 1, 0]
indices := sortup [6, 1, 7]
values#indices := sortup values#indices
7 0 5 4 3 2 1 6
Nim
import algorithm
proc sortDisjoinSublist[T](data: var seq[T], indices: seq[int]) =
var indices = indices
sort indices, cmp[T]
var values: seq[T] = @[]
for i in indices: values.add data[i]
sort values, cmp[T]
for j, i in indices: data[i] = values[j]
var d = @[7, 6, 5, 4, 3, 2, 1, 0]
sortDisjoinSublist(d, @[6, 1, 7])
echo d
- Output:
@[7, 0, 5, 4, 3, 2, 1, 6]
Objective-C
Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array.
#import <Foundation/Foundation.h>
@interface DisjointSublistView : NSMutableArray {
NSMutableArray *array;
int *indexes;
int num_indexes;
}
- (instancetype)initWithArray:(NSMutableArray *)a andIndexes:(NSIndexSet *)ind;
@end
@implementation DisjointSublistView
- (instancetype)initWithArray:(NSMutableArray *)a andIndexes:(NSIndexSet *)ind {
if ((self = [super init])) {
array = a;
num_indexes = [ind count];
indexes = malloc(num_indexes * sizeof(int));
for (NSUInteger i = [ind firstIndex], j = 0; i != NSNotFound; i = [ind indexGreaterThanIndex:i], j++)
indexes[j] = i;
}
return self;
}
- (void)dealloc {
free(indexes);
}
- (NSUInteger)count { return num_indexes; }
- (id)objectAtIndex:(NSUInteger)i { return array[indexes[i]]; }
- (void)replaceObjectAtIndex:(NSUInteger)i withObject:(id)x { array[indexes[i]] = x; }
@end
@interface NSMutableArray (SortDisjoint)
- (void)sortDisjointSublist:(NSIndexSet *)indexes usingSelector:(SEL)comparator;
@end
@implementation NSMutableArray (SortDisjoint)
- (void)sortDisjointSublist:(NSIndexSet *)indexes usingSelector:(SEL)comparator {
DisjointSublistView *d = [[DisjointSublistView alloc] initWithArray:self andIndexes:indexes];
[d sortUsingSelector:comparator];
}
@end
int main(int argc, const char *argv[]) {
@autoreleasepool {
NSMutableArray *a = [@[@7, @6, @5, @4, @3, @2, @1, @0] mutableCopy];
NSMutableIndexSet *ind = [NSMutableIndexSet indexSet];
[ind addIndex:6]; [ind addIndex:1]; [ind addIndex:7];
[a sortDisjointSublist:ind usingSelector:@selector(compare:)];
NSLog(@"%@", a);
}
return 0;
}
- Output:
( 7, 0, 5, 4, 3, 2, 1, 6 )
OCaml
With arrays:
let disjoint_sort cmp values indices =
let temp = Array.map (Array.get values) indices in
Array.sort cmp temp;
Array.sort compare indices;
Array.iteri (fun i j -> values.(j) <- temp.(i)) indices
let () =
let values = [| 7; 6; 5; 4; 3; 2; 1; 0 |]
and indices = [| 6; 1; 7 |] in
disjoint_sort compare values indices;
Array.iter (Printf.printf " %d") values;
print_newline()
With lists:
let disjoint_sort cmp values indices =
let indices = List.sort compare indices in
let rec aux acc j = function
| (i::iq), (v::vq) when i = j ->
aux (v::acc) (succ j) (iq, vq)
| [], _ -> acc
| il, (_::vq) ->
aux acc (succ j) (il, vq)
| _, [] ->
invalid_arg "index out of bounds"
in
let temp = aux [] 0 (indices, values) in
let temp = List.sort cmp temp in
let rec aux acc j = function
| (i::iq), (_::vq), (r::rq) when i = j ->
aux (r::acc) (succ j) (iq, vq, rq)
| [], vl, _ ->
List.rev_append acc vl
| il, (v::vq), rl ->
aux (v::acc) (succ j) (il, vq, rl)
| (_::_, [], _) ->
assert false
in
aux [] 0 (indices, values, temp)
let () =
let values = [ 7; 6; 5; 4; 3; 2; 1; 0 ]
and indices = [ 6; 1; 7 ] in
let res = disjoint_sort compare values indices in
List.iter (Printf.printf " %d") res;
print_newline()
ooRexx
data = .array~of(7, 6, 5, 4, 3, 2, 1, 0)
-- this could be a list, array, or queue as well because of polymorphism
-- also, ooRexx arrays are 1-based, so using the alternate index set for the
-- problem.
indexes = .set~of(7, 2, 8)
call disjointSorter data, indexes
say "Sorted data is: ["data~toString("l", ", ")"]"
::routine disjointSorter
use arg data, indexes
temp = .array~new(indexes~items)
-- we want to process these in a predictable order, so make an array
tempIndexes = indexes~makearray
-- we can't just assign things back in the same order. The expected
-- result requires the items be inserted back in first-to-last index
-- order, so we need to sort the index values too
tempIndexes~sortWith(.numberComparator~new)
do index over tempIndexes
temp~append(data[index])
end
-- sort as numbers
temp~sortwith(.numberComparator~new)
do i = 1 to tempIndexes~items
data[tempIndexes[i]] = temp[i]
end
-- a custom comparator that sorts strings as numeric values rather than
-- strings
::class numberComparator subclass comparator
::method compare
use strict arg left, right
-- perform the comparison on the names. By subtracting
-- the two and returning the sign, we give the expected
-- results for the compares
return (left - right)~sign
- Output:
Sorted data is: [7, 0, 5, 4, 3, 2, 1, 6]
Order
#include <order/interpreter.h>
#define ORDER_PP_DEF_8sort_disjoint_sublist ORDER_PP_FN( \
8fn(8L, 8I, \
8lets((8I, 8seq_sort(8less, 8tuple_to_seq(8I))) \
(8J, \
8seq_sort(8less, 8seq_map(8fn(8X, 8seq_at(8X, 8L)), 8I))), \
8replace(8L, 8I, 8J))) )
#define ORDER_PP_DEF_8replace ORDER_PP_FN( \
8fn(8L, 8I, 8V, \
8if(8is_nil(8I), \
8L, \
8replace(8seq_set(8seq_head(8I), 8L, 8seq_head(8V)), \
8seq_tail(8I), 8seq_tail(8V)))) )
ORDER_PP(
8sort_disjoint_sublist(8seq(7, 6, 5, 4, 3, 2, 1, 0), 8tuple(6, 1, 7))
)
PARI/GP
sortsome(v,which)={
my(x=sum(i=1,#which,1<<(which[i]-1)),u=vecextract(v,x));
u=vecsort(u);
which=vecsort(which);
for(i=1,#which,v[which[i]]=u[i]);
v
};
pascal
Tested free pascal.
program disjointsort;
procedure swap(var a, b: Integer);
var
temp: Integer;
begin
temp := a;
a := b;
b := temp;
end;
procedure d_sort(var index,arr:array of integer);
var
n,i,j,num:integer;
begin
num:=length(index);
for n:=1 to 2 do
begin
for i:=0 to num-1 do
begin
for j:=i+1 to num-1 do
begin
if n=1 then if index[j]<index[i] then swap(index[j],index[i]);
if n=2 then if arr[index[j]]<arr[index[i]] then swap(arr[index[j]],arr[index[i]]);
end;
end;
end;
end;
var
i:integer;
arr :array[0 .. 7] of integer =(7, 6, 5, 4, 3, 2, 1, 0);
index:array[0 .. 2] of integer =(6, 1, 7);
begin
writeln('Before');
for i:=0 to 7 do write(arr[i],' ');
writeln;
d_sort(index,arr);
writeln('After');
for i:=0 to 7 do write(arr[i],' ');
writeln;
readln;
end.
Before 7 6 5 4 3 2 1 0 After 7 0 5 4 3 2 1 6
Perl
#!/usr/bin/perl -w
use strict ;
# this function sorts the array in place
sub disjointSort {
my ( $values , @indices ) = @_ ;
@{$values}[ sort @indices ] = sort @{$values}[ @indices ] ;
}
my @values = ( 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ) ;
my @indices = ( 6 , 1 , 7 ) ;
disjointSort( \@values , @indices ) ;
print "[@values]\n" ;
- Output:
[7 0 5 4 3 2 1 6]
Phix
with javascript_semantics function disjoint_sort(sequence s, sequence idx) idx = unique(idx) integer l = length(idx) sequence copies = repeat(0, l) for i=1 to l do copies[i] = s[idx[i]] end for copies = sort(copies) for i=1 to l do s[idx[i]] = copies[i] end for return s end function ?disjoint_sort({7,6,5,4,3,2,1,0},{7,2,8})
- Output:
{7,0,5,4,3,2,1,6}
Shorter Alternative Version
with javascript_semantics function disjoint_sort(sequence s, idx) idx = unique(idx) return reinstate(s,idx,sort(extract(s,idx))) end function ?disjoint_sort({7,6,5,4,3,2,1,0},{7,2,8})
- Output:
same output.
PicoLisp
The indices are incremented here, as PicoLisp is 1-based
(let (Values (7 6 5 4 3 2 1 0) Indices (7 2 8))
(mapc
'((V I) (set (nth Values I) V))
(sort (mapcar '((N) (get Values N)) Indices))
(sort Indices) )
Values )
- Output:
-> (7 0 5 4 3 2 1 6)
Prolog
Using only predicates marked as "builtin"
% ===
% Problem description
% ===
% http://rosettacode.org/wiki/Sort_disjoint_sublist
%
% Given a list of values and a set of integer indices into that value list,
% the task is to sort the values at the given indices, while preserving the
% values at indices outside the set of those to be sorted.
%
% Make your example work with the following list of values and set of indices:
%
% Values: [7, 6, 5, 4, 3, 2, 1, 0]
%
% Indices: {6, 1, 7}
%
% Where the correct result would be:
%
% [7, 0, 5, 4, 3, 2, 1, 6].
%
% In case of one-based indexing, rather than the zero-based indexing above,
% you would use the indices {7, 2, 8} instead.
%
% The indices are described as a set rather than a list but any collection-type
% of those indices without duplication may be used as long as the example is
% insensitive to the order of indices given.
% ===
% Notes
% ===
% For predicate descriptions, see https://www.swi-prolog.org/pldoc/man?section=preddesc
%
% Solution using only predicates marked "builtin".
%
% - sort/2 is a built-in predicate. When called as sort(A,B) then
% it sorts A to B according to the "standard order of terms",
% (for integers, this means ascending order). It does remove
% duplicates.
% - msort/2 is the same as sort/2 but does not remove duplicates.
%
% Everything is a list as there is no "set" datatype in Prolog.
% ===
% Main predicate (the one that would be exported from a Module)
% sort_disjoint_sublist(+Values,+Indexes,?ValuesSorted)
% ===
sort_disjoint_sublist(Values,Indexes,ValuesSorted) :-
sort(Indexes,IndexesSorted),
insert_fresh_vars(0,IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened),
msort(ValsToSort,ValsSorted), % this is the "sorting of values"
% The next two lines could be left out with suitable naming,
% but they make explicit what happens:
FreshVars = ValsSorted, % fresh variables are unified with sorted variables
ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output
% ===
% Helper predicate (would not be exported from a Module)
% ===
% insert_fresh_vars(+CurIdx,+[I|Is],+[V|Vs],-FreshVars,-ValsToSort,-ValsFreshy)
%
% CurIdx: Monotonically increasing index into the list of values by
% which we iterate.
% [I|Is]: Sorted list of indexes of interest. The smallest (leftmost)
% element is removed on every "index hit", leaving eventually
% an empty list, which gives us the base case.
% [V|Vs]: The list of values of interest with the leftmost element the
% element with index CurIdx, all elements with lower index
% having been discarded. Leftmost element is popped off on
% each call.
% FreshVars: Constructed as output. If there was an "index hit", the
% fresh variable pushed on FreshVars is also pushed on Vars.
% ValsToSort: Constructed as output. If there was an "index hit", the
% leftmost value from [V|Vs] is pushed on.
% ValsFreshy: Constructed as output. If there was an "index hit", a fresh
% variable is pushed on. If there was no "index hit", the actual
% value from [V|Vs] is pushed on instead.
insert_fresh_vars(CurIdx,[I|Is],[V|Vs],FreshVars,ValsToSort,[V|ValsFreshy]) :-
CurIdx<I, % no index hit, CurIdx is still too small, iterate over value
!,
succ(CurIdx,NextIdx),
insert_fresh_vars(NextIdx,[I|Is],Vs,FreshVars,ValsToSort,ValsFreshy).
insert_fresh_vars(CurIdx,[I|Is],[V|Vs],[Fresh|FreshVars],[V|ValsToSort],[Fresh|ValsFreshy]) :-
CurIdx=I, % index hit, replace value by fresh variable
!,
succ(CurIdx,NextIdx),
insert_fresh_vars(NextIdx,Is,Vs,FreshVars,ValsToSort,ValsFreshy).
insert_fresh_vars(_,[],V,[],[],V).
Alternatively, using predicates from library(list)
Using append/3
from SWi-Prolog's library(list)
% ===
% Main predicate
% ===
sort_disjoint_sublist(Values,Indexes,ValuesSorted) :-
sort(Indexes,IndexesSorted),
insert_fresh_vars_by_splintering(IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened),
msort(ValsToSort,ValsSorted), % this is the "sorting of values"
% The next two lines could be left out with suitable naming,
% but they make explicit what happens:
FreshVars = ValsSorted, % fresh variables are unified with sorted variables
ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output
% ===
% Helpers
% ===
insert_fresh_vars_by_splintering([I|Is],Values,[Fresh|FreshVars],[ValAtI|ValsToSort],ValsFreshyFinal) :-
splinter(Values,I,ValAtI,ValsFront,ValsBack), % splinter Values --> ValsFront + ValAtI + ValsBack
append([ValsFront,[Fresh],ValsBack],ValsFreshyNext), % recompose ValsFront + Fresh + ValsBack --> ValuesFreshyNext
insert_fresh_vars_by_splintering(Is,ValsFreshyNext,FreshVars,ValsToSort,ValsFreshyFinal).
insert_fresh_vars_by_splintering([],V,[],[],V).
% "splinter" a list into a frontlist, the element at position N and a backlist
splinter(List, N, Elem, Front, Back) :-
length(Front, N),
append(Front, [Elem|Back], List).
Unit Tests
Test code using the Unit Testing framework of SWI Prolog.
% We use the "R" intermediate var to decouple processing by the predicate
% from subsequent checking against expected result.
:- begin_tests(sort_disjoint_sublist).
test(rosetta) :- sort_disjoint_sublist([7,6,5,4,3,2,1,0],[6,1,7],R), R = [7,0,5,4,3,2,1,6].
test(another1) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[3,4,5,6,7],R), R = [4,2,1,0,0,4,5,5].
test(another2) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,1,2,3,4],R), R = [1,2,4,4,5,5,0,0].
test(another3) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,2,4,6],R), R = [0,2,1,4,4,5,5,0].
test(another4) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[1,3,5,7],R), R = [4,0,1,2,5,4,0,5].
test(edge1) :- sort_disjoint_sublist([],[],R), R = [].
test(edge2) :- sort_disjoint_sublist([3,2,1],[],R), R = [3,2,1].
test(edge3) :- sort_disjoint_sublist([3,2,1],[0],R), R = [3,2,1].
test(edge4) :- sort_disjoint_sublist([3,2,1],[1],R), R = [3,2,1].
test(edge5) :- sort_disjoint_sublist([3,2,1],[2],R), R = [3,2,1].
test(x1) :- sort_disjoint_sublist([3,2,1],[0,1,2],R), R = [1,2,3].
test(x2) :- sort_disjoint_sublist([1,2,3],[0,1,2],R), R = [1,2,3].
test(dups1) :- sort_disjoint_sublist([3,2,1],[1,1,1],R), R = [3,2,1].
test(dups2) :- sort_disjoint_sublist([3,2,1],[2,1,2],R), R = [3,1,2].
test(fail1,[fail]) :- sort_disjoint_sublist([1,2],[0,1,2],_).
test(fail2,[fail]) :- sort_disjoint_sublist([],[0,1],_).
:- end_tests(sort_disjoint_sublist).
% ---
% Run unit tests.
% ---
rt :- run_tests(sort_disjoint_sublist).
PowerShell
function sublistsort($values, $indices) {
$indices = $indices | sort
$sub, $i = ($values[$indices] | sort), 0
$indices | foreach { $values[$_] = $sub[$i++] }
$values
}
$values = 7, 6, 5, 4, 3, 2, 1, 0
$indices = 6, 1, 7
"$(sublistsort $values $indices)"
- Output:
7 0 5 4 3 2 1 6
Python
The function modifies the input data list in-place and follows the Python convention of returning None in such cases.
>>> def sort_disjoint_sublist(data, indices):
indices = sorted(indices)
values = sorted(data[i] for i in indices)
for index, value in zip(indices, values):
data[index] = value
>>> d = [7, 6, 5, 4, 3, 2, 1, 0]
>>> i = set([6, 1, 7])
>>> sort_disjoint_sublist(d, i)
>>> d
[7, 0, 5, 4, 3, 2, 1, 6]
>>> # Which could be more cryptically written as:
>>> def sort_disjoint_sublist(data, indices):
for index, value in zip(sorted(indices), sorted(data[i] for i in indices)): data[index] = value
>>>
Or, checking a dictionary for sublist indices, and returning a new (rather than mutated) list:
'''Disjoint sublist sorting'''
# --------------------- DISJOINT SORT ----------------------
# disjointSort :: [Int] -> [Int] -> [Int]
def disjointSort(ixs):
'''A copy of the list xs, in which the disjoint sublist
of items at zero-based indexes ixs is sorted in a
default numeric or lexical order.'''
def go(xs):
ks = sorted(ixs)
dct = dict(zip(ks, sorted(xs[k] for k in ks)))
return [
dct[i] if i in dct else x
for i, x in enumerate(xs)
]
return go
# -------------------------- TEST --------------------------
# main :: IO ()
def main():
'''Disjoint sublist at three indices.'''
print(
tabulated(
'Disjoint sublist at indices [6, 1, 7] sorted:\n'
)
(str)(str)(
disjointSort([6, 1, 7])
)([
[7, 6, 5, 4, 3, 2, 1, 0],
['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a']
])
)
# ------------------------ DISPLAY -------------------------
# tabulated :: String -> (a -> String) ->
# (b -> String) ->
# (a -> b) -> [a] -> String
def tabulated(s):
'''Heading -> x display function -> fx display function ->
f -> value list -> tabular string.'''
def go(xShow, fxShow, f, xs):
w = max(map(compose(len)(xShow), xs))
return s + '\n' + '\n'.join(
xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs
)
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Function composition.'''
return lambda f: lambda x: g(f(x))
if __name__ == '__main__':
main()
- Output:
Disjoint sublists at indices [6, 1, 7] sorted: [7, 6, 5, 4, 3, 2, 1, 0] -> [7, 0, 5, 4, 3, 2, 1, 6] ['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'] -> ['h', 'a', 'f', 'e', 'd', 'c', 'b', 'g']
Quackery
[ sort tuck [] unrot
witheach
[ dip dup peek
rot join swap ]
swap sort
dip swap witheach
[ over i^ peek
dip rot poke
swap ]
drop ] is sortdisjointsublist ( [ [ --> [ )
' [ 7 6 5 4 3 2 1 0 ] ' [ 6 1 7 ] sortdisjointsublist echo
- Output:
[ 7 0 5 4 3 2 1 6 ]
R
R lets you access elements of vectors with a vector of indices.
values=c(7,6,5,4,3,2,1,0)
indices=c(7,2,8)
values[sort(indices)]=sort(values[indices])
print(values)
Output:
7 0 5 4 3 2 1 6
Racket
#lang racket
(define (sort-disjoint l is)
(define xs
(sort (for/list ([x l] [i (in-naturals)] #:when (memq i is)) x) <))
(let loop ([l l] [i 0] [xs xs])
(cond [(null? l) l]
[(memq i is) (cons (car xs) (loop (cdr l) (add1 i) (cdr xs)))]
[else (cons (car l) (loop (cdr l) (add1 i) xs))])))
(sort-disjoint '(7 6 5 4 3 2 1 0) '(6 1 7))
;; --> '(7 0 5 4 3 2 1 6)
Raku
(formerly Perl 6)
Inline
Using L-value slice of the array, and `sort` as a mutating method:
my @values = 7, 6, 5, 4, 3, 2, 1, 0;
my @indices = 6, 1, 7;
@values[ @indices.sort ] .= sort;
say @values;
Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Iterative
sub disjointSort( @values, @indices --> List ) {
my @sortedValues = @values[ @indices ].sort ;
for @indices.sort -> $insert {
@values[ $insert ] = @sortedValues.shift ;
}
return @values ;
}
my @values = ( 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ) ;
my @indices = ( 6 , 1 , 7 ) ;
my @sortedValues = disjointSort( @values , @indices ) ;
say @sortedValues ;
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
REXX
Duplicate entries in the index list aren't destructive or illegal.
Note that the list may contain numbers in any form (integer, floating point, exponentationed),
as well as alphabetic/alphanumeric/non-displayable characters.
The REXX language normally uses a one-based index.
/*REXX program uses a disjointed sublist to sort a random list of values. */
parse arg old ',' idx /*obtain the optional lists from the CL*/
if old='' then old= 7 6 5 4 3 2 1 0 /*Not specified: Then use the default.*/
if idx='' then idx= 7 2 8 /* " " " " " " */
say ' list of indices:' idx; say /* [↑] is for one─based lists. */
say ' unsorted list:' old /*display the old list of numbers. */
say ' sorted list:' disjoint_sort(old,idx) /*sort 1st list using 2nd list indices.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
disjoint_sort: procedure; parse arg x,ix; y=; z=; p= 0
ix= sortL(ix) /*ensure the index list is sorted*/
do i=1 for words(ix) /*extract indexed values from X.*/
z= z word(x, word(ix, i) ) /*pick the correct value from X.*/
end /*j*/
z= sortL(z) /*sort extracted (indexed) values*/
do m=1 for words(x) /*re─build (re-populate) X list.*/
if wordpos(m, ix)==0 then y=y word(x,m) /*is the same or new?*/
else do; p= p + 1; y= y word(z, p)
end
end /*m*/
return strip(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortL: procedure; parse arg L; n= words(L); do j=1 for n; @.j= word(L,j)
end /*j*/
do k=1 for n-1 /*sort a list using a slow method*/
do m=k+1 to n; if @.m<@.k then parse value @.k @.m with @.m @.k
end /*m*/
end /*k*/ /* [↑] use PARSE for swapping.*/
$= @.1; do j=2 to n; $= $ @.j
end /*j*/
return $
- output when using the default inputs:
list of indices: 7 2 8 unsorted list: 7 6 5 4 3 2 1 0 sorted list: 7 0 5 4 3 2 1 6
Ring
aList = [7, 6, 5, 4, 3, 2, 1, 0]
indList = [7, 2, 8]
bList = []
for n = 1 to len(indList)
add(bList,[indList[n],aList[indList[n]]])
next
bList1 = sort(bList,1)
bList2 = sort(bList,2)
for n = 1 to len(bList)
aList[bList1[n][1]] = bList2[n][2]
next
showarray(aList)
func showarray vect
svect = ""
for n in vect
svect += " " + n + ","
next
? "[" + left(svect, len(svect) - 1) + "]"
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
RPL
≪ SORT → set
≪ { } 1 set SIZE FOR j
OVER set j GET GET + NEXT
SORT SWAP
1 set SIZE FOR j
set j GET 3 PICK j GET PUT NEXT
SWAP DROP
≫ ≫ 'SUBSORT' STO
HP-28 models shall use their homemade version of the SORT instruction, or use the one defined in Sorting algorithms/Bubble sort
{ 7 6 5 4 3 2 1 0 } { 6 1 7 } SUBSORT
- Output:
1: { 7 0 5 4 3 2 1 6 }
Ruby
By convention, the exlamation mark in the method name indicates that something potentially dangerous can happen. (In this case, the in place modification).
def sort_disjoint_sublist!(ar, indices)
values = ar.values_at(*indices).sort
indices.sort.zip(values).each{ |i,v| ar[i] = v }
ar
end
values = [7, 6, 5, 4, 3, 2, 1, 0]
indices = [6, 1, 7]
p sort_disjoint_sublist!(values, indices)
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Rust
use std::collections::BTreeSet;
fn disjoint_sort(array: &mut [impl Ord], indices: &[usize]) {
let mut sorted = indices.to_owned();
sorted.sort_unstable_by_key(|k| &array[*k]);
indices
.iter()
.zip(sorted.iter())
.map(|(&a, &b)| if a > b { (b, a) } else { (a, b) })
.collect::<BTreeSet<_>>()
.iter()
.for_each(|(a, b)| array.swap(*a, *b))
}
fn main() {
let mut array = [7, 6, 5, 4, 3, 2, 1, 0];
let indices = [6, 1, 7];
disjoint_sort(&mut array, &indices);
println!("{:?}", array);
}
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Scala
import scala.compat.Platform
object SortedDisjointSubList extends App {
val (list, subListIndex) = (List(7, 6, 5, 4, 3, 2, 1, 0), List(6, 1, 7))
def sortSubList[T: Ordering](indexList: List[Int], list: List[T]) = {
val subListIndex = indexList.sorted
val sortedSubListMap = subListIndex.zip(subListIndex.map(list(_)).sorted).toMap
list.zipWithIndex.map { case (value, index) =>
if (sortedSubListMap.isDefinedAt(index)) sortedSubListMap(index) else value
}
}
assert(sortSubList(subListIndex, list) == List(7, 0, 5, 4, 3, 2, 1, 6), "Incorrect sort")
println(s"List in sorted order.\nSuccessfully completed without errors. [total ${Platform.currentTime - executionStart} ms]")
}
Scheme
(use gauche.sequence)
(define num-list '(7 6 5 4 3 2 1 0))
(define indices '(6 1 7))
(define table
(alist->hash-table
(map cons
(sort indices)
(sort indices < (lambda (x) (~ num-list x))))))
(map last
(sort
(map-with-index
(lambda (i x) (list (hash-table-get table i i) x))
num-list)
<
car))
- Output:
(7 0 5 4 3 2 1 6)
Sidef
func disjointSort(values, indices) {
values[indices.sort] = [values[indices]].sort...
}
var values = [7, 6, 5, 4, 3, 2, 1, 0];
var indices = [6, 1, 7];
disjointSort(values, indices);
say values;
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Standard ML
functor SortDisjointFn (A : MONO_ARRAY) : sig
val sort : (A.elem * A.elem -> order) -> (A.array * int array) -> unit
end = struct
structure DisjointView : MONO_ARRAY = struct
type elem = A.elem
type array = A.array * int array
fun length (a, s) = Array.length s
fun sub ((a, s), i) = A.sub (a, Array.sub (s, i))
fun update ((a, s), i, x) = A.update (a, Array.sub (s, i), x)
(* dummy implementations for not-needed functions *)
type vector = unit
val maxLen = Array.maxLen
fun array _ = raise Domain
fun fromList _ = raise Domain
fun tabulate _ = raise Domain
fun vector _ = raise Domain
fun copy _ = raise Domain
fun copyVec _ = raise Domain
fun appi _ = raise Domain
fun app _ = raise Domain
fun modifyi _ = raise Domain
fun modify _ = raise Domain
fun foldli _ = raise Domain
fun foldl _ = raise Domain
fun foldri _ = raise Domain
fun foldr _ = raise Domain
fun findi _ = raise Domain
fun find _ = raise Domain
fun exists _ = raise Domain
fun all _ = raise Domain
fun collate _ = raise Domain
end
structure DisjointViewSort = ArrayQSortFn (DisjointView)
fun sort cmp (arr, indices) = (
ArrayQSort.sort Int.compare indices;
DisjointViewSort.sort cmp (arr, indices)
)
end
Usage:
- structure IntArray = struct = open Array = type elem = int = type array = int Array.array = type vector = int Vector.vector = end; structure IntArray : sig [ ... rest omitted ] - structure IntSortDisjoint = SortDisjointFn (IntArray); structure IntSortDisjoint : sig val sort : (A.elem * A.elem -> order) -> A.array * int array -> unit end - val a = Array.fromList [7, 6, 5, 4, 3, 2, 1, 0]; val a = [|7,6,5,4,3,2,1,0|] : int array - val indices = Array.fromList [6, 1, 7]; val indices = [|6,1,7|] : int array - IntSortDisjoint.sort Int.compare (a, indices); val it = () : unit - a; val it = [|7,0,5,4,3,2,1,6|] : int array
Swift
Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array.
struct DisjointSublistView<T> : MutableCollectionType {
let array : UnsafeMutablePointer<T>
let indexes : [Int]
subscript (position: Int) -> T {
get {
return array[indexes[position]]
}
set {
array[indexes[position]] = newValue
}
}
var startIndex : Int { return 0 }
var endIndex : Int { return indexes.count }
func generate() -> IndexingGenerator<DisjointSublistView<T>> { return IndexingGenerator(self) }
}
func sortDisjointSublist<T : Comparable>(inout array: [T], indexes: [Int]) {
var d = DisjointSublistView(array: &array, indexes: sorted(indexes))
sort(&d)
}
var a = [7, 6, 5, 4, 3, 2, 1, 0]
let ind = [6, 1, 7]
sortDisjointSublist(&a, ind)
println(a)
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
Tcl
This returns the sorted copy of the list; this is idiomatic for Tcl programs where values are immutable.
package require Tcl 8.5
proc disjointSort {values indices args} {
# Ensure that we have a unique list of integers, in order
# We assume there are no end-relative indices
set indices [lsort -integer -unique $indices]
# Map from those indices to the values to sort
set selected {}
foreach i $indices {lappend selected [lindex $values $i]}
# Sort the values (using any extra options) and write back to the list
foreach i $indices v [lsort {*}$args $selected] {
lset values $i $v
}
# The updated list is the result
return $values
}
Demonstration:
set values {7 6 5 4 3 2 1 0}
set indices {6 1 7}
puts \[[join [disjointSort $values $indices] ", "]\]
- Output:
[7, 0, 5, 4, 3, 2, 1, 6]
TUSCRIPT
TUSCRIPT indexing is one based
$$ MODE TUSCRIPT
values="7'6'5'4'3'2'1'0"
indices="7'2'8"
v_unsorted=SELECT (values,#indices)
v_sort=DIGIT_SORT (v_unsorted)
i_sort=DIGIT_SORT (indices)
LOOP i=i_sort,v=v_sort
values=REPLACE (values,#i,v)
ENDLOOP
PRINT values
- Output:
7'0'5'4'3'2'1'6
Uiua
⍜▽(⊏⍏.)°⊚ 6_1_7 [7 6 5 4 3 2 1 0]
- Output:
[7 0 5 4 3 2 1 6]
Ursala
#import std
#import nat
disjoint_sort = ^|(~&,num); ("i","v"). (-:(-:)"v"@p nleq-<~~lSrSX ~&rlPlw~|/"i" "v")*lS "v"
#cast %nL
t = disjoint_sort({6,1,7},<7,6,5,4,3,2,1,0>)
- Output:
<7,0,5,4,3,2,1,6>
Wren
import "./sort" for Sort
// sorts values in place, leaves indices unsorted
var sortDisjoint = Fn.new { |values, indices|
var sublist = []
for (ix in indices) sublist.add(values[ix])
Sort.quick(sublist)
var i = 0
var indices2 = Sort.merge(indices)
for (ix in indices2) {
values[ix] = sublist[i]
i = i + 1
}
}
var values = [7, 6, 5, 4, 3, 2, 1, 0]
var indices = [6, 1, 7]
System.print("Initial: %(values)")
sortDisjoint.call(values, indices)
System.print("Sorted : %(values)")
- Output:
Initial: [7, 6, 5, 4, 3, 2, 1, 0] Sorted : [7, 0, 5, 4, 3, 2, 1, 6]
XPL0
include xpllib; \for Sort routine
int Values, Indices, J, I, T;
[Values:= [7, 6, 5, 4, 3, 2, 1, 0];
Indices:= [6, 1, 7];
Sort(Indices, 3);
for J:= 3-1 downto 0 do \bubble sort values at Indices
for I:= 0 to J-1 do
if Values(Indices(I)) > Values(Indices(I+1)) then
[T:= Values(Indices(I));
Values(Indices(I)):= Values(Indices(I+1));
Values(Indices(I+1)):= T;
];
for I:= 0 to 8-1 do
[IntOut(0, Values(I)); ChOut(0, ^ )];
]
- Output:
7 0 5 4 3 2 1 6
zkl
values :=T(7, 6, 5, 4, 3, 2, 1, 0);
indices:=T(6, 1, 7);
indices.apply(values.get).sort() // a.get(0) == a[0]
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7))
.reduce(fcn(newList,[(v,i)]){ newList[i]=v; newList },values.copy())
.println(); // new list
This is an create-new-object version. An in place version is almost identical:
values :=L(7, 6, 5, 4, 3, 2, 1, 0);
indices.apply(values.get).sort() // a.get(0) == a[0]
.zip(indices.sort()) //-->(v,i) == L(L(0,1),L(1,6),L(6,7))
.apply2(fcn([(v,i)],list){ list[i]=v },values);
values.println(); // modified list
- Output:
L(7,0,5,4,3,2,1,6)
- Programming Tasks
- Sorting Algorithms
- Sorting
- 11l
- AArch64 Assembly
- Action!
- Ada
- ALGOL W
- APL
- AppleScript
- ARM Assembly
- Arturo
- ATS
- AutoHotkey
- BASIC
- Applesoft BASIC
- BBC BASIC
- Chipmunk Basic
- FreeBASIC
- GW-BASIC
- Minimal BASIC
- MSX Basic
- PureBasic
- Run BASIC
- True BASIC
- Yabasic
- Bracmat
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Delphi
- SysUtils,StdCtrls
- EasyLang
- EchoLisp
- Elena
- Elixir
- Erlang
- ERRE
- Euphoria
- F Sharp
- Factor
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Io
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Ksh
- Lua
- Maple
- Mathematica
- Wolfram Language
- MiniScript
- NetRexx
- Nial
- Nim
- Objective-C
- OCaml
- OoRexx
- Order
- PARI/GP
- Pascal
- Perl
- Phix
- PicoLisp
- Prolog
- PowerShell
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Standard ML
- Swift
- Tcl
- TUSCRIPT
- Uiua
- Ursala
- Wren
- Wren-sort
- XPL0
- Zkl