Sort disjoint sublist: Difference between revisions
No edit summary |
(→{{header|Java}}: When I said "HashSet" I meant "TreeSet") |
||
Line 281: | Line 281: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{incorrect|Java|Sorts incorrectly with a list of length >16, and indices [1, 16]}} |
|||
{{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. |
||
Line 287: | Line 286: | ||
import java.util.Arrays; |
import java.util.Arrays; |
||
import java.util.Collections; |
import java.util.Collections; |
||
import java.util. |
import java.util.TreeSet; |
||
import java.util.List; |
import java.util.List; |
||
public class Disjoint { |
public class Disjoint { |
||
public static <T extends Comparable<? super T>> void sortDisjoint( |
public static <T extends Comparable<? super T>> void sortDisjoint( |
||
List<T> array, |
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>(); |
List<T> disjoint = new ArrayList<T>(); |
||
for(int idx : idxs){ |
for(int idx : idxs){ |
||
Line 307: | Line 306: | ||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
List<Integer> list = Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0); |
List<Integer> list = Arrays.asList(7, 6, 5, 4, 3, 2, 1, 0); |
||
TreeSet<Integer> indices = new TreeSet<Integer>(); |
|||
indices.addAll(Arrays.asList(6, 1, 7)); |
indices.addAll(Arrays.asList(6, 1, 7)); |
||
System.out.println(list); |
System.out.println(list); |
Revision as of 14:35, 22 March 2011
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.
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <iterator>
- 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.stdio, std.array, std.algorithm;
void disjointSort(T, U)(T[] arr, U[] s) {
const idxSet = array(uniq(s.sort())); auto values = array(map!((i){ return arr[i]; })(idxSet)).sort(); foreach (i, ix; idxSet) arr[ix] = values[i];
}
void main() {
auto data = [7, 6, 5, 4, 3, 2, 1, 0]; auto indexes = [6, 1, 1, 7]; disjointSort(data, indexes); writeln(data);
}</lang> Output:
[7, 0, 5, 4, 3, 2, 1, 6]
A lower level version, that uses no extra heap memory: <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>
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>
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.SortInts(orderedValues) sort.SortInts(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.SortInts(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.IntArray(values), ordered} fmt.Println("initial:", s.values) sort.Sort(s) fmt.Println("sorted: ", s.values)
}</lang>
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>
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.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){ 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); TreeSet<Integer> indices = new TreeSet<Integer>(); indices.addAll(Arrays.asList(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]
Perl
<lang Perl>#!/usr/bin/perl -w use strict ;
- this function sorts the array in place
sub disjointSort {
my ( $values , $indices ) = @_ ; my @sortedindices = sort @{$indices} ; @{$values}[ @sortedindices ] = sort @{$values}[ @sortedindices ] ;
}
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
<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)
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>
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