Sort disjoint sublist

Sort disjoint sublist is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 may be used as long as the example is insensitive to the order of indices given.

D

Translation of: Python

<lang d>import std.stdio, std.array, std.algorithm, std.range ;

T[] disjointSort(T, U)(T[] arr, U[] s) {

   auto idx     = array(uniq(s.dup.sort)) ;
   auto values  = array(map!((i){ return arr[i] ; })(idx)) ;
   sort(values) ;
   foreach(i, ix ; idx)
       arr[ix] = values[i] ;
   return arr ;

}

void main() {

   auto d = [7, 6, 5, 4, 3, 2, 1, 0] ;
   auto i = [6, 1, 1, 7] ;
   writeln(disjointSort(d, i)) ; // print [7, 0, 5, 4, 3, 2, 1, 6]

}</lang>

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 = Array.sort indices
 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|] [|6;1;7|])</lang>

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

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 = [6, 1, 7] >>> sort_disjoint_sublist(d, i) >>> d [7, 0, 5, 4, 3, 2, 1, 6]</lang>

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]