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, but preserving the values at indices outside the set of those to be sorted.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Ada
<lang 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;</lang>
BBC BASIC
<lang bbcbasic> 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$)) + "]"</lang>
Output:
[7, 0, 5, 4, 3, 2, 1, 6]
C
<lang 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;
}</lang>
C++
<lang cpp>#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;
}</lang>
- Output:
7 0 5 4 3 2 1 6
Solution that sorts using a custom iterator that iterates a disjoint sublist. <lang cpp>#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;
}</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 = indices.sort().uniq().array(); data.indexed(idxSet).sort();
assert(data == [7, 0, 5, 4, 3, 2, 1, 6]);
}</lang>
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>
Simple Alternative Version
<lang d>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]);
}</lang>
Erlang
<lang 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}}. </lang>
- Output:
20> sort_disjoint:task(). [7,0,5,4,3,2,1,6]
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#
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
<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>
Groovy
Groovy allows List-valued indexing to "gather" and "scatter" arbitrary sublists, making the solution almost trivial. <lang groovy>def sparseSort = { a, indices = ([] + (0..<(a.size()))) ->
indices.sort().unique() a[indices] = a[indices].sort() a
}</lang>
Test: <lang groovy>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</lang>
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.
<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
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.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); }
}</lang>
- 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. <lang java5>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); }
}</lang>
- Output:
[7, 6, 5, 4, 3, 2, 1, 0] [7, 0, 5, 4, 3, 2, 1, 6]
JavaScript
Does not check for duplicate indices. <lang JavaScript>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;
}</lang>
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
Mathematica
<lang Mathematica>Values = { 7, 6, 5, 4, 3, 2, 1, 0} ; Indices = { 7, 2, 8 }; Values[[Sort[Indices]]] = Sort[ValuesIndices];
Values -> { 7, 0, 5, 4, 3, 2, 1, 6 }</lang>
NetRexx
<lang 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
</lang>
- Output:
In: 7 6 5 4 3 2 1 0 Out: 7 0 5 4 3 2 1 6 Idx: 7 2 8
Nimrod
<lang nimrod>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</lang> 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. <lang objc>#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;
} </lang>
- Output:
( 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>
ooRexx
<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 -- 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
</lang>
Order
<lang c>#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))
)</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 ;
- 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 = 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
>>> </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
Racket
<lang 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)
</lang>
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.
<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:
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
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]
Run BASIC
Normally we sort with SQLite in memory. Faster and less code <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</lang>
Standard ML
<lang sml>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</lang>
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
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
- 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>)</lang> output:
<7,0,5,4,3,2,1,6>
zkl
<lang zkl>values :=T(7, 6, 5, 4, 3, 2, 1, 0); indices:=T(6, 1, 7);
indices.apply(values.__sGet).sort() // a.__sGet(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</lang> This is an create-new-object version. An in place version is almost identical: <lang zkl>values :=L(7, 6, 5, 4, 3, 2, 1, 0);
indices.apply(values.__sGet).sort() // a.__sGet(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</lang>
- Output:
L(7,0,5,4,3,2,1,6)