Sort disjoint sublist: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 10:54, 8 February 2024

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.

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

In case of one-based indexing, rather than the zero-based indexing above, you would use the indices {7, 2, 8} instead.

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.

Cf.

Order disjoint list items

11l

Translation of: Python

F sort_disjoint_sublist(&data, indices)
   V sindices = sorted(indices)
   V values = sorted(sindices.map(i -> @data[i]))
   L(index, value) zip(sindices, values)
      data[index] = value

V d = [7, 6, 5, 4, 3, 2, 1, 0]
V i = [6, 1, 7]
sort_disjoint_sublist(&d, i)
print(d)

Output:

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

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
or android 64 bits with application Termux

/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program sublistSort64.s   */

/************************************/
/* Constantes                       */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc" 
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessStart:        .asciz "Program 64 bits start.\n"
sMessResult:        .ascii "Value  : "
sMessValeur:        .fill 11, 1, ' '            // size => 11
szCarriageReturn:   .asciz "\n"
 
.align 4
ArrayNumber:      .quad    7, 6, 5, 4, 3, 2, 1, 0
.equ NBELEMENTS,     (. - ArrayNumber) / 8
ArrayIndex:       .quad  6,1,7
.equ NBELEMINDEX,     (. - ArrayIndex) / 8
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
ArrayExtract:       .skip 8 * NBELEMINDEX
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:
    ldr x0,qAdrszMessStart
    bl affichageMess
    ldr x4,qAdrArrayNumber         // number array address
    ldr x5,qAdrArrayIndex          // index array address
    ldr x6,qAdrArrayExtract        // extract array address
    mov x3,#0                      // index
1:
    ldr x0,[x5,x3,lsl #3]          // load index
    ldr x1,[x4,x0,lsl #3]          // load value of index
    str x1,[x6,x3,lsl #3]          // store value in array extract
    add x3,x3,#1                   // increment index
    cmp x3,#NBELEMINDEX            // end array index ?
    blt 1b                         // no -> loop

    mov x0,x5                      // index array address
    mov x1,#0                      // first element 
    mov x2,#NBELEMINDEX            // array size
    bl insertionSort
    mov x0,x6                      // extract array address
    mov x1,#0                      // first element 
    mov x2,#NBELEMINDEX            // array size
    bl insertionSort

    mov x3,#0                      // init index
2:
    ldr x0,[x6,x3,lsl #3]          // load value of array extract
    ldr x1,[x5,x3,lsl #3]          // load index
    str x0,[x4,x1,lsl #3]          // store value in number array in index place
    add x3,x3,#1                   // increment indice
    cmp x3,#NBELEMINDEX
    blt 2b

    mov x0,x4                      // number array address
    bl displayArray  
 
100:                               // standard end of the program 
    mov x0, #0                     // return code
    mov x8, #EXIT                  // request to exit program
    svc #0                         // perform the system call
 
qAdrsMessValeur:          .quad  sMessValeur
qAdrszMessStart:          .quad  szMessStart
qAdrszCarriageReturn:     .quad  szCarriageReturn
qAdrsMessResult:          .quad  sMessResult
qAdrArrayNumber:          .quad  ArrayNumber
qAdrArrayIndex:           .quad  ArrayIndex
qAdrArrayExtract:         .quad  ArrayExtract
/******************************************************************/
/*         insertion sort                                              */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element    */
/* x2 contains the number of element */
insertionSort:
    stp x1,lr,[sp,-16]!             // save registers
    stp x2,x3,[sp,-16]! 
    stp x4,x5,[sp,-16]! 
    stp x6,x7,[sp,-16]! 
    add x3,x1,#1                    // start index i
1:                                  // start loop
    ldr x4,[x0,x3,lsl #3]           // load value A[i]
    sub x5,x3,#1                    // index j
2:
    ldr x6,[x0,x5,lsl #3]           // load value A[j]
    cmp x6,x4                       // compare value
    ble 3f
    add x5,x5,#1                    // increment index j
    str x6,[x0,x5,lsl #3]           // store value A[j+1]
    subs x5,x5,#2                   // j = j - 1
    bge 2b                          // loop if j >= 0
3:
    add x5,x5,#1                    // increment index j
    str x4,[x0,x5,lsl #3]           // store value A[i] in A[j+1]
    add x3,x3,#1                    // increment index i
    cmp x3,x2                       // end ?
    blt 1b                          // no -> loop

100:
    ldp x6,x7,[sp],16
    ldp x4,x5,[sp],16
    ldp x2,x3,[sp],16
    ldp x1,lr,[sp],16
    ret 

/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* x0 contains the address of array */
displayArray:
    stp x1,lr,[sp,-16]!
    stp x2,x3,[sp,-16]! 
    mov x2,x0                         // table address
    mov x3,#0
1:                                    // loop display table
    ldr x0,[x2,x3,lsl #3]
    ldr x1,qAdrsMessValeur            // display value
    bl conversion10                   // call function
    ldr x0,qAdrsMessResult
    bl affichageMess                  // display message
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
    add x3,x3,#1
    cmp x3,#NBELEMENTS
    blt 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
100:
    ldp x2,x3,[sp],16
    ldp x1,lr,[sp],16
    ret 

/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"

Output:

Program 64 bits start.
Value  : 7
Value  : 0
Value  : 5
Value  : 4
Value  : 3
Value  : 2
Value  : 1
Value  : 6

Action!

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

BYTE FUNC InSet(INT ARRAY s INT size INT v)
  INT i

  FOR i=0 TO size-1
  DO
    IF s(i)=v THEN
      RETURN (1)
    FI
  OD
RETURN (0)

PROC Sort(INT ARRAY arr INT arrSize
          INT ARRAY ind INT indSize)
  INT i,j,minpos,tmp

  FOR i=0 TO arrSize-2
  DO
    IF InSet(ind,indSize,i) THEN
      minpos=i
      FOR j=i+1 TO arrSize-1
      DO
        IF InSet(ind,indSize,j)=1 AND arr(minpos)>arr(j) THEN
          minpos=j
        FI
      OD
    
      IF minpos#i THEN
        tmp=arr(i)
        arr(i)=arr(minpos)
        arr(minpos)=tmp
      FI
    FI
  OD
RETURN

PROC Test(INT ARRAY arr INT arrSize
          INT ARRAY ind INT indSize)
  PrintE("Array before sort:")
  PrintArray(arr,arrSize)
  PrintE("Indices:")
  PrintArray(ind,indSize)
  Sort(arr,arrSize,ind,indSize)
  PrintE("Array after sort:")
  PrintArray(arr,arrSize)
RETURN

PROC Main()
  INT ARRAY
    arr(8)=[7 6 5 4 3 2 1 0],
    ind(3)=[6 1 7]
  
  Test(arr,8,ind,3)
RETURN

Output:

Screenshot from Atari 8-bit computer

Array before sort:
[7 6 5 4 3 2 1 0]
Indices:
[6 1 7]
Array after sort:
[7 0 5 4 3 2 1 6]

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;

ALGOL W

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

begin % sort a disjoint sub-set of a list                         %
    % Quicksorts in-place the array of integers v, from lb to ub %
    procedure quicksort ( integer array v( * )
                        ; integer value lb, ub
                        ) ;
    if ub > lb then begin
        % more than one element, so must sort %
        integer left, right, pivot;
        left   := lb;
        right  := ub;
        % choosing the middle element of the array as the pivot %
        pivot  := v( left + ( ( right + 1 ) - left ) div 2 );
        while begin
            while left  <= ub and v( left  ) < pivot do left  := left  + 1;
            while right >= lb and v( right ) > pivot do right := right - 1;
            left <= right
        end do begin
            integer swap;
            swap       := v( left  );
            v( left  ) := v( right );
            v( right ) := swap;
            left       := left  + 1;
            right      := right - 1
        end while_left_le_right ;
        quicksort( v, lb,   right );
        quicksort( v, left, ub    )
    end quicksort ;
    % Quicksorts in-place the array of integers v, using          %
    % the indxexes in unsortedIndexes which has bounds lb to ub   %
    % it is assumed all elements of unsortedIndexes are in the    %
    % range for subscripts of v                                   %
    procedure indexedQuicksort ( integer array v, unsortedIndexes ( * )
                               ; integer value lb, ub
                               ) ;
    if ub > lb then begin
        % more than one element, so must sort %
        integer array indexes ( lb :: ub );
        integer left, right, pivot, p;
        % sort the indexes %
        for i := lb until ub do indexes( i ) := unsortedIndexes( i );
        quicksort( indexes, lb, ub );
        % sort the indexed items of the v array %
        left   := lb;
        right  := ub;
        % choosing the middle element of the array as the pivot %
        p      := left + ( ( ( right + 1 ) - left ) div 2 );
        pivot  := v( indexes( p ) );
        while begin
            while left  <= ub and v( indexes( left  ) ) < pivot do left  := left  + 1;
            while right >= lb and v( indexes( right ) ) > pivot do right := right - 1;
            left <= right
        end do begin
            integer swap;
            swap                  := v( indexes( left  ) );
            v( indexes( left  ) ) := v( indexes( right ) );
            v( indexes( right ) ) := swap;
            left                  := left  + 1;
            right                 := right - 1
        end while_left_le_right ;
        indexedQuicksort( v, indexes, lb,   right );
        indexedQuicksort( v, indexes, left, ub    )
    end indexedQuicksort ;
    begin % task % 
        integer array indexes ( 0 :: 2 );
        integer array values  ( 0 :: 7 );
        integer aPos;
        aPos := 0;
        for v := 7, 6, 5, 4, 3, 2, 1, 0 do begin
            values( aPos ) := v;
            aPos           := aPos + 1
        end for_v ;
        indexes( 0 ) := 6;
        indexes( 1 ) := 1;
        indexes( 2 ) := 7;
        i_w := 1; s_w := 0; % set output formatting %
        write( "[" );
        for v := 0 until 7 do writeon( " ", values( v ) );
        writeon( " ]" );
        indexedQuicksort( values, indexes, 0, 2 );
        writeon( " -> [" );
        for v := 0 until 7 do writeon( " ", values( v ) );
        writeon( " ]" )
    end
end.

Output:

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

APL

      ∇SDS[⎕]∇
    ∇
[0]   Z←I SDS L
[1]   L[I[⍋I]]←Z[⍋Z←L[I←∪I]]
[2]   Z←L
    ∇

Output:

      ⎕IO←0
      6 1 7 SDS ⎕←⌽⍳8
7 6 5 4 3 2 1 0
7 0 5 4 3 2 1 6

AppleScript

Functional

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

use AppleScript version "2.4"
use framework "Foundation"
use scripting additions


-- disjointSort :: [Int] -> [Int] -> [Int]
on disjointSort(ixs, xs)
    set ks to sort(ixs)
    script nth -- 1-based index
        on |λ|(k)
            item (succ(k)) of xs
        end |λ|
    end script
    set dct to mapFromList(zip(ks, sort(map(nth, ks))))
    
    script build
        on |λ|(x, i)
            set mb to lookupDict(pred(i) as string, dct)
            if Nothing of mb then
                x
            else
                |Just| of mb
            end if
        end |λ|
    end script
    map(build, xs)
end disjointSort


on run
    disjointSort({6, 1, 7}, {7, 6, 5, 4, 3, 2, 1, 0})
end run



-- GENERIC FUNCTIONS ----------------------------------------------------

-- Just :: a -> Maybe a
on Just(x)
    {type:"Maybe", Nothing:false, Just:x}
end Just

-- Nothing :: Maybe a
on Nothing()
    {type:"Maybe", Nothing:true}
end Nothing

-- length :: [a] -> Int
on |length|(xs)
    set c to class of xs
    if list is c or string is c then
        length of xs
    else
        (2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
    end if
end |length|

-- lookupDict :: a -> Dict -> Maybe b
on lookupDict(k, dct)
    set ca to current application
    set v to (ca's NSDictionary's dictionaryWithDictionary:dct)'s objectForKey:k
    if v ≠ missing value then
        Just(item 1 of ((ca's NSArray's arrayWithObject:v) as list))
    else
        Nothing()
    end if
end lookupDict

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- mapFromList :: [(k, v)] -> Dict
on mapFromList(kvs)
    set tpl to unzip(kvs)
    script
        on |λ|(x)
            x as string
        end |λ|
    end script
    (current application's NSDictionary's ¬
        dictionaryWithObjects:(|2| of tpl) ¬
            forKeys:map(result, |1| of tpl)) as record
end mapFromList

-- min :: Ord a => a -> a -> a
on min(x, y)
    if y < x then
        y
    else
        x
    end if
end min

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- pred :: Enum a => a -> a
on pred(x)
    x - 1
end pred

-- sort :: Ord a => [a] -> [a]
on sort(xs)
    ((current application's NSArray's arrayWithArray:xs)'s ¬
        sortedArrayUsingSelector:"compare:") as list
end sort

-- succ :: Enum a => a -> a
on succ(x)
    1 + x
end succ

-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
    set c to class of xs
    if list is c then
        if 0 < n then
            items 1 thru min(n, length of xs) of xs
        else
            {}
        end if
    else if string is c then
        if 0 < n then
            text 1 thru min(n, length of xs) of xs
        else
            ""
        end if
    else if script is c then
        set ys to {}
        repeat with i from 1 to n
            set v to xs's |λ|()
            if missing value is v then
                return ys
            else
                set end of ys to v
            end if
        end repeat
        return ys
    else
        missing value
    end if
end take

-- Tuple (,) :: a -> b -> (a, b)
on Tuple(a, b)
    {type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple

-- unzip :: [(a,b)] -> ([a],[b])
on unzip(xys)
    set xs to {}
    set ys to {}
    repeat with xy in xys
        set end of xs to |1| of xy
        set end of ys to |2| of xy
    end repeat
    return Tuple(xs, ys)
end unzip

-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
    zipWith(Tuple, xs, ys)
end zip

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on zipWith(f, xs, ys)
    set lng to min(|length|(xs), |length|(ys))
    if 1 > lng then return {}
    set xs_ to take(lng, xs) -- Allow for non-finite
    set ys_ to take(lng, ys) -- generators like cycle etc
    set lst to {}
    tell mReturn(f)
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs_, item i of ys_)
        end repeat
        return lst
    end tell
end zipWith

Output:

{7, 0, 5, 4, 3, 2, 1, 6}

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 AppleScript version "2.3.1" -- Mac OS 10.9 (Mavericks) or later.
use sorter : script "Insertion sort" -- https://www.rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#AppleScript.

on sortValuesAtIndices(values, indices)
    set indexedValues to {}
    repeat with thisIndex in indices
        set end of indexedValues to item thisIndex of values
    end repeat
    
    set indexCount to (count indices)
    
    tell sorter to sort(indexedValues, 1, indexCount)
    tell sorter to sort(indices, 1, indexCount)
    
    repeat with i from 1 to indexCount
        set thisIndex to item i of indices
        set item thisIndex of values to item i of indexedValues
    end repeat
    
    return
end sortValuesAtIndices

-- Test code:
set values to {7, 6, 5, 4, 3, 2, 1, 0}
set indices to {7, 2, 8} -- AppleScript indices are one-based.
sortValuesAtIndices(values, indices)
return values

Output:

{7, 0, 5, 4, 3, 2, 1, 6}

ARM Assembly

Works with: as version Raspberry Pi
or android 32 bits with application Termux

/* ARM assembly Raspberry PI  */
/*  program sublistSort.s   */

/************************************/
/* Constantes                       */
/************************************/
/* for constantes see task include a file in arm assembly */
.include "../constantes.inc"
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessStart:        .asciz "Program 32 bits start.\n"
sMessResult:        .ascii "Value  : "
sMessValeur:        .fill 11, 1, ' '            @ size => 11
szCarriageReturn:   .asciz "\n"
 
.align 4
ArrayNumber:      .int   7, 6, 5, 4, 3, 2, 1, 0
.equ NBELEMENTS,     (. - ArrayNumber) / 4
ArrayIndex:       .int 6,1,7
.equ NBELEMINDEX,     (. - ArrayIndex) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
ArrayExtract:       .skip 4 * NBELEMINDEX
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:
    ldr r0,iAdrszMessStart
    bl affichageMess
    ldr r4,iAdrArrayNumber         @ number array address
    ldr r5,iAdrArrayIndex          @ index array address
    ldr r6,iAdrArrayExtract        @ extract array address
    mov r3,#0                      @ index
1:
    ldr r0,[r5,r3,lsl #2]          @ load index
    ldr r1,[r4,r0,lsl #2]          @ load value of index
    str r1,[r6,r3,lsl #2]          @ store value in array extract
    add r3,r3,#1                   @ increment index
    cmp r3,#NBELEMINDEX            @ end array index ?
    blt 1b                         @ no -> loop

    mov r0,r5                      @ index array address
    mov r1,#0                      @ first element 
    mov r2,#NBELEMINDEX            @ array size
    bl insertionSort
    mov r0,r6                      @ extract array address
    mov r1,#0                      @ first element 
    mov r2,#NBELEMINDEX            @ array size
    bl insertionSort

    mov r3,#0                      @ init index
2:
    ldr r0,[r6,r3,lsl #2]          @ load value of array extract
    ldr r1,[r5,r3,lsl #2]          @ load index
    str r0,[r4,r1,lsl #2]          @ store value in number array in index place
    add r3,r3,#1                   @ increment indice
    cmp r3,#NBELEMINDEX
    blt 2b

    mov r0,r4                      @ number array address
    bl displayArray  
 
100:                               @ standard end of the program 
    mov r0, #0                                      @ return code
    mov r7, #EXIT                  @ request to exit program
    svc #0                         @ perform the system call
 
iAdrsMessValeur:          .int sMessValeur
iAdrszMessStart:          .int szMessStart
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrArrayNumber:          .int ArrayNumber
iAdrArrayIndex:           .int ArrayIndex
iAdrArrayExtract:         .int ArrayExtract
/******************************************************************/
/*         insertion sort                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element    */
/* r2 contains the number of element */
insertionSort:
    push {r2-r6,lr}                 @ save registers
    add r3,r1,#1                    @ start index i
1:                                  @ start loop
    ldr r4,[r0,r3,lsl #2]           @ load value A[i]
    sub r5,r3,#1                    @ index j
2:
    ldr r6,[r0,r5,lsl #2]           @ load value A[j]
    cmp r6,r4                       @ compare value
    ble 3f
    add r5,#1                       @ increment index j
    str r6,[r0,r5,lsl #2]           @ store value A[j+1]
    subs r5,#2                      @ j = j - 1
    bge 2b                          @ loop if j >= 0
3:
    add r5,#1                       @ increment index j
    str r4,[r0,r5,lsl #2]           @ store value A[i] in A[j+1]
    add r3,#1                       @ increment index i
    cmp r3,r2                       @ end ?
    blt 1b                          @ no -> loop

100:
    pop {r2-r6,pc}

/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayArray:
    push {r0-r3,lr}                                    @ save registers
    mov r2,r0                                          @ table address
    mov r3,#0
1:                                                    @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsMessValeur                         @ display value
    bl conversion10                                 @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                                @ display message
    add r3,#1
    cmp r3,#NBELEMENTS
    blt 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r0-r3,lr}
    bx lr

/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language ARM assembly*/
.include "../affichage.inc"

Output:

Program 32 bits start.
Value  : 7
Value  : 0
Value  : 5
Value  : 4
Value  : 3
Value  : 2
Value  : 1
Value  : 6

Arturo

sortDisjoint: function [data, indices][
    result: new data
    inds: new indices
    sort 'inds

    vals: new []
    loop inds 'i -> 'vals ++ result\[i]
    sort 'vals

    loop.with:'j inds 'i -> result\[i]: vals\[j]
    return result
]
 
d: [7 6 5 4 3 2 1 0]
print sortDisjoint d [6 1 7]

Output:

7 0 5 4 3 2 1 6

ATS

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

#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"

(* For simplicity, I implement this task only for sorting values of
   non-linear type. That would include all the basic integer types,
   garbage-collected strings, etc.
   
   Also I freely create arrays as workspace, although the size of any
   workspace array is equal only to the number of indices (not to the
   number of values). *)

extern fn {a : t@ype}
sort_disjoint_sublist$cmp : (a, a) -<> int

fn {a : t@ype}
sort_disjoint_sublist
          {m       : int}
          {n       : int}
          (values  : &list_vt (a, m) >> _,
           indices : list ([i : nat | i < m] int i, n))
    : void =
  let
    typedef index = [i : nat | i < m] int i

    prval () = lemma_list_vt_param values
    prval () = lemma_list_param indices
    val num_values : size_t m = i2sz (list_vt_length values)
    and num_indices : size_t n = i2sz (list_length indices)

    (* Put the indices in ascending order. *)
    val @(pf_ix, pfgc_ix | p_ix) =
      array_ptr_alloc<index> num_indices
    macdef ix = !p_ix
    val () = array_initize_list<index> (ix, sz2i num_indices, indices)
    implement
    array_quicksort$cmp<index> (x, y) =
      if x < y then ~1 else 1
    val () = array_quicksort<index> (ix, num_indices)

    (* Initialize a "refs" array with pointers to the relevant list
       nodes. The pointers will be in ascending index order. *)
    val @(pf_refs, pfgc_refs | p_refs) =
      array_ptr_alloc<ptr> num_indices
    fun
    init_refs {j      : nat | j <= m}
              {i      : nat | i <= n}
              {p_refs : addr}
              .<m - j>.
              (pf_refs : !array_v (ptr?, p_refs + (i * sizeof ptr),
                                   n - i)
                          >> array_v (ptr, p_refs + (i * sizeof ptr),
                                      n - i) |
               ix      : &array (index, n),
               p_refs  : ptr p_refs,
               i       : size_t i,
               values  : &list_vt (a, m - j),
               j       : size_t j)
        :<!wrt> void =
      if i < num_indices then
        case+ values of
        | list_vt_nil () => $effmask_exn assertloc (false)
        | @ list_vt_cons (head, tail) =>
          if j = ix[i] then
            let
              prval @(pf_elem, pf_rest) = array_v_uncons pf_refs
              val p = ptr_add<ptr> (p_refs, i)
              val () = ptr_set<ptr> (pf_elem | p, addr@ values)
              val () = init_refs (pf_rest | ix, p_refs, succ i,
                                            tail, succ j)
              prval () = pf_refs := array_v_cons (pf_elem, pf_rest)
              prval () = fold@ values
            in
            end
          else
            let
              val () = init_refs (pf_refs | ix, p_refs, i,
                                            tail, succ j)
              prval () = fold@ values
            in
            end
      else
        let
          prval () = pf_refs := array_v_unnil_nil{ptr?, ptr} pf_refs
        in
        end
    val () = init_refs (pf_refs | ix, p_refs, i2sz 0, values, i2sz 0)

    (* Sort through the "refs" pointers. Here we will do that by
       copying the values to an array, sorting the array, then writing
       the sorted values back. One could also do the sort in place,
       however. *)
    val @(pf_vals, pfgc_vals | p_vals) =
      array_ptr_alloc<a> num_indices
    macdef vals = !p_vals
    implement
    array_initize$init<a> (i, x) =
      let
        val @(pf1, fpf1 | p1) = $UN.ptr_vtake{array (ptr, n)} p_refs
        macdef refs = !p1
        val i1 = g1ofg0 i
        prval () = lemma_g1uint_param i1
        val () = assertloc (i1 < num_indices)
        val @(pf2, fpf2 | p2) = $UN.ptr_vtake{List1_vt a} (refs[i1])
        val+ @ list_vt_cons (head, tail) = !p2
        val () = x := head
        prval () = fold@ (!p2)
        prval () = fpf2 pf2
        prval () = fpf1 pf1
      in
      end
    val () = array_initize<a> (vals, num_indices)
    implement
    array_quicksort$cmp<a> (x, y) =
      sort_disjoint_sublist$cmp<a> (x, y)
    val () = array_quicksort<a> (vals, num_indices)
    fun
    write_back_values
              {i       : nat | i <= n}
              {p_refs  : addr}
              (pf_refs : !array_v (ptr, p_refs, n) |
               p_refs  : ptr p_refs,
               vals    : &array (a, n),
               i       : size_t i)
        : void =
      if i <> num_indices then
        let
          macdef refs = !p_refs
          val @(pf1, fpf1 | p1) = $UN.ptr_vtake{List1_vt a} (refs[i])
          val+ @ list_vt_cons (head, tail) = !p1
          val () = head := vals[i]
          prval () = fold@ (!p1)
          prval () = fpf1 pf1
        in
          write_back_values (pf_refs | p_refs, vals, succ i)
        end
    val () = write_back_values (pf_refs | p_refs, vals, i2sz 0)
  in
    array_ptr_free (pf_ix, pfgc_ix | p_ix);
    array_ptr_free (pf_refs, pfgc_refs | p_refs);
    array_ptr_free (pf_vals, pfgc_vals | p_vals)
  end

implement
sort_disjoint_sublist$cmp<int> (x, y) =
  if x < y then
    ~1
  else if y < x then
    1
  else
    0

implement
main0 () =
  let
    var values = $list_vt{int} (7, 6, 5, 4, 3, 2, 1, 0)
    val indices = $list{[i : nat | i < 8] int i} (6, 1, 7)
  in
    println! values;
    sort_disjoint_sublist<int> (values, indices);
    println! values;
    free values
  end

Output:

$ patscc -DATS_MEMALLOC_GCBDW -O3 sort_disjoint_sublist_task.dats -lgc && ./a.out
7, 6, 5, 4, 3, 2, 1, 0
7, 0, 5, 4, 3, 2, 1, 6

AutoHotkey

Sort_disjoint_sublist(Values, Indices){
    A := [], B:=[], C := [], D := []
    for k, v in Indices
        A[v] := 1 , B[Values[v]] := v
    for k, v in A
        C.Push(k)
    for k, v in B
        D.Push(k)
    for k, v in D
        Values[C[A_Index]] := D[A_Index]
    return Values
}

Examples:

Values := [7, 6, 5, 4, 3, 2, 1, 0]
Indices := [7, 2, 8]
Values := Sort_disjoint_sublist(Values, Indices)
for k, v in Values
    output .= v ", "
MsgBox % "[" Trim(output, ", ") "]"					; show output

Output:

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

BASIC

Applesoft BASIC

The GW-BASIC solution works without any changes.

BBC BASIC

Works with: BBC BASIC for Windows

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

Output:

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

Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4

The GW-BASIC solution works without any changes.

100 cls
110 dim values(7)
120 data 7,6,5,4,3,2,1,0
130 for i = 0 to 7
140   read values(i)
150 next
160 dim indices(2)
170 data 6,1,7
180 for i = 0 to 2
190   read indices(i)
200 next
210 print "Before sort:"
220 for i = 0 to ubound(values)
230   print values(i);
240 next i
250 print
260 print
270 print "After sort:"
280 for i = 0 to 1
290   if values(indices(i)) > values(indices(i+1)) then
300      temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp
310   endif
320 next i
330 for i = 0 to ubound(values)
340   print values(i);
350 next i
360 print
370 end

Output:

Same as FreeBASIC entry.

FreeBASIC

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

for i = 0 to 1
    if value(index(i))>value(index(i+1)) then
        swap value(index(i)), value(index(i+1))
    end if
next i

for i  = 0 to 7
    print value(i);
next i : print

Output:

 7 0 5 4 3 2 1 6

GW-BASIC

Works with: Applesoft BASIC

Works with: Chipmunk Basic

Works with: PC-BASIC version any

Works with: QBasic

Works with: Quite BASIC

100 CLS : rem  100 HOME for Applesoft BASIC
110 DIM V(7)
120 DATA 7,6,5,4,3,2,1,0
130 FOR C = 0 TO 7
140   READ V(C)
150 NEXT C
160 DIM I(2)
170 DATA 6,1,7
180 FOR C = 0 TO 2
190   READ I(C)
200 NEXT C
210 PRINT "Before sort:"
220 FOR C = 0 TO 7
230   PRINT V(C); " ";
240 NEXT C
250 PRINT
260 PRINT
270 PRINT "After sort:"
280 FOR C = 0 TO 1
290   IF V(I(C)) > V(I(C+1)) THEN LET T = V(I(C)) : LET V(I(C)) = V(I(C+1)) : LET V(I(C+1)) = T
300 NEXT C
310 FOR C = 0 TO 7
320   PRINT V(C); " ";
330 NEXT C
340 END

Output:

Same as FreeBASIC entry.

Minimal BASIC

Works with: QBasic

Works with: QuickBasic

Works with: Applesoft BASIC

Works with: BASICA

Works with: Chipmunk Basic

Works with: GW-BASIC

Works with: MSX BASIC version any

110 DIM V(7)
120 DATA 7,6,5,4,3,2,1,0
130 FOR C = 0 TO 7
140   READ V(C)
150 NEXT C
160 DIM I(2)
170 DATA 6,1,7
180 FOR C = 0 TO 2
190   READ I(C)
200 NEXT C
210 PRINT "BEFORE SORT:"
220 FOR C = 0 TO 7
230   PRINT V(C);" ";
240 NEXT C
250 PRINT
260 PRINT
270 PRINT "AFTER SORT:"
280 FOR C = 0 TO 1
290   IF V(I(C)) > V(I(C+1)) THEN 310
300   GOTO 340
310   LET T = V(I(C))
320   LET V(I(C)) = V(I(C+1))
330   LET V(I(C+1)) = T
340 NEXT C
350 FOR C = 0 TO 7
360   PRINT V(C);" ";
370 NEXT C
380 END

Output:

Same as FreeBASIC entry.

MSX Basic

Works with: MSX BASIC version any

The GW-BASIC solution works without any changes.

PureBasic

Based on the C implementation

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

Output:

Before sort:
7 6 5 4 3 2 1 0

After sort:
7 0 5 4 3 2 1 6

Run BASIC

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

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

True BASIC

OPTION BASE 0

SUB SWAP(vb1, vb2)
    LET temp = vb1
    LET vb1 = vb2
    LET vb2 = temp
END SUB

DIM values(7)
DATA 7, 6, 5, 4, 3, 2, 1, 0
FOR i = 0 TO 7
    READ values(i)
NEXT i
DIM indices(2)
DATA 6, 1, 7
FOR i = 0 TO 2
    READ indices(i)
NEXT i
PRINT "Before sort:"
FOR i = 0 TO 7 !UBOUND(values)
    PRINT values(i);
NEXT i
PRINT
PRINT
PRINT "After sort:"
FOR i = 0 TO 1
    IF values(indices(i)) > values(indices(i+1)) THEN CALL SWAP (values(indices(i)), values(indices(i+1)))
NEXT i
FOR i = 0 TO 7 !UBOUND(values)
    PRINT values(i);
NEXT i

END

Output:

Same as BASIC entry.

Yabasic

dim values(7)
values(0) = 7 : values(1) = 6 : values(2) = 5
values(3) = 4 : values(4) = 3 : values(5) = 2
values(6) = 1 : values(7) = 0

dim indices(2)
indices(0) = 6 : indices(1) = 1 : indices(2) = 7

print "Before sort:"
for i = 0 to arraysize(values(),1)
    print values(i), " ";
next i

print "\n\nAfter sort:"
for i = 0 to 1
    if values(indices(i)) > values(indices(i + 1)) then
		temp = values(indices(i)) : values(indices(i)) = values(indices(i+1)) : values(indices(i+1)) = temp
    end if
next i
for i = 0 to arraysize(values(),1)
    print values(i), " ";
next i
end

Output:

Same as BASIC entry.

Bracmat

7 6 5 4 3 2 1 0:?values
& 6 1 7:?indices
& 0:?sortedValues:?sortedIndices
&   whl
  ' ( !indices:%?i ?indices
    & !values:? [!i %@?value ?
    & (!value.)+!sortedValues:?sortedValues
    & (!i.)+!sortedIndices:?sortedIndices
    )
&   whl
  ' ( !sortedIndices:(?i.)+?sortedIndices
    & !values:?A [!i %@? ?Z
    & !sortedValues:(?value.)+?sortedValues
    & !A !value !Z:?values
    )
& out$!values;

Output:

7 0 5 4 3 2 1 6

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

C#

using System;
using System.Linq;
using System.Collections.Generic;
     
public class Test
{
    public static void Main()
    {
        var list = new List<int>{ 7, 6, 5, 4, 3, 2, 1, 0 };
        list.SortSublist(6, 1, 7);
        Console.WriteLine(string.Join(", ", list));
    }
}
     
public static class Extensions
{
    public static void SortSublist<T>(this List<T> list, params int[] indices)
        where T : IComparable<T>
    {
        var sublist = indices.OrderBy(i => i)
            .Zip(indices.Select(i => list[i]).OrderBy(v => v),
                (Index, Value) => new { Index, Value });
     
        foreach (var entry in sublist) {
            list[entry.Index] = entry.Value;
        }
    }
     
}

C++

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

Output:

7 0 5 4 3 2 1 6

Translation of: Go

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

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

Output:

7 0 5 4 3 2 1 6

Clojure

(defn disjoint-sort [coll idxs]
  (let [val-subset (keep-indexed #(when ((set idxs) %) %2) coll)
        replacements (zipmap (set idxs) (sort val-subset))]
    (apply assoc coll (flatten (seq replacements)))))

Output:

user=> (disjoint-sort [7 6 5 4 3 2 1 0] #{6 1 7})
[7 0 5 4 3 2 1 6]

Common Lisp

(defun disjoint-sort (values indices)
  "Destructively perform a disjoin sublist sort on VALUES with INDICES."
  (loop :for element :in
     (sort (loop :for index :across indices
              :collect (svref values index))
           '<)
     :for index :across (sort indices '<)
     :do (setf (svref values index) element))
  values)

Output:

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

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

    data.indexed(indices.sort()).sort();

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

Lower Level version

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]);
}

Simple Alternative Version

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]);
}

Delphi

Works with: Delphi version 6.0

Library: SysUtils,StdCtrls

{Test values}

var Values: array [0..7] of integer = (7, 6, 5, 4, 3, 2, 1, 0);
var indices: array [0..2] of integer = (6, 1, 7);

function CompareValues(Item1, Item2: Pointer): Integer;
{Compare the values pointed to by the indices}
begin
Result:=Values[integer(Item1)]-Values[integer(Item2)];
end;

function CompareIndices(Item1, Item2: Pointer): Integer;
{Compare the indices themselves}
begin
Result:=integer(Item1)-integer(Item2);
end;

procedure SortDisjointSublist(Memo: TMemo);
var L1,L2: TList;
var I,Inx1,Inx2: integer;
var OutList: TIntegerDynArray;
var S: string;
begin
L1:=TList.Create;
L2:=TList.Create;
try
{Copy values array to output array}
SetLength(OutList,Length(Values));
for I:=0 to High(Values) do OutList[I]:=Values[I];
{Load two lists with the indices}
for I:=0 to High(Indices) do
	begin
	L1.Add(Pointer(Indices[I]));
	L2.Add(Pointer(Indices[I]));
	end;
{Sort by index and by value}
L1.Sort(CompareValues);
L2.Sort(CompareIndices);
{Copy the sorted values through the sorted indices}
for I:=0 to L1.Count-1 do
  OutList[Integer(L2[I])]:=Values[Integer(L1[I])];
{Display the result}
S:='[';
for I:=0 to High(OutLIst) do
 	begin
	if I>0 then S:=S+' ';
 	S:=S+IntToStr(OutList[I]);
 	end;
S:=S+']';
Memo.Lines.Add(S);
finally
 L1.Free;
 L2.Free;
 end;
end;

Output:


[7 0 5 4 3 2 1 6]

Elapsed Time: 0.626 ms.

EasyLang

val[] = [ 7 6 5 4 3 2 1 0 ]
ind[] = [ 7 2 8 ]
#
for i = 1 to len ind[] - 1
   for j = i + 1 to len ind[]
      if ind[j] < ind[i]
         swap ind[j] ind[i]
      .
   .
. 
for i = 1 to len ind[] - 1
   for j = i + 1 to len ind[]
      if val[ind[j]] < val[ind[i]]
         swap val[ind[j]] val[ind[i]]
      .
   .
.
print val[]

EchoLisp

(define (sort-disjoint values indices)
    (define sorted (list-sort <
    (for/list [(v values) (i (in-naturals))]
	#:when (member i indices)  v)))
	
    (for/list [(v values) (i (in-naturals))]
	(if (not (member i indices)) v
	(begin0
		(first sorted)
		(set! sorted (rest sorted))))))
		
(define (task)
	(sort-disjoint '[7 6 5 4 3 2 1 0] {6 1 7}))
	
(task)
    → (7 0 5 4 3 2 1 6)

Elena

ELENA 6.x :

import extensions;
import system'routines;
import system'culture;
 
extension op
{
    sortSublist(indices)
    {
        var subList := indices.orderBy::(x => x)
                            .zipBy(indices.selectBy::(i => self[i]) 
                                .orderBy::(x => x), (index,val => new{ Index = index; Value = val; })) 
                            .toArray();
 
        var list := self.clone();
        subList.forEach::(r)
        {
            list[r.Index] := r.Value
        };
 
        ^ list
    }
}
 
public program()
{
    var list := new int[]{ 7, 6, 5, 4, 3, 2, 1, 0 };
 
    console.printLine(list.sortSublist(new int[]{6, 1, 7}).asEnumerable())
}

Output:

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

Elixir

defmodule Sort_disjoint do
  def sublist(values, indices) when is_list(values) and is_list(indices) do
    indices2 = Enum.sort(indices)
    selected = select(values, indices2, 0, []) |> Enum.sort
    replace(values, Enum.zip(indices2, selected), 0, [])
  end
  
  defp select(_, [], _, selected), do: selected
  defp select([val|t], [i|rest], i, selected), do: select(t, rest, i+1, [val|selected])
  defp select([_|t], indices, i, selected), do: select(t, indices, i+1, selected)
  
  defp replace(values, [], _, list), do: Enum.reverse(list, values)
  defp replace([_|t], [{i,v}|rest], i, list), do: replace(t, rest, i+1, [v|list])
  defp replace([val|t], indices, i, list), do: replace(t, indices, i+1, [val|list])
end

values = [7, 6, 5, 4, 3, 2, 1, 0]
indices = [6, 1, 7]
IO.inspect Sort_disjoint.sublist(values, indices)

Output:

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

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

Output:

20> sort_disjoint:task().
[7,0,5,4,3,2,1,6]

ERRE

PROGRAM DISJOINT

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

DIM L%[7],I%[2],Z%[2]
PROCEDURE SHOWLIST(L%[]->O$)
      LOCAL I%
      O$="["
      FOR I%=0 TO UBOUND(L%,1) DO
        O$=O$+STR$(L%[I%])+", "
      END FOR
      O$=LEFT$(O$,LEN(O$)-2)+"]"
END PROCEDURE

PROCEDURE SORT(Z%[]->Z%[])
   LOCAL N%,P%,FLIPS%
   P%=UBOUND(Z%,1)
   FLIPS%=TRUE
   WHILE FLIPS% DO
      FLIPS%=FALSE
      FOR N%=0 TO P%-1 DO
        IF Z%[N%]>Z%[N%+1] THEN SWAP(Z%[N%],Z%[N%+1]) FLIPS%=TRUE
      END FOR
   END WHILE
END PROCEDURE

PROCEDURE SortDisJoint(L%[],I%[]->L%[])
      LOCAL J%,N%
      LOCAL DIM T%[2]

      N%=UBOUND(I%,1)
      FOR J%=0 TO N% DO
        T%[J%]=L%[I%[J%]]
      END FOR
      SORT(I%[]->I%[])
      SORT(T%[]->T%[])
      FOR J%=0 TO N% DO
        L%[I%[J%]]=T%[J%]
      END FOR
END PROCEDURE

BEGIN
  LST%[]=(7,6,5,4,3,2,1,0)
  INDICES%[]=(6,1,7)
  SortDisJoint(LST%[],INDICES%[]->LST%[])
  ShowList(LST%[]->O$)
  PRINT(O$)
END PROGRAM

Output:

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

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}

Output:

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

F#

Translation of: 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 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]))

Factor

: disjoint-sort! ( values indices -- values' )
    over <enumerated> nths unzip swap [ natural-sort ] bi@
    pick [ set-nth ] curry 2each ;

Output:

IN: scratchpad { 7 6 5 4 3 2 1 0 } { 6 1 7 } disjoint-sort! .
{ 7 0 5 4 3 2 1 6 }

Fortran

Works with: Fortran version 90 and later

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

Output:

           7           0           5           4           3           2           1           6

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

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.

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

Groovy

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

def sparseSort = { a, indices = ([] + (0..<(a.size()))) ->
    indices.sort().unique()
    a[indices] = a[indices].sort()
    a
}

Test:

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

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.

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 <- (zip (sort is) . sort) Control.Applicative.<$> mapM (readArray as) is
     mapM_ (uncurry (writeArray as)) sub
     return as

main :: IO ()
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

Or, in terms of Data.Map:

import Data.Map as M (fromList, keys, lookup)
import Control.Applicative ((<|>))
import Data.Maybe (mapMaybe)
import Data.List (sort)

disjointSort :: [Int] -> [Int] -> [Int]
disjointSort ixs xs =
  let ks = sort ixs
      dctAll = fromList $ zip xs [0 ..]
      dctIx = fromList $ zip ks $ sort (mapMaybe (`M.lookup` dctAll) ks)
  in mapMaybe
       ((<|>) <$> (`M.lookup` dctIx) <*> (`M.lookup` dctAll))
       (keys dctAll)

main :: IO ()
main = print $ disjointSort [6, 1, 7] [7, 6, 5, 4, 3, 2, 1, 0]

Output:

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

Icon and Unicon

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

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

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

every put (values, result[!indices])

effectively loops through each index, putting result[index] into the list 'values'.

Io

Io does not come with a set type.

List disjointSort := method(indices,
    sortedIndices := indices unique sortInPlace
    sortedValues := sortedIndices map(idx,at(idx)) sortInPlace
    sortedValues foreach(i,v,atPut(sortedIndices at(i),v))
    self
)

list(7,6,5,4,3,2,1,0) disjointSort(list(6,1,7)) println

Output:

list(7, 0, 5, 4, 3, 2, 1, 6)

J

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

   7 6 5 4 3 2 1 0 (/:~@:{`[`]}~ /:~@~.) 6 1 7
7 0 5 4 3 2 1 6

Compare this with:

   6 1 7 /:~@:{`[`]} 7 6 5 4 3 2 1 0
7 1 5 4 3 2 0 6

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

Works with: Java version 1.5+

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

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

Output:

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

Works with: Java version 1.5+

Translation of: Go

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

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

Output:

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

JavaScript

ES5

Iterative

Does not check for duplicate indices.

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

Functional

(function () {
    'use strict';

    // disjointSort :: [a] -> [Int] -> [a]
    function disjointSort(xs, indices) {

        // Sequence of indices discarded
        var indicesSorted = indices.sort(),
            subsetSorted = indicesSorted
            .map(function (i) {
                return xs[i];
            })
            .sort();

        return xs
            .map(function (x, i) {
                var iIndex = indicesSorted.indexOf(i);

                return iIndex !== -1 ? (
                    subsetSorted[iIndex]
                ) : x;
            });
    }

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

})();

Output:

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

ES6

(() => {
  'use strict';

  // disjointSort :: [Int] -> [Int] -> [Int]
  const disjointSort = (indices, xs) => {
    const
      ks = sort(indices),
      dct = mapFromList(
        zip(ks, sort(map(k => xs[k], ks)))
      );
    return map(
      (x, i) => {
        const v = dct[i.toString()];
        return undefined !== v ? v : x;
      },
      xs
    );
  };

  // main :: IO ()
  const main = () =>
    showLog(
      disjointSort(
        [6, 1, 7],
        [7, 6, 5, 4, 3, 2, 1, 0]
      )
    );

  // GENERIC FUNCTIONS ----------------------------

  // length :: [a] -> Int
  const length = xs => xs.length || Infinity;

  // map :: (a -> b) -> [a] -> [b]
  const map = (f, xs) => xs.map(f);

  // mapFromList :: [(k, v)] -> Dict
  const mapFromList = kvs =>
    kvs.reduce(
      (a, kv) => {
        const k = kv[0];
        return Object.assign(a, {
          [(('string' === typeof k) && k) || showJSON(k)]: kv[1]
        });
      }, {}
    );

  // showJSON :: a -> String
  const showJSON = x => JSON.stringify(x);

  // showLog :: a -> IO ()
  const showLog = (...args) =>
    console.log(
      args
      .map(JSON.stringify)
      .join(' -> ')
    );

  // sort :: Ord a => [a] -> [a]
  const sort = xs => xs.slice()
    .sort((a, b) => a < b ? -1 : (a > b ? 1 : 0));

  // take :: Int -> [a] -> [a]
  // take :: Int -> String -> String
  const take = (n, xs) =>
    xs.constructor.constructor.name !== 'GeneratorFunction' ? (
      xs.slice(0, n)
    ) : [].concat.apply([], Array.from({
      length: n
    }, () => {
      const x = xs.next();
      return x.done ? [] : [x.value];
    }));

  // Tuple (,) :: a -> b -> (a, b)
  const Tuple = (a, b) => ({
    type: 'Tuple',
    '0': a,
    '1': b,
    length: 2
  });

  // Use of `take` and `length` here allows for zipping with non-finite
  // lists - i.e. generators like cycle, repeat, iterate.

  // zip :: [a] -> [b] -> [(a, b)]
  const zip = (xs, ys) => {
    const lng = Math.min(length(xs), length(ys));
    return Infinity !== lng ? (() => {
      const bs = take(lng, ys);
      return take(lng, xs).map((x, i) => Tuple(x, bs[i]));
    })() : zipGen(xs, ys);
  };


  // MAIN ---
  return main();
})();

Output:

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

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:

def setpaths(indices; values):
  reduce range(0; indices|length) as $i
    (.; .[indices[$i]] = values[$i]);
      
def disjointSort(indices):
  (indices|unique) as $ix   # "unique" sorts
  # Set $sorted to the sorted array of values at $ix:
  | ([ .[ $ix[] ] ] | sort) as $sorted  
  | setpaths( $ix; $sorted) ;

Example:

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

produces:

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

Julia

Works with: Julia version 0.6

function sortselected(a::AbstractVector{<:Real}, s::AbstractVector{<:Integer})
    sel = unique(sort(s))
    if sel[1] < 1 || length(a) < sel[end]
        throw(BoundsError())
    end
    b = collect(copy(a))
    b[sel] = sort(b[sel])
    return b
end

a = [7, 6, 5, 4, 3, 2, 1, 0]
sel = [7, 2, 8]
b = sortselected(a, sel)

println("Original: $a\n\tsorted on $sel\n -> sorted array: $b")

Output:

Original: [7, 6, 5, 4, 3, 2, 1, 0]
	sorted on [7, 2, 8]
 -> sorted array: [7, 0, 5, 4, 3, 2, 1, 6]

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
i : sort 6 1 7 
nums[i] : sort nums[i]
nums
7 0 5 4 3 2 1 6

Kotlin

// version 1.1.51

/* in place sort */
fun IntArray.sortDisjoint(indices: Set<Int>) {
    val sortedSubset = this.filterIndexed { index, _ -> index in indices }.sorted()
    if (sortedSubset.size < indices.size) 
        throw IllegalArgumentException("Argument set contains out of range indices")
    indices.sorted().forEachIndexed { index, value -> this[value] = sortedSubset[index] }
}

fun main(args: Array<String>) {
    val values = intArrayOf(7, 6, 5, 4, 3, 2, 1, 0)
    val indices = setOf(6, 1, 7)
    println("Original array : ${values.asList()} sorted on indices $indices")
    values.sortDisjoint(indices)   
    println("Sorted array   : ${values.asList()}")
}

Output:

Original array : [7, 6, 5, 4, 3, 2, 1, 0] sorted on indices [6, 1, 7]
Sorted array   : [7, 0, 5, 4, 3, 2, 1, 6]

Ksh

#!/bin/ksh

# Sort disjoint sublist

#	# Variables:
#
typeset -a arr_Val=( 7 6 5 4 3 2 1 0 )
typeset -a arr_Ind=( 6 1 7 )
integer i

#	# Functions:
#
#       # Function _insertionSort(array) - Insertion sort of array of integers
#
function _insertionSort {
	typeset _arr ; nameref _arr="$1"
	typeset _i _j _val ; integer _i _j _val

	for (( _i=1; _i<${#_arr[*]}; _i++ )); do
		_val=${_arr[_i]}
		(( _j = _i - 1 ))
		while (( _j>=0 && _arr[_j]>_val )); do
			_arr[_j+1]=${_arr[_j]}
			(( _j-- ))
		done
		_arr[_j+1]=${_val}
	done
}

 ######
# main #
 ######
print "Before sort: ${arr_Val[*]}"

typeset -a arr_2sort
for ((i=0; i<${#arr_Ind[*]}; i++)); do
	arr_2sort+=( ${arr_Val[${arr_Ind[i]}]} )
done

_insertionSort arr_2sort	# Sort the chosen values
_insertionSort arr_Ind		# Sort the indices

for ((i=0; i<${#arr_Ind[*]}; i++)); do
	arr_Val[${arr_Ind[i]}]=${arr_2sort[i]}
done

print "After  sort: ${arr_Val[*]}"

Output:

Before sort: 7 6 5 4 3 2 1 0

After sort: 7 0 5 4 3 2 1 6

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

Output:

7  0  5  4  3  2  1  6

Maple

sortDisjoint := proc(values, indices::set)
	local vals,inds,i:
	vals := sort([seq(values[i], i in indices)]):
	inds := sort(convert(indices, Array)):
	for i to numelems(vals) do
		values(inds[i]) := vals[i]:
	od:
end proc:
tst := Array([7,6,5,4,3,2,1,0]):	
sortDisjoint(tst,{7,2,8});

Output:

[7 0 5 4 3 2 1 6]

Mathematica/Wolfram Language

Values = { 7, 6, 5, 4, 3, 2, 1, 0} ; Indices = { 7, 2, 8 };
Values[[Sort[Indices]]] = Sort[Values[[Indices]]];
Values

Output:

{ 7, 0, 5, 4, 3, 2, 1, 6 }

MiniScript

sortDisjointSublist = function(arr, indexes)
	indexes.sort
	newArr = arr[:]
	sublist = []
	for i in indexes
		sublist.push(arr[i])
	end for
	sublist.sort
	for i in range(0, indexes.len - 1)
		arrIx = indexes[i]
		newArr[arrIx] = sublist[i]
	end for
	return newArr
end function

print sortDisjointSublist([7,6,5,4,3,2,1,0], [6,1,7])

Output:

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

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

Output:

In:  7 6 5 4 3 2 1 0
Out: 7 0 5 4 3 2 1 6
Idx: 7 2 8

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

Nim

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

Output:

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

Objective-C

Translation of: Go

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

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

Output:

OCaml

With arrays:

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

With lists:

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

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

Output:

Sorted data is: [7, 0, 5, 4, 3, 2, 1, 6]

Order

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

PARI/GP

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

pascal

Tested free pascal.

    program disjointsort;

    procedure swap(var a, b: Integer);
    var
    temp: Integer;
    begin
    temp := a;
    a := b;
    b := temp;
    end;

    procedure d_sort(var index,arr:array of integer);
    var
    n,i,j,num:integer;
    begin
    num:=length(index);
    for n:=1 to 2 do
    begin
    for i:=0 to num-1 do
    begin
    for j:=i+1 to num-1 do
    begin
     if n=1 then if index[j]<index[i] then swap(index[j],index[i]);
     if n=2 then if arr[index[j]]<arr[index[i]] then swap(arr[index[j]],arr[index[i]]);
    end;
    end;
    end;
    end;

    var
    i:integer;
    arr  :array[0 .. 7] of integer =(7, 6, 5, 4, 3, 2, 1, 0);
    index:array[0 .. 2] of integer =(6, 1, 7);


    begin
    writeln('Before');
    for i:=0 to 7 do write(arr[i],'  ');
    writeln;
    d_sort(index,arr);
    writeln('After');
    for i:=0 to 7 do write(arr[i],'  ');
    writeln;
    readln;
    end.

Before
7  6  5  4  3  2  1  0
After
7  0  5  4  3  2  1  6

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

Output:

[7 0 5 4 3 2 1 6]

Phix

with javascript_semantics
function disjoint_sort(sequence s, sequence idx)
    idx = unique(idx)
    integer l = length(idx)
    sequence copies = repeat(0, l)
    for i=1 to l do
        copies[i] = s[idx[i]]
    end for
    copies = sort(copies)
    for i=1 to l do
        s[idx[i]] = copies[i]
    end for
    return s
end function
 
?disjoint_sort({7,6,5,4,3,2,1,0},{7,2,8})

Output:

{7,0,5,4,3,2,1,6}

Shorter Alternative Version

with javascript_semantics
function disjoint_sort(sequence s, idx)
    idx = unique(idx)
    return reinstate(s,idx,sort(extract(s,idx)))
end function
 
?disjoint_sort({7,6,5,4,3,2,1,0},{7,2,8})

Output:

same output.

PicoLisp

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

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

Output:

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

Prolog

Using only predicates marked as "builtin"

% ===
% Problem description
% ===
% http://rosettacode.org/wiki/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, while 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].
%
% In case of one-based indexing, rather than the zero-based indexing above,
% you would use the indices {7, 2, 8} instead.
%
% 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. 


% ===
% Notes
% ===
% For predicate descriptions, see https://www.swi-prolog.org/pldoc/man?section=preddesc
%
% Solution using only predicates marked "builtin".
%
% - sort/2 is a built-in predicate. When called as sort(A,B) then
%          it sorts A to B according to the "standard order of terms",
%          (for integers, this means ascending order). It does remove
%          duplicates.
% - msort/2 is the same as sort/2 but does not remove duplicates.
%
% Everything is a list as there is no "set" datatype in Prolog.


% ===
% Main predicate (the one that would be exported from a Module)
% sort_disjoint_sublist(+Values,+Indexes,?ValuesSorted)
% ===
 
sort_disjoint_sublist(Values,Indexes,ValuesSorted) :-
   sort(Indexes,IndexesSorted),
   insert_fresh_vars(0,IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened),
   msort(ValsToSort,ValsSorted),  % this is the "sorting of values"
   % The next two lines could be left out with suitable naming, 
   % but they make explicit what happens:
   FreshVars = ValsSorted,         % fresh variables are unified with sorted variables
   ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output 

% ===
% Helper predicate (would not be exported from a Module)
% ===
 
% insert_fresh_vars(+CurIdx,+[I|Is],+[V|Vs],-FreshVars,-ValsToSort,-ValsFreshy)
%
%   CurIdx:     Monotonically increasing index into the list of values by 
%               which we iterate.
%   [I|Is]:     Sorted list of indexes of interest. The smallest (leftmost)
%               element is removed on every "index hit", leaving eventually
%               an empty list, which gives us the base case.
%   [V|Vs]:     The list of values of interest with the leftmost element the
%               element with index CurIdx, all elements with lower index
%               having been discarded. Leftmost element is popped off on
%               each call.
%   FreshVars:  Constructed as output. If there was an "index hit", the
%               fresh variable pushed on FreshVars is also pushed on Vars.
%   ValsToSort: Constructed as output. If there was an "index hit", the
%               leftmost value from [V|Vs] is pushed on.
%   ValsFreshy: Constructed as output. If there was an "index hit", a fresh
%               variable is pushed on. If there was no "index hit", the actual
%               value from [V|Vs] is pushed on instead.  

insert_fresh_vars(CurIdx,[I|Is],[V|Vs],FreshVars,ValsToSort,[V|ValsFreshy]) :-
   CurIdx<I, % no index hit, CurIdx is still too small, iterate over value
   !,
   succ(CurIdx,NextIdx),
   insert_fresh_vars(NextIdx,[I|Is],Vs,FreshVars,ValsToSort,ValsFreshy).
 
insert_fresh_vars(CurIdx,[I|Is],[V|Vs],[Fresh|FreshVars],[V|ValsToSort],[Fresh|ValsFreshy]) :-
   CurIdx=I, % index hit, replace value by fresh variable
   !,
   succ(CurIdx,NextIdx),
   insert_fresh_vars(NextIdx,Is,Vs,FreshVars,ValsToSort,ValsFreshy).
 
insert_fresh_vars(_,[],V,[],[],V).

Alternatively, using predicates from `library(list)`

Using append/3 from SWi-Prolog's library(list)

% ===
% Main predicate
% ===

sort_disjoint_sublist(Values,Indexes,ValuesSorted) :-
   sort(Indexes,IndexesSorted),
   insert_fresh_vars_by_splintering(IndexesSorted,Values,FreshVars,ValsToSort,ValuesFreshened),
   msort(ValsToSort,ValsSorted),  % this is the "sorting of values"
   % The next two lines could be left out with suitable naming, 
   % but they make explicit what happens:
   FreshVars = ValsSorted,         % fresh variables are unified with sorted variables
   ValuesSorted = ValuesFreshened. % ValuesFreshend is automatically the sought output 

% ===
% Helpers
% ===

insert_fresh_vars_by_splintering([I|Is],Values,[Fresh|FreshVars],[ValAtI|ValsToSort],ValsFreshyFinal) :-
   splinter(Values,I,ValAtI,ValsFront,ValsBack),         % splinter  Values  --> ValsFront + ValAtI + ValsBack
   append([ValsFront,[Fresh],ValsBack],ValsFreshyNext),  % recompose ValsFront + Fresh + ValsBack --> ValuesFreshyNext
   insert_fresh_vars_by_splintering(Is,ValsFreshyNext,FreshVars,ValsToSort,ValsFreshyFinal).

insert_fresh_vars_by_splintering([],V,[],[],V).

% "splinter" a list into a frontlist, the element at position N and a backlist
 
splinter(List, N, Elem, Front, Back) :-
    length(Front, N),
    append(Front, [Elem|Back], List).

Unit Tests

Test code using the Unit Testing framework of SWI Prolog.

% We use the "R" intermediate var to decouple processing by the predicate 
% from subsequent checking against expected result.
 
:- begin_tests(sort_disjoint_sublist).

test(rosetta)  :- sort_disjoint_sublist([7,6,5,4,3,2,1,0],[6,1,7],R), R = [7,0,5,4,3,2,1,6].
test(another1) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[3,4,5,6,7],R), R = [4,2,1,0,0,4,5,5].
test(another2) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,1,2,3,4],R), R = [1,2,4,4,5,5,0,0].
test(another3) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[0,2,4,6],R), R = [0,2,1,4,4,5,5,0].
test(another4) :- sort_disjoint_sublist([4,2,1,4,5,5,0,0],[1,3,5,7],R), R = [4,0,1,2,5,4,0,5].
test(edge1)    :- sort_disjoint_sublist([],[],R), R = [].
test(edge2)    :- sort_disjoint_sublist([3,2,1],[],R), R = [3,2,1].
test(edge3)    :- sort_disjoint_sublist([3,2,1],[0],R), R = [3,2,1].
test(edge4)    :- sort_disjoint_sublist([3,2,1],[1],R), R = [3,2,1].
test(edge5)    :- sort_disjoint_sublist([3,2,1],[2],R), R = [3,2,1].
test(x1)       :- sort_disjoint_sublist([3,2,1],[0,1,2],R), R = [1,2,3].
test(x2)       :- sort_disjoint_sublist([1,2,3],[0,1,2],R), R = [1,2,3].
test(dups1)    :- sort_disjoint_sublist([3,2,1],[1,1,1],R), R = [3,2,1].
test(dups2)    :- sort_disjoint_sublist([3,2,1],[2,1,2],R), R = [3,1,2].
test(fail1,[fail]) :- sort_disjoint_sublist([1,2],[0,1,2],_).
test(fail2,[fail]) :- sort_disjoint_sublist([],[0,1],_).
 
:- end_tests(sort_disjoint_sublist).
 
% ---
% Run unit tests.
% ---
 
rt :- run_tests(sort_disjoint_sublist).

PowerShell

Works with: PowerShell version 4.0

function sublistsort($values, $indices) {
   $indices = $indices | sort 
   $sub, $i = ($values[$indices] | sort), 0
   $indices | foreach { $values[$_] = $sub[$i++] }
   $values
}
$values = 7, 6, 5, 4, 3, 2, 1, 0
$indices = 6, 1, 7
"$(sublistsort $values $indices)"

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.

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

	
>>>

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

'''Disjoint sublist sorting'''


# --------------------- DISJOINT SORT ----------------------

# disjointSort :: [Int] -> [Int] -> [Int]
def disjointSort(ixs):
    '''A copy of the list xs, in which the disjoint sublist
       of items at zero-based indexes ixs is sorted in a
       default numeric or lexical order.'''
    def go(xs):
        ks = sorted(ixs)
        dct = dict(zip(ks, sorted(xs[k] for k in ks)))
        return [
            dct[i] if i in dct else x 
            for i, x in enumerate(xs)
        ]
    return go


# -------------------------- TEST --------------------------
# main :: IO ()
def main():
    '''Disjoint sublist at three indices.'''
    print(
        tabulated(
            'Disjoint sublist at indices [6, 1, 7] sorted:\n'
        )
        (str)(str)(
            disjointSort([6, 1, 7])
        )([
            [7, 6, 5, 4, 3, 2, 1, 0],
            ['h', 'g', 'f', 'e', 'd', 'c', 'b', 'a']
        ])
    )


# ------------------------ DISPLAY -------------------------

# tabulated :: String -> (a -> String) ->
#                        (b -> String) ->
#                        (a -> b) -> [a] -> String
def tabulated(s):
    '''Heading -> x display function -> fx display function ->
                f -> value list -> tabular string.'''
    def go(xShow, fxShow, f, xs):
        w = max(map(compose(len)(xShow), xs))
        return s + '\n' + '\n'.join(
            xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs
        )
    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
        xShow, fxShow, f, xs
    )

# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
    '''Function composition.'''
    return lambda f: lambda x: g(f(x))


if __name__ == '__main__':
    main()

Output:

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

Quackery

  [ sort tuck [] unrot 
    witheach
      [ dip dup peek 
        rot join swap ]
    swap sort
    dip swap witheach
      [ over i^ peek 
        dip rot poke
        swap ] 
    drop ]              is sortdisjointsublist ( [ [ --> [ )

  ' [ 7 6 5 4 3 2 1 0 ] ' [ 6 1 7 ] sortdisjointsublist echo

Output:

[ 7 0 5 4 3 2 1 6 ]

R

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

 values=c(7,6,5,4,3,2,1,0)
 indices=c(7,2,8)
 values[sort(indices)]=sort(values[indices])
 print(values)

Output:

 7 0 5 4 3 2 1 6

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)

Raku

(formerly Perl 6)

Works with: Rakudo version 2020.08.1

Inline

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

my @values  = 7, 6, 5, 4, 3, 2, 1, 0;
my @indices = 6, 1, 7;

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

say @values;

Output:

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

Iterative

sub disjointSort( @values, @indices --> 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 ) ;
say @sortedValues ;

Output:

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

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.

The REXX language normally uses a one-based index.

/*REXX program uses a   disjointed sublist   to  sort  a  random list  of values.       */
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.*/
if idx=''  then idx= 7 2 8                       /* "      "         "   "   "     "    */
say '  list of indices:'  idx;   say             /*    [↑]  is for one─based lists.     */
say '    unsorted list:'  old                    /*display the  old  list of numbers.   */
say '      sorted list:'  disjoint_sort(old,idx) /*sort 1st list using 2nd list indices.*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
disjoint_sort: procedure;    parse arg x,ix;   y=;    z=;    p= 0
               ix= sortL(ix)                           /*ensure the index list is sorted*/
                    do i=1  for  words(ix)             /*extract indexed values from  X.*/
                    z= z   word(x, word(ix, i) )       /*pick the correct value from  X.*/
                    end   /*j*/
               z= sortL(z)                             /*sort extracted (indexed) values*/
                    do m=1  for words(x)               /*re─build (re-populate)  X list.*/
                    if wordpos(m, ix)==0  then y=y  word(x,m)    /*is the same  or  new?*/
                                          else do;  p= p + 1;        y= y word(z, p)
                                               end
                    end   /*m*/
               return strip(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortL: procedure; parse arg L;    n= words(L);       do j=1  for n;        @.j= word(L,j)
                                                     end   /*j*/
         do k=1  for n-1                               /*sort a list using a slow method*/
           do m=k+1  to n;   if @.m<@.k  then parse value   @.k  @.m    with  @.m  @.k
           end   /*m*/
         end     /*k*/                                 /* [↑]  use  PARSE  for swapping.*/
       $= @.1;               do j=2  to n;   $= $ @.j
                             end   /*j*/
       return $

output when using the default inputs:

  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

Ring

aList = [7, 6, 5, 4, 3, 2, 1, 0]
indList = [7, 2, 8]
bList = []
for n = 1 to len(indList)
    add(bList,[indList[n],aList[indList[n]]])
next
bList1 = sort(bList,1)
bList2 = sort(bList,2)
for n = 1 to len(bList)
    aList[bList1[n][1]] = bList2[n][2]
next
showarray(aList)

func showarray vect
     svect = ""
     for n in vect
         svect += " " + n + ","
     next
     ? "[" + left(svect, len(svect) - 1) + "]"

Output:

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

RPL

≪ SORT → set
  ≪ { } 1 set SIZE FOR j
        OVER set j GET GET + NEXT
     SORT SWAP
     1 set SIZE FOR j
        set j GET 3 PICK j GET PUT NEXT
     SWAP DROP
≫ ≫ 'SUBSORT' STO

HP-28 models shall use their homemade version of the SORT instruction, or use the one defined in Sorting algorithms/Bubble sort

{ 7 6 5 4 3 2 1 0 } { 6 1 7 } SUBSORT

Output:

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

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)

Output:

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

Rust

use std::collections::BTreeSet;

fn disjoint_sort(array: &mut [impl Ord], indices: &[usize]) {
    let mut sorted = indices.to_owned();
    sorted.sort_unstable_by_key(|k| &array[*k]);
    indices
        .iter()
        .zip(sorted.iter())
        .map(|(&a, &b)| if a > b { (b, a) } else { (a, b) })
        .collect::<BTreeSet<_>>()
        .iter()
        .for_each(|(a, b)| array.swap(*a, *b))
}

fn main() {
    let mut array = [7, 6, 5, 4, 3, 2, 1, 0];
    let indices = [6, 1, 7];
    disjoint_sort(&mut array, &indices);
    println!("{:?}", array);
}

Output:

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

Scala

Library: Scala

import scala.compat.Platform

object SortedDisjointSubList extends App {
  val (list, subListIndex) = (List(7, 6, 5, 4, 3, 2, 1, 0), List(6, 1, 7))

  def sortSubList[T: Ordering](indexList: List[Int], list: List[T]) = {
    val subListIndex = indexList.sorted
    val sortedSubListMap = subListIndex.zip(subListIndex.map(list(_)).sorted).toMap

    list.zipWithIndex.map { case (value, index) =>
      if (sortedSubListMap.isDefinedAt(index)) sortedSubListMap(index) else value
    }
  }

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

Scheme

Works with: Gauche Scheme

(use gauche.sequence)
(define num-list '(7 6 5 4 3 2 1 0))
(define indices '(6 1 7))
(define table 
  (alist->hash-table
    (map cons
      (sort indices)
      (sort indices < (lambda (x) (~ num-list x))))))

(map last
  (sort
    (map-with-index
      (lambda (i x) (list (hash-table-get table i i) x))
      num-list)
    <
    car))

Output:

(7 0 5 4 3 2 1 6)

Sidef

func disjointSort(values, indices) {
    values[indices.sort] = [values[indices]].sort...
}

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

disjointSort(values, indices);
say values;

Output:

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

Standard ML

Works with: SML/NJ

Translation of: Go

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

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

Swift

Translation of: Go

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

struct DisjointSublistView<T> : MutableCollectionType {
  let array : UnsafeMutablePointer<T>
  let indexes : [Int]
  
  subscript (position: Int) -> T {
    get {
      return array[indexes[position]]
    }
    set {
      array[indexes[position]] = newValue
    }
  }
  var startIndex : Int { return 0 }
  var endIndex : Int { return indexes.count }
  func generate() -> IndexingGenerator<DisjointSublistView<T>> { return IndexingGenerator(self) }
}

func sortDisjointSublist<T : Comparable>(inout array: [T], indexes: [Int]) {
  var d = DisjointSublistView(array: &array, indexes: sorted(indexes))
  sort(&d)
}

var a = [7, 6, 5, 4, 3, 2, 1, 0]
let ind = [6, 1, 7]
sortDisjointSublist(&a, ind)
println(a)

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.

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
}

Demonstration:

set values {7 6 5 4 3 2 1 0}
set indices {6 1 7}
puts \[[join [disjointSort $values $indices] ", "]\]

Output:

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

TUSCRIPT

TUSCRIPT indexing is one based

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

Output:

7'0'5'4'3'2'1'6

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

Output:

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

Wren

Library: Wren-sort

import "./sort" for Sort

// sorts values in place, leaves indices unsorted
var sortDisjoint = Fn.new { |values, indices|
    var sublist = []
    for (ix in indices) sublist.add(values[ix])
    Sort.quick(sublist)
    var i = 0
    var indices2 = Sort.merge(indices)
    for (ix in indices2) {
        values[ix] = sublist[i]
        i = i + 1
    }
}

var values  = [7, 6, 5, 4, 3, 2, 1, 0]
var indices = [6, 1, 7]
System.print("Initial: %(values)")
sortDisjoint.call(values, indices)
System.print("Sorted : %(values)")

Output:

Initial: [7, 6, 5, 4, 3, 2, 1, 0]
Sorted : [7, 0, 5, 4, 3, 2, 1, 6]

XPL0

include xpllib;         \for Sort routine
int  Values, Indices, J, I, T;
[Values:= [7, 6, 5, 4, 3, 2, 1, 0];
Indices:= [6, 1, 7];
Sort(Indices, 3);
for J:= 3-1 downto 0 do \bubble sort values at Indices
    for I:= 0 to J-1 do
        if Values(Indices(I)) > Values(Indices(I+1)) then
            [T:= Values(Indices(I));
            Values(Indices(I)):= Values(Indices(I+1));
            Values(Indices(I+1)):= T;
            ];
for I:= 0 to 8-1 do
        [IntOut(0, Values(I));  ChOut(0, ^ )];
]

Output:

7 0 5 4 3 2 1 6

zkl

values :=T(7, 6, 5, 4, 3, 2, 1, 0);
indices:=T(6, 1, 7);

indices.apply(values.get).sort() // a.get(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

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

values :=L(7, 6, 5, 4, 3, 2, 1, 0);

indices.apply(values.get).sort() // a.get(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

Output:

L(7,0,5,4,3,2,1,6)

Latest revision as of 10:54, 8 February 2024

Functional

Idiomatic, vanilla

Lower Level version

Simple Alternative Version

Icon and Unicon

ES5

Iterative

Functional

ES6

Another way

Mathematica/Wolfram Language

With arrays:

With lists:

Shorter Alternative Version

Using only predicates marked as "builtin"

Alternatively, using predicates from library(list)

Unit Tests

Inline

Iterative

Alternatively, using predicates from `library(list)`