17
\$\begingroup\$

Your challenge today is to write a program or function which takes a list l and gives the positions in l at which each successive element of l sorted appears.

In other words, output the index of the smallest value, followed by the index of the second smallest value, etc.

You can assume that the input array will contain only positive integers, and will contain at least one element.

Test cases:

Input                  | Output (1-indexed)
[7, 4, 5]              | [2, 3, 1]
[1, 2, 3]              | [1, 2, 3]
[2, 6, 1, 9, 1, 2, 3]  | [3, 5, 1, 6, 7, 2, 4]
[4]                    | [1]

When two or more elements with the same value appear, their indices should appear next to each other from smallest to largest.

This is , fewest bytes wins!

\$\endgroup\$
8
  • 16
    \$\begingroup\$ -1 for a trivial challenge that can be solved with built-ins in common golfing languages, and for accepting an answer in less than 24 hours. This was neither a fair challenge, nor an interesting one. \$\endgroup\$
    – Cody Gray
    Jul 30, 2017 at 11:44
  • 3
    \$\begingroup\$ Well, I get why he accepted an answer within 24 hours, it's impossible to beat. \$\endgroup\$
    – Adalynn
    Jul 30, 2017 at 14:28
  • 3
    \$\begingroup\$ @CodyGray I thought downvoting when I saw the 1-2 bytes answer, but actually, I don't think it's a bad challenge for more standard programming languages. Of course, it's not a hard challenge, but still, there is definitely some golfing possibilities. Of course, it's unpleasant to see 1-byte built-ins, but I don't think that it's fair to blame the challenge for that. \$\endgroup\$
    – Dada
    Jul 30, 2017 at 16:07
  • 1
    \$\begingroup\$ Using a 1 character builtin is hardly practice. Easy doesn't necessarily mean solvable using only builtins. \$\endgroup\$
    – JAD
    Jul 31, 2017 at 7:36
  • 2
    \$\begingroup\$ The best solution in such cases is to forget about te accept feature, which isn't really relevant anyway here. \$\endgroup\$
    – Mr. Xcoder
    Jul 31, 2017 at 9:01

35 Answers 35

11
\$\begingroup\$

Dyalog APL, 1 byte

Dyalog APL has a built in operator function (thank you Zacharý for clearing this up) to do this.

Example

⍋11 2 4 15
    2 3 1 4  
{⍵[⍋⍵]}11 4 2 15
    2 4 11 15

Here I'm indexing into the list by the sorted indices to return the list in ascending order.

\$\endgroup\$
2
  • \$\begingroup\$ Oh, just to alert you to some confusing terminology, in APL, builtins like are considered functions, while things like ¨⍨⍣.∘/\⌿⍀⌸⍤ are operators. \$\endgroup\$
    – Adalynn
    Jul 30, 2017 at 15:45
  • \$\begingroup\$ polyglot with BQN. \$\endgroup\$
    – Razetime
    Dec 31, 2021 at 7:39
10
\$\begingroup\$

Jelly, 1 byte

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Heh that was too obvious... \$\endgroup\$ Jul 30, 2017 at 8:25
  • 2
    \$\begingroup\$ APL deserved this one, +1 though for your speed. \$\endgroup\$
    – Adalynn
    Jul 30, 2017 at 14:25
  • \$\begingroup\$ @Zacharý I'm sure Jelly picked this one up from J, which in turn inherited it from APL. \$\endgroup\$
    – Adám
    Aug 17, 2017 at 12:51
10
\$\begingroup\$

Haskell, 43 42 bytes

1-indexed:

import Data.List
map snd.sort.(`zip`[1..])

Try it online!

-1 byte thanks to @ØrjanJohansen!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Pointfree version saves one byte: map snd.sort.(`zip`[1..]). \$\endgroup\$ Jul 30, 2017 at 5:56
9
\$\begingroup\$

Python 2, 56 bytes

This solution is 0-indexed. This abuses the fact that sorted() creates a copy of the original list.

l=input()
for k in sorted(l):a=l.index(k);print a;l[a]=0

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Why did you ungolf this? \$\endgroup\$ Jul 30, 2017 at 9:11
  • \$\begingroup\$ @EriktheOutgolfer Fixed, Rollback. \$\endgroup\$
    – Mr. Xcoder
    Jul 30, 2017 at 9:13
9
\$\begingroup\$

Javascript (ES6), 39 bytes

-2 bytes thanks to @powelles

This only works in browsers where Array.prototype.sort is stable.

a=>[...a.keys()].sort((b,c)=>a[b]-a[c])

1-indexed version (47 bytes):

a=>a.map((_,i)=>i+1).sort((b,c)=>a[b-1]-a[c-1])

Example code snippet:

f=
a=>[...a.keys()].sort((b,c)=>a[b]-a[c])
console.log("7,4,5 => "+f([7,4,5]))
console.log("1,2,3 => "+f([1,2,3]))
console.log("2,6,1,9,1,2,3 => "+f([2,6,1,9,1,2,3]))
console.log("4 -> "+f([4]))

\$\endgroup\$
1
  • \$\begingroup\$ [...a.keys()] instead of a.map((_,i)=>i) will save you a couple of bytes. \$\endgroup\$
    – powelles
    Jul 30, 2017 at 18:32
7
\$\begingroup\$

Python 2, 48 bytes

lambda x:sorted(range(len(x)),key=x.__getitem__)

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Nice, I got outgolfed >_<. I switched my answer to Python 3 such that I don't feel that bad \$\endgroup\$
    – Mr. Xcoder
    Jul 30, 2017 at 9:06
  • 4
    \$\begingroup\$ @Mr.Xcoder Well, that's his job... \$\endgroup\$
    – Neil
    Jul 30, 2017 at 9:14
  • \$\begingroup\$ @Mr.Xcoder Come on, you shouldn't feel bad for that! You made a full program, I made a function, and my approach is a bit different. \$\endgroup\$ Jul 30, 2017 at 9:14
  • \$\begingroup\$ I don't feel bad, I knew this will appear (I personally hate the __<blahblah>__ syntax). I will do some Jelly, I don't want to lose my training :) \$\endgroup\$
    – Mr. Xcoder
    Jul 30, 2017 at 9:16
  • 1
    \$\begingroup\$ @Mr.Xcoder Codegolf doesn't mean pretty syntax and formatting. ;) \$\endgroup\$ Jul 30, 2017 at 9:17
5
\$\begingroup\$

Perl 6,  27  21 bytes

*.pairs.sort(*.value)».key

Test it

->\x{sort {x[$_]},^x}

Test it

Inspired by a Python answer

Expanded:

->    # pointy block lambda
  \x  # declare sigilless parameter
{
  sort
    { x[$_] },  # sort by the value in 「x」 at the given position
    ^x          # Range up-to the number of elements in 「x」
}
\$\endgroup\$
5
\$\begingroup\$

Bash + coreutils, 20

nl|sort -nk2|cut -f1

Try it online.

\$\endgroup\$
4
\$\begingroup\$

Swift 4, 82 bytes

func f(l:[Int]){var l=l;for k in l.sorted(){let a=l.index(of:k)!;print(a);l[a]=0}}

Test Suite.

Explanation

In Swift, l.sorted() creates a sorted copy of the original Array. We loop through the sorted elements in the list and after printing each item's index in the original Array with let a=l.index(of:k)!;print(a), and then, in order to keep the correct indexes in the Array, we assign l[a] to 0, because it does not affect our normal output.


Take note that this is 0-indexed, since it is a port of my Python solution. If you want it to be 1-indexed, replace print(a) with print(a+1) or Try it online!.

\$\endgroup\$
4
\$\begingroup\$

R, 5 bytes

There is a builtin function for this.

order
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Standard rules is to provide a program of function. order is already a function, so you don't have to handle input using scan(). This would be 5 bytes. \$\endgroup\$
    – JAD
    Jul 31, 2017 at 7:34
  • \$\begingroup\$ rank() would save a byte \$\endgroup\$
    – gstats
    Aug 1, 2017 at 15:10
  • 1
    \$\begingroup\$ I am sure there was a rank answer by @JarkoDubbeldam, but I do not see it anymore. \$\endgroup\$
    – djhurio
    Aug 1, 2017 at 16:58
  • 1
    \$\begingroup\$ Correct, it does not follow the spec so I deleted it. \$\endgroup\$
    – JAD
    Aug 1, 2017 at 17:02
4
\$\begingroup\$

Ruby, 40 bytes

->a{a.zip([*1..a.size]).sort.map &:last}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

MATL, 2 bytes

&S

Try it online!

Input and output are implicit.

\$\endgroup\$
3
\$\begingroup\$

J, 2 bytes

/:

Try it online!

Zero-based indexing.

\$\endgroup\$
1
  • \$\begingroup\$ Was going to post this... \$\endgroup\$
    – Cyoce
    Aug 1, 2017 at 4:19
3
\$\begingroup\$

Python 3, 52 bytes

0-indexed. Based on Bruce Forte's Haskell answer here and G B's Ruby answer here.

lambda l:list(zip(*sorted(zip(l,range(len(l))))))[1]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Octave, 17 bytes

@(i)[~,y]=sort(i)

Try it online!

Octave is like MATLAB but with inline assignment, making things possible that gives the folks at Mathworks HQ headaches. It doesn't matter what you call y, but you can't do without that dummy variable, as far as I know.

\$\endgroup\$
3
\$\begingroup\$

MY, 3 bytes

MY also has a builtin for this!

⎕⍋↵

Try it online!

How?

Evaluated input, grade up, then output with a newline.

Indexed however you set the index, with /0x48. (Can even be some weird integer like -1 or 2, the default is 1).

\$\endgroup\$
3
\$\begingroup\$

Java 8, 128 + 19 = 147 bytes

Based on Mr. Xcoder's solution. 0-based. Lambda takes input as an Integer[] and returns Integer[]. Byte count includes lambda expression and required import.

import java.util.*;

l->{Integer o[]=l.clone(),s[]=l.clone(),i=0;for(Arrays.sort(s);i<l.length;)l[o[i]=Arrays.asList(l).indexOf(s[i++])]=0;return o;}

Try It Online

Ungolfed lambda

l -> {
    Integer
        o[] = l.clone(),
        s[] = l.clone(),
        i = 0
    ;
    for (Arrays.sort(s); i < l.length; )
        l[o[i] = Arrays.asList(l).indexOf(s[i++])] = 0;
    return o;
}

Notes

I use Integer[] instead of int[] to allow use of Arrays.asList, which has no primitive versions. Integer is preferred to Long because values are used as array indices and would require casting.

This ended up being shorter than my best procedural-style List solution because of the cost of class and method names.

This also beat a solution I tried that streamed the inputs, mapped to (value, index) pairs, sorted on values, and mapped to indices, mostly because of the baggage needed to collect the stream.

Acknowledgments

  • -5 bytes thanks to Nevay
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You don't need j: l->{Integer o[]=l.clone(),s[]=l.clone(),i=0;for(Arrays.sort(s);i<l.length;l[o[i]=Arrays.asList(l).indexOf(s[i++])]=0);return o;} (19+128 bytes). \$\endgroup\$
    – Nevay
    Aug 16, 2017 at 18:23
2
\$\begingroup\$

Common Lisp, 82 bytes

(lambda(l)(loop as i in(sort(copy-seq l)'<)do(setf(elt l(print(position i l)))0)))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Clojure, 39 bytes

#(map key(sort-by val(zipmap(range)%)))
\$\endgroup\$
1
  • \$\begingroup\$ Translated to Perl 6 {map *.key,(sort *.value,(0..* Z=> @_))} \$\endgroup\$ Jul 30, 2017 at 13:51
2
\$\begingroup\$

CJam, 12 bytes

{ee{1=}$0f=}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

MATLAB / Octave, 29 bytes

[~,y]=sort(input(''));disp(y)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ While your answer is perfect MATLAB, you can actually do inline assignment in anonymous functions in Octave. \$\endgroup\$
    – Sanchises
    Jul 30, 2017 at 14:18
  • \$\begingroup\$ Good one! I knew about in-line assignment, but I didn't know you could output directly like that \$\endgroup\$
    – Luis Mendo
    Jul 30, 2017 at 15:06
  • 1
    \$\begingroup\$ To be honest, me neither. I started with something like @(X)([~,y]=sort(X)), and while I was looking of a way to get y from this, I realized y was actually the return value from the assignment, and closer inspection revealed that brackets weren't even needed. MATLAB likes everything explicit; Octave is happy when it's unambiguous. \$\endgroup\$
    – Sanchises
    Jul 30, 2017 at 15:40
2
\$\begingroup\$

JavaScript (ES6), 69 bytes

0-indexed. Works for lists containing up to 65,536 elements.

a=>[...a=a.map((n,i)=>n<<16|i)].sort((a,b)=>a-b).map(n=>a.indexOf(n))

Test cases

let f =

a=>[...a=a.map((n,i)=>n<<16|i)].sort((a,b)=>a-b).map(n=>a.indexOf(n))

console.log(JSON.stringify(f([7, 4, 5])))
console.log(JSON.stringify(f([1, 2, 3])))
console.log(JSON.stringify(f([2, 6, 1, 9, 1, 2, 3])))
console.log(JSON.stringify(f([4])))

\$\endgroup\$
3
  • \$\begingroup\$ Can you change n=>a.indexOf(n) to just a.indexOf? \$\endgroup\$
    – Adalynn
    Jul 30, 2017 at 15:33
  • \$\begingroup\$ @Zacharý Unfortunately not. A method of an instanced object cannot be used as a callback. \$\endgroup\$
    – Arnauld
    Jul 30, 2017 at 15:36
  • \$\begingroup\$ @Zacharý Even worse is that Array#map passes 3 arguments to the callback function, and Array#indexOf expects 2, so it will give undesirable results. \$\endgroup\$
    – kamoroso94
    Jul 31, 2017 at 4:56
2
\$\begingroup\$

Husk, 10 7 bytes

This is a direct port of my Haskell answer, also 1-indexed:

m→O`z,N

Try it online!

Ungolfed/Explained

Code        Description               Example
         -- implicit input            [2,6,1]
      N  -- natural numbers           [1,2,3,..]
   `z,   -- zip, but keep input left  [(2,1),(6,2),(1,3)]
  O      -- sort                      [(1,3),(2,1),(6,2)]
m→       -- keep only indices         [3,1,2]
\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 72 bytes

l->l.stream().sorted().map(i->{int j=l.indexOf(i);l.set(j,0);return j;})

Try it online!

Takes a List<Integer>, returns a Stream<Integer> containing the results.

We get a Stream based off the initial list, sort it, then map each number to it's index in the list. In order to accommodate duplicate elements, we set the original element in the list to 0.

\$\endgroup\$
2
\$\begingroup\$

SmileBASIC, 67 bytes

DEF I(A)DIM B[0]FOR I=1TO LEN(A)PUSH B,I
NEXT
SORT A,B
RETURN B
END

Very simple, all it does is generate a list of numbers from 1 to (length of array) and sort this by the same order as the input.

\$\endgroup\$
2
\$\begingroup\$

Python 3 with Numpy, 38 26 bytes

12 bytes saved thanks to Jo King (no need to give the function a name)

import numpy
numpy.argsort

Output is 0-based.

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ The function could just be numpy.argsort without the lambda part \$\endgroup\$
    – Jo King
    Nov 6, 2018 at 5:21
  • \$\begingroup\$ @JoKing Thanks for the suggestion. I wrote it that way because with just numpy.argsort;import numpy I get an error (numpy has not been imported yet), and with import numpy;numpy.argsort I need to move f= to the code part. Do you know that the standard procedure is in these cases? Move the f= and not count it? \$\endgroup\$
    – Luis Mendo
    Nov 6, 2018 at 10:36
  • \$\begingroup\$ Yeah, I guess. Maybe just redefine f=numpy.argsort in the footer \$\endgroup\$
    – Jo King
    Nov 6, 2018 at 10:42
  • \$\begingroup\$ @JoKing Good idea. Done. Thanks! \$\endgroup\$
    – Luis Mendo
    Nov 6, 2018 at 11:26
1
\$\begingroup\$

05AB1E, 4 bytes

ā<Σè

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 16 bytes

a->vecsort(a,,1)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

PHP, 54 bytes

<?php function i($a){asort($a);return array_keys($a);}

Try it online!

This is zero-indexed. Simply sorts the array and returns the keys.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The <?php tag is unnecessary for a function. 48 bytes. \$\endgroup\$
    – Titus
    Aug 21, 2017 at 17:33
1
\$\begingroup\$

Tcl, 21 bytes

(0-indexed)

puts [lsort -indi $L]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ The test cases only have 1 digit numbers; my solution only works well on 1 digit numbers. \$\endgroup\$
    – sergiol
    Oct 21, 2017 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.