Sort disjoint sublist: Difference between revisions

 

Make your example work with the following list of values and set of indices:

Where the correct result would be:

 

 

 

*   [[Order disjoint list items]]

<br><br>

 

=={{header|Ada}}==

use Ada.Text_IO;

 

New_Line;

 

 

=={{header|APL}}==

∇SDS[⎕]∇

∇

[2] Z←L

∇

{{out}}

<pre>

 

=={{header|AppleScript}}==

 

 

 

 

end |λ|

end script

on |λ|(x, i)

x

else

end if

end |λ|

end script

end disjointSort

 

on run

end run

 

 

 

-- map :: (a -> b) -> [a] -> [b]

end tell

end map

 

-- Lift 2nd class handler function into 1st class script wrapper

on mReturn(f)

if class of f is script then

end mReturn

 

sortedArrayUsingSelector:"compare:") as list

{{Out}}

 

{{works with|BBC BASIC for Windows}}

Sort% = FN_sortinit(0,0) : REM Ascending

o$ += STR$(l%(i%)) + ", "

NEXT

 

=={{header|Bracmat}}==

& 6 1 7:?indices

& 0:?sortedValues:?sortedIndices

& !A !value !Z:?values

)

<pre>7 0 5 4 3 2 1 6</pre>

 

=={{header|C}}==

 

/* yes, bubble sort */

 

return 0;

 

=={{header|C sharp}}==

using System.Linq;

using System.Collections.Generic;

}

 

=={{header|C++}}==

#include <iostream>

#include <iterator>

 

return 0;

{{out}}

<pre>

{{trans|Go}}

Solution that sorts using a custom iterator that iterates a disjoint sublist.

#include <iostream>

#include <iterator>

 

return 0;

{{out}}

<pre>

 

=={{header|Clojure}}==

(let [val-subset (keep-indexed #(when ((set idxs) %) %2) coll)

replacements (zipmap (set idxs) (sort val-subset))]

 

{{out}}

 

=={{header|Common Lisp}}==

"Destructively perform a disjoin sublist sort on VALUES with INDICES."

(loop :for element :in

:for index :across (sort indices '<)

:do (setf (svref values index) element))

{{out}}

<pre>CL-USER> (disjoint-sort #(7 6 5 4 3 2 1 0) #(6 1 7))

 

=={{header|D}}==

 

void main() {

 

assert(data == [7, 0, 5, 4, 3, 2, 1, 6]);

===Lower Level version===

 

void disjointSort(T, U)(T[] arr, U[] indexes)

disjointSort(data, indexes);

assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]);

 

===Simple Alternative Version===

 

void main() {

 

assert(data == [7.0, 0.0, 5.0, 4.0, 3.0, 2.0, 1.0, 6.0]);

 

=={{header|EchoLisp}}==

(define (sort-disjoint values indices)

(define sorted (list-sort <

(task)

→ (7 0 5 4 3 2 1 6)

=={{header|Elena}}==

extension op

{

^ list

}

{{out}}

 

=={{header|Elixir}}==

def sublist(values, indices) when is_list(values) and is_list(indices) do

indices2 = Enum.sort(indices)

values = [7, 6, 5, 4, 3, 2, 1, 0]

indices = [6, 1, 7]

{{out}}

 

=={{header|Erlang}}==

-module( sort_disjoint ).

 

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}}.

{{out}}

 

=={{header|ERRE}}==

 

DIM LST%[7],INDICES%[2]

ShowList(LST%[]->O$)

PRINT(O$)

{{out}}

 

=={{header|Euphoria}}==

 

function uniq(sequence s)

 

constant data = {7, 6, 5, 4, 3, 2, 1, 0}

 

=={{header|F_Sharp|F#}}==

{{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#.

let indices = Set.toArray indices // creates a sorted array

let result = Array.copy data

 

 

 

=={{header|Factor}}==

over <enumerated> nths unzip swap [ natural-sort ] bi@

{{out}}

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

 

end subroutine Isort

<pre> 7 0 5 4 3 2 1 6</pre>

 

=={{header|Go}}==

 

import (

}

fmt.Println("sorted: ", values)

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.

 

import (

sort.Sort(s)

fmt.Println("sorted: ", s.values)

 

=={{header|Groovy}}==

Groovy allows List-valued indexing to "gather" and "scatter" arbitrary sublists, making the solution almost trivial.

indices.sort().unique()

a[indices] = a[indices].sort()

a

 

Test:

 

println a

println a

println sparseSort(a) // default == sort all

 

Output:

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

 

import qualified Data.Array as A

import Data.Array.IArray

print $ disSort1 xs is

print $ disSort2 xs is

 

 

Or, in terms of Data.Map:

import Data.Maybe (mapMaybe)

import Data.List (sort)

disjointSort :: [Int] -> [Int] -> [Int]

disjointSort ixs xs =

in mapMaybe

(keys dctAll)

 

main :: IO ()

{{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).

 

 

procedure sortDisjoint (items, indices)

every writes (!result || " ")

write ()

2 7 8

 

 

=={{header|Io}}==

Io does not come with a set type.

sortedIndices := indices unique sortInPlace

sortedValues := sortedIndices map(idx,at(idx)) sortInPlace

)

 

{{output}}

<pre>list(7, 0, 5, 4, 3, 2, 1, 6)</pre>

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

 

 

Compare this with:

 

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

{{works with|Java|1.5+}}

This function will modify the index array and the values list.

import java.util.Arrays;

import java.util.Collections;

System.out.println(list);

}

{{out}}

<pre>[7, 6, 5, 4, 3, 2, 1, 0]

{{trans|Go}}

Shorter solution that sorts a list "wrapper" which represents a "view" into the disjoint sublist of the list.

import java.util.Collections;

import java.util.List;

System.out.println(list);

}

{{out}}

<pre>[7, 6, 5, 4, 3, 2, 1, 0]

===ES5===

====Iterative====

Does not check for duplicate indices.

var sublist = [];

indices.sort(function(a, b) { return a > b; });

 

return values;

 

====Functional====

'use strict';

 

return disjointSort([7, 6, 5, 4, 3, 2, 1, 0], [6, 1, 7])

 

{{Out}}

<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre>

 

===ES6===

'use strict';

 

// MAIN ---

return main();

{{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:

reduce range(0; indices|length) as $i

(.; .[indices[$i]] = values[$i]);

# Set $sorted to the sorted array of values at $ix:

| ([ .[ $ix[] ] ] | sort) as $sorted

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

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

sel = unique(sort(s))

if sel[1] < 1 || length(a) < sel[end]

b = sortselected(a, sel)

 

{{out}}

<pre>Original: [7, 6, 5, 4, 3, 2, 1, 0]

 

=={{header|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===

nums : 7 6 5 4 3 2 1 0

i : sort 6 1 7

nums[i] : sort nums[i]

nums

 

=={{header|Kotlin}}==

 

/* in place sort */

values.sortDisjoint(indices)

println("Sorted array : ${values.asList()}")

{{out}}

 

=={{header|Lua}}==

indices = { 6, 1, 7 }

 

for i = 1, #values do

io.write( values[i], " " )

<pre>7 0 5 4 3 2 1 6</pre>

 

=={{header|Maple}}==

local vals,inds,i:

vals := sort([seq(values[i], i in indices)]):

end proc:

tst := Array([7,6,5,4,3,2,1,0]):

{{out}}

<pre>[7 0 5 4 3 2 1 6]</pre>

 

Values[[Sort[Indices]]] = Sort[Values[[Indices]]];

 

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

say 'Idx:' iList.space

return

{{out}}

Out: 7 0 5 4 3 2 1 6

 

=={{header|Nial}}==

{{works with|Q'Nial Version 6.3}}

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

 

=={{header|Nim}}==

 

proc sortDisjoinSublist[T](data: var seq[T], indices: seq[int]) =

var d = @[7, 6, 5, 4, 3, 2, 1, 0]

sortDisjoinSublist(d, @[6, 1, 7])

<pre>@[7, 0, 5, 4, 3, 2, 1, 6]</pre>

 

{{trans|Go}}

Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array.

 

@interface DisjointSublistView : NSMutableArray {

}

return 0;

{{out}}

<pre>(

 

=={{header|OCaml}}==

let temp = Array.map (Array.get values) indices in

Array.sort cmp temp;

disjoint_sort compare values indices;

Array.iter (Printf.printf " %d") values;

 

let indices = List.sort compare indices in

let rec aux acc j = function

let res = disjoint_sort compare values indices in

List.iter (Printf.printf " %d") res;

 

=={{header|ooRexx}}==

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

-- the two and returning the sign, we give the expected

-- results for the compares

{{out}}

<pre>Sorted data is: [7, 0, 5, 4, 3, 2, 1, 6]</pre>

 

=={{header|Order}}==

 

#define ORDER_PP_DEF_8sort_disjoint_sublist ORDER_PP_FN( \

ORDER_PP(

8sort_disjoint_sublist(8seq(7, 6, 5, 4, 3, 2, 1, 0), 8tuple(6, 1, 7))

 

=={{header|PARI/GP}}==

my(x=sum(i=1,#which,1<<(which[i]-1)),u=vecextract(v,x));

u=vecsort(u);

for(i=1,#which,v[which[i]]=u[i]);

v

 

=={{header|Perl}}==

use strict ;

 

my @indices = ( 6 , 1 , 7 ) ;

disjointSort( \@values , @indices ) ;

<pre>[7 0 5 4 3 2 1 6]</pre>

 

=={{header|Phix}}==

 

{{out}}

 

=={{header|PicoLisp}}==

The indices are incremented here, as PicoLisp is 1-based

(mapc

'((V I) (set (nth Values I) V))

(sort (mapcar '((N) (get Values N)) Indices))

(sort Indices) )

<pre>-> (7 0 5 4 3 2 1 6)</pre>

 

=={{header|PowerShell}}==

{{works with|PowerShell|4.0}}

 

function sublistsort($values, $indices) {

$indices = $indices | sort

$indices = 6, 1, 7

"$(sublistsort $values $indices)"

 

=={{header|Python}}==

The function modifies the input data list in-place and follows the Python convention of returning None in such cases.

 

indices = sorted(indices)

values = sorted(data[i] for i in indices)

 

 

=={{header|R}}==

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

 

indices=c(7,2,8)

values[sort(indices)]=sort(values[indices])

Output:

<pre> 7 0 5 4 3 2 1 6</pre>

 

=={{header|Racket}}==

 

(define (sort-disjoint l is)

 

(sort-disjoint '(7 6 5 4 3 2 1 0) '(6 1 7))

 

=={{header|REXX}}==

 

The REXX language normally uses a one-based index.

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.*/

$= @.1; do j=2 to n; $= $ @.j

end /*j*/

{{out|output|text=&nbsp; when using the default inputs:}}

 

unsorted list: 7 6 5 4 3 2 1 0

 

=={{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).

values = ar.values_at(*indices).sort

indices.sort.zip(values).each{ |i,v| ar[i] = v }

values = [7, 6, 5, 4, 3, 2, 1, 0]

indices = [6, 1, 7]

<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre>

 

 

 

 

=={{header|Scala}}==

 

object SortedDisjointSubList extends App {

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]")

 

=={{header|Scheme}}==

{{works with|Gauche Scheme}}

(define num-list '(7 6 5 4 3 2 1 0))

(define indices '(6 1 7))

num-list)

<

{{output}}

 

=={{header|Sidef}}==

values[indices.sort] = [values[indices]].sort...

}

 

disjointSort(values, indices);

{{out}}

<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre>

{{works with|SML/NJ}}

{{trans|Go}}

val sort : (A.elem * A.elem -> order) -> (A.array * int array) -> unit

end = struct

DisjointViewSort.sort cmp (arr, indices)

)

Usage:

<pre>- structure IntArray = struct

{{trans|Go}}

Sorts an array "wrapper" which represents a "view" into the disjoint sublist of the array.

let array : UnsafeMutablePointer<T>

let indexes : [Int]

let ind = [6, 1, 7]

sortDisjointSublist(&a, ind)

{{out}}

<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre>

=={{header|Tcl}}==

This returns the sorted copy of the list; this is idiomatic for Tcl programs where values are immutable.

proc disjointSort {values indices args} {

# Ensure that we have a unique list of integers, in order

# The updated list is the result

return $values

Demonstration:

set indices {6 1 7}

<pre>[7, 0, 5, 4, 3, 2, 1, 6]</pre>

=={{header|TUSCRIPT}}==

TUSCRIPT indexing is one based

values="7'6'5'4'3'2'1'0"

indices="7'2'8"

values=REPLACE (values,#i,v)

ENDLOOP

 

=={{header|Ursala}}==

#import nat

 

#cast %nL

 

<pre><7,0,5,4,3,2,1,6></pre>

 

=={{header|zkl}}==

indices:=T(6, 1, 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())

This is an create-new-object version. An in place version is almost identical:

 

indices.apply(values.get).sort() // a.get(0) == a[0]

.apply2(fcn([(v,i)],list){ list[i]=v },values);