Sort disjoint sublist: Difference between revisions

{{trans|Python}}

 

V sindices = sorted(indices)

V values = sorted(sindices.map(i -> @data[i]))

V i = [6, 1, 7]

sort_disjoint_sublist(&d, i)

 

{{out}}

 

=={{header|Action!}}==

INT i

 

Test(arr,8,ind,3)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sort_disjoint_sublist.png Screenshot from Atari 8-bit computer]

 

=={{header|Ada}}==

use Ada.Text_IO;

 

New_Line;

 

 

=={{header|ALGOL W}}==

Uses the quicksort procedure from the Sorting Algorithms/Quicksort task and a variant for indexed sorting.

% Quicksorts in-place the array of integers v, from lb to ub %

procedure quicksort ( integer array v( * )

writeon( " ]" )

end

{{out}}

<pre>

 

=={{header|APL}}==

∇SDS[⎕]∇

∇

[2] Z←L

∇

{{out}}

<pre>

Uses Foundation framework (through the ObjC interface), and works with versions of AppleScript from OS X 10.10 onwards.

 

use framework "Foundation"

use scripting additions

return lst

end tell

{{Out}}

 

===Idiomatic, vanilla===

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

 

=={{header|Arturo}}==

 

result: new data

inds: new indices

d: [7 6 5 4 3 2 1 0]

 

{{out}}

Much of the code here is proofs, unfolding and re-folding of lists, necessary assertions, memory management enforced by the type system, etc. (Some might say I am somewhat lax in my handling of pointers, using the simplest type '''ptr''' instead of more elaborate types.)

 

staload UN = "prelude/SATS/unsafe.sats"

 

println! values;

free values

 

{{out}}

 

=={{header|AutoHotkey}}==

A := [], B:=[], C := [], D := []

for k, v in Indices

Values[C[A_Index]] := D[A_Index]

return Values

Indices := [7, 2, 8]

Values := Sort_disjoint_sublist(Values, Indices)

for k, v in Values

output .= v ", "

{{out}}

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

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

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

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

NEXT

'''Output:'''

<pre>

 

=={{header|Bracmat}}==

& 6 1 7:?indices

& 0:?sortedValues:?sortedIndices

& !A !value !Z:?values

)

Output:

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

ELENA 5.0 :

import system'routines;

import system'culture;

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

{{out}}

<pre>

 

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

<pre>

 

=={{header|ERRE}}==

 

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

ShowList(LST%[]->O$)

PRINT(O$)

{{out}}

<pre>

 

=={{header|Euphoria}}==

 

function uniq(sequence s)

 

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

 

Output:

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

Output

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

 

=={{header|FreeBASIC}}==

dim as integer index(0 to 2) = {6, 1, 7}, i

 

for i = 0 to 7

print value(i);

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

 

=={{header|Go}}==

 

import (

}

fmt.Println("sorted: ", values)

Output:

<pre>

 

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>

Icon's lists are 1-based, so the example uses (7, 2, 8) as the indices, not (6, 1 7).

 

link sort # get the 'isort' procedure for sorting a list

 

write ()

end

 

Output:

</pre>

 

 

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

 

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

===ES6===

 

'use strict';

 

// MAIN ---

return main();

{{Out}}

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

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]

 

{{works with|Julia|0.6}}

 

sel = unique(sort(s))

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

b = sortselected(a, sel)

 

 

{{out}}

 

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

sort : {x[<x]}

nums : 7 6 5 4 3 2 1 0

nums

7 0 5 4 3 2 1 6

 

=={{header|Kotlin}}==

 

/* in place sort */

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

}

 

{{out}}

 

=={{header|Ksh}}==

#!/bin/ksh

 

done

 

{{out}}<pre>

Before sort: 7 6 5 4 3 2 1 0

 

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

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

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

say 'Idx:' iList.space

return

{{out}}

<pre>

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

Output:

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

With arrays:

 

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

Array.sort cmp temp;

disjoint_sort compare values indices;

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

 

With lists:

 

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

Tested free pascal.

 

program disjointsort;

readln;

end.

<pre>

Before

 

=={{header|Perl}}==

use strict ;

 

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

disjointSort( \@values , @indices ) ;

Output:

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

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

 

=== Shorter Alternative Version ===

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">disjoint_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span>

same output.

 

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

Output:

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

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

<b>Output:</b>

<pre>

=={{header|PureBasic}}==

Based on the C implementation

Protected i, j

SortArray(idx(),#PB_Sort_Ascending)

EndProcedure

 

<pre>Before sort:

7 6 5 4 3 2 1 0

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:

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

#lang racket

 

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

;; --> '(7 0 5 4 3 2 1 6)

 

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

Output:

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

<pre>

 

=={{header|Ring}}==

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

indList = [7, 2, 8]

next

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

{{out}}

<pre>

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

Output

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

=={{header|Run BASIC}}==

Normally we sort with SQLite in memory. Faster and less code

sortIdx$ = "7, 2, 8"

 

next i

wend

 

=={{header|Rust}}==

 

 

 

fn disjoint_sort(array: &mut [impl Ord], indices: &[usize]) {

println!("{:?}", array);

}

 

{{out}}

 

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

<pre>

 

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

Output:

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

=={{header|TUSCRIPT}}==

TUSCRIPT indexing is one based

$$ MODE TUSCRIPT

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

ENDLOOP

PRINT values

Output:

<pre>

 

=={{header|Ursala}}==

#import nat

 

#cast %nL

 

output:

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

int Values, Indices, J, I, T;

[Values:= [7, 6, 5, 4, 3, 2, 1, 0];

for I:= 0 to 8-1 do

[IntOut(0, Values(I)); ChOut(0, ^ )];

 

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

 

{{out}}<pre>L(7,0,5,4,3,2,1,6)</pre>