Sort disjoint sublist: Difference between revisions

{{Sorting Algorithm}}

[[Category:Sorting]]

 

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, while preserving the values at indices outside the set of those to be sorted.

*   [[Order disjoint list items]]

<br><br>

 

=={{header|Ada}}==

use Ada.Text_IO;

 

New_Line;

 

 

=={{header|APL}}==

∇SDS[⎕]∇

∇

[2] Z←L

∇

{{out}}

<pre>

 

=={{header|AppleScript}}==

 

 

use framework "Foundation"

use scripting additions

return lst

end tell

{{Out}}

 

 

This works with Mac OS 10.9 or later, and with older systems if an earlier method's used to load the insertion sort handler or that handler's copied into the script.

 

use sorter : script "Insertion sort" -- https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript.

 

set indices to {7, 2, 8} -- AppleScript indices are one-based.

sortValuesAtIndices(values, indices)

 

{{output}}

 

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

import system'routines;

import system'culture;

sortSublist(indices)

{

.toArray();

var list := self.clone();

{

list[r.Index] := r.Value

console.printLine(list.sortSublist(new int[]{6, 1, 7}).asEnumerable())

{{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 Control.Applicative ((<|>))

import Data.Maybe (mapMaybe)

 

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

 

=== Shorter Alternative Version ===

 

=={{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|Prolog}}==

=== Using only predicates marked as "builtin" ===

% ===

% Problem description

insert_fresh_vars(_,[],V,[],[],V).

 

=== Alternatively, using predicates from <code>library(list)</code> ===

Using <code>append/3</code> from SWi-Prolog's [https://eu.swi-prolog.org/pldoc/man?section=lists library(list)]

 

% ===

% Main predicate

length(Front, N),

append(Front, [Elem|Back], List).

 

=== Unit Tests ===

Test code using the [https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/plunit.html%27) Unit Testing framework of SWI Prolog].

 

% We use the "R" intermediate var to decouple processing by the predicate

% from subsequent checking against expected result.

rt :- run_tests(sort_disjoint_sublist).

 

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

 

 

 

Or, checking a dictionary for sublist indices, and returning a new (rather than mutated) list:

 

 

 

if __name__ == '__main__':

{{Out}}

<pre>Disjoint sublists at indices [6, 1, 7] sorted:

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

['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'] -> ['h', 'a', 'f', 'e', 'd', 'c', 'b', 'g']</pre>

 

=={{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|Raku}}==

===Inline===

Using L-value slice of the array, and `sort` as a mutating method:

my @indices = 6, 1, 7;

 

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

 

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

 

===Iterative===

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

for @indices.sort -> $insert {

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

my @sortedValues = disjointSort( @values , @indices ) ;

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

 

 

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|Ring}}==

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

indList = [7, 2, 8]

next

? "[" + left(svect, len(svect) - 1) + "]"

{{out}}

 

=={{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|Wren}}==

{{libheader|Wren-sort}}

 

// sorts values in place, leaves indices unsorted

System.print("Initial: %(values)")

sortDisjoint.call(values, indices)

 

{{out}}

 

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