# Sort disjoint sublist

Sort disjoint sublist
You are encouraged to solve this task according to the task description, using any language you may know.

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.

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]`.
```

Note that for one based, rather than the zero-based indexing above, use the `indices: {7, 2, 8}`. 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 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;</lang>

## C

<lang C>#include <stdio.h>

/* yes, bubble sort */ void bubble_sort(int *idx, int n_idx, int *buf) {

```       int i, j, tmp;
```
1. define for_ij for (i = 0; i < n_idx; i++) for (j = i + 1; j < n_idx; j++)
2. 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]]);}
```
1. undef for_ij
2. 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;
```

}</lang>

## C++

<lang cpp>#include <algorithm>

1. include <iostream>
2. include <iterator>
3. include <vector>

int main() {

```   int values[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
int indices[] = { 6, 1, 7 };
```
```   std::vector<int> temp;
```
```   for (size_t i = 0; i < 3; ++i)
{
temp.push_back(values[indices[i]]); // extract
}
```
```   std::sort(indices, indices + 3); // sort a C-style array
std::sort(temp.begin(), temp.end()); // sort a C++ container
```
```   for (size_t i = 0; i < 3; ++i)
{
values[indices[i]] = temp[i]; // replace
}
```
```   std::copy(values, values + 8, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
```

}</lang> Output:

```7 0 5 4 3 2 1 6
```

## D

<lang 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];
```
```   auto idxSet = array(uniq(indices.sort()));
sort(indexed(data, idxSet));
```
```   assert(data == [7, 0, 5, 4, 3, 2, 1, 6]);
```

}</lang> A lower level version: <lang d>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]);
```

}</lang>

## Euphoria

<lang 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}</lang>

Output:

```{7,0,5,4,3,2,1,6}
```

## F#

Translation of: 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#. <lang fsharp>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]))</lang>

## Fortran

Works with: Fortran version 90 and later

<lang 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</lang> Output

`           7           0           5           4           3           2           1           6`

## Go

<lang 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)
```

}</lang> 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. <lang go>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)
```

}</lang>

Here are three variations on the solution: using ordinary lists, immutable "boxed" arrays, and mutable "unboxed" arrays.

<lang haskell> 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 <- liftM (zip (sort is) . sort) \$ mapM (readArray as) is
mapM_ (uncurry (writeArray as)) sub
return as
```

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
```

</lang>

## Icon and Unicon

Icon's lists are 1-based, so the example uses (7, 2, 8) as the indices, not (6, 1 7).

<lang icon> link sort # get the 'isort' procedure for sorting a list

procedure sortDisjoint (items, indices)

``` indices := isort (indices) # sort indices into a list
result := copy (items)
values := []
every put (values, result[!indices])
values := isort (values)
every result[!indices] := pop (values)
return result
```

end

procedure main ()

``` # set up and do the sort
items := [7, 6, 5, 4, 3, 2, 1, 0]
indices := set(7, 2, 8) # note, Icon lists 1-based
result := sortDisjoint (items, indices)
# display result
every writes (!items || " ")
write ()
every writes (!indices || " ")
write ()
every writes (!result || " ")
write ()
```

end </lang>

Output:

```7 6 5 4 3 2 1 0
2 7 8
7 0 5 4 3 2 1 6
```

The expression `!indices` 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 `result[index]` into the list 'values'.

## J

Note that the task requires us to ignore the order of the indices.

<lang j> 7 6 5 4 3 2 1 0 (/:~@:{`[`]}~ /:~@~.) 6 1 7 7 0 5 4 3 2 1 6</lang>

Compare this with: <lang j> 6 1 7 /:~@:{`[`]} 7 6 5 4 3 2 1 0 7 1 5 4 3 2 0 6</lang>

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

Works with: Java version 1.5+

This function will modify the index array and the values list. <lang java5>import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.TreeSet; import java.util.List;

public class Disjoint {

```   public static <T extends Comparable<? super T>> void sortDisjoint(
List<T> array, TreeSet<Integer> idxs){
//TreeSets are already sorted, so we don't need to sort the indices
List<T> disjoint = new ArrayList<T>();
for(int idx : idxs){
}
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);
TreeSet<Integer> indices = new TreeSet<Integer>();
System.out.println(list);
sortDisjoint(list, indices);
System.out.println(list);
}
```

} </lang> Output:

```[7, 6, 5, 4, 3, 2, 1, 0]
[7, 0, 5, 4, 3, 2, 1, 6]```

## K

<lang 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 </lang>

## Lua

<lang 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</lang>

`7  0  5  4  3  2  1  6`

## OCaml

With arrays:

<lang ocaml>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()</lang>
```

With lists:

<lang ocaml>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()</lang>
```

## PARI/GP

<lang parigp>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
```

};</lang>

## Perl

<lang Perl>#!/usr/bin/perl -w use strict ;

1. 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" ;</lang> Output:

`[7 0 5 4 3 2 1 6]`

## Perl 6

### Inline

Using L-value slice of the array, and `sort` as a mutating method: <lang perl6>my @values = 7, 6, 5, 4, 3, 2, 1, 0; my @indices = 6, 1, 7;

@values[ @indices.sort ] .= sort;

@values.perl.say;</lang>

Output:
`[7, 0, 5, 4, 3, 2, 1, 6]`

### Iterative

<lang Perl 6>sub disjointSort( @values is rw , @indices is rw --> 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 ) ; @sortedValues.perl.say ;</lang> Output:

`[7, 0, 5, 4, 3, 2, 1, 6]`

## PicoLisp

The indices are incremented here, as PicoLisp is 1-based <lang PicoLisp>(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 )</lang>
```

Output:

`-> (7 0 5 4 3 2 1 6)`

## PureBasic

Based on the C implementation <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()</lang>

```Before sort:
7 6 5 4 3 2 1 0

After sort:
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.

<lang python>>>> def sort_disjoint_sublist(data, indices): indices = sorted(indices) values = [data[i] for i in indices] values.sort() 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]</lang>

## R

R lets you access elements of vectors with a vector of indices.

<lang R> values=c(7,6,5,4,3,2,1,0)

```indices=c(7,2,8)
values[sort(indices)]=sort(values[indices])
print(values)</lang>
```

Output:

` 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). <lang ruby>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)</lang> 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. <lang tcl>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
```

}</lang> Demonstration: <lang tcl>set values {7 6 5 4 3 2 1 0} set indices {6 1 7} puts \[[join [disjointSort \$values \$indices] ", "]\]</lang> Output:

`[7, 0, 5, 4, 3, 2, 1, 6]`

## TUSCRIPT

TUSCRIPT indexing is one based <lang tuscript> \$\$ 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 </lang> Output:

```7'0'5'4'3'2'1'6
```

## Ursala

<lang Ursala>#import std

1. import nat

disjoint_sort = ^|(~&,num); ("i","v"). (-:(-:)"v"@p nleq-<~~lSrSX ~&rlPlw~|/"i" "v")*lS "v"

1. cast %nL

t = disjoint_sort({6,1,7},<7,6,5,4,3,2,1,0>)</lang> output:

`<7,0,5,4,3,2,1,6>`