Get the indices of an array after sorting

Question

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 code-golf, fewest bytes wins!

-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. — Cody Gray, Jul 30, 2017 at 11:44
Well, I get why he accepted an answer within 24 hours, it's impossible to beat. — Adalynn, Jul 30, 2017 at 14:28
@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. — Dada, Jul 30, 2017 at 16:07
Using a 1 character builtin is hardly practice. Easy doesn't necessarily mean solvable using only builtins. — JAD, Jul 31, 2017 at 7:36
The best solution in such cases is to forget about te accept feature, which isn't really relevant anyway here. — Mr. Xcoder, Jul 31, 2017 at 9:01

Pavel · Accepted Answer · 2017-07-30 22:42:22Z

11

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.

edited Jul 30, 2017 at 22:42

Pavel

9,2411 gold badge48 silver badges94 bronze badges

answered Jul 30, 2017 at 7:45

James Heslip

1594 bronze badges

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

Add a comment |

Dennis · Accepted Answer · 2017-07-30 04:57:37Z

10

Jelly, 1 byte

Ụ

Try it online!

answered Jul 30, 2017 at 4:57

Dennis

208k41 gold badges363 silver badges816 bronze badges

\$\begingroup\$ Heh that was too obvious... \$\endgroup\$
– Erik the Outgolfer
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

Add a comment |

ბიმო · Accepted Answer · 2017-07-30 15:36:54Z

10

Haskell, 43 42 bytes

1-indexed:

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

Try it online!

-1 byte thanks to @ØrjanJohansen!

edited Jul 30, 2017 at 15:36

answered Jul 30, 2017 at 4:58

ბიმო

16.6k2 gold badges39 silver badges102 bronze badges

2

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

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-07-30 19:48:56Z

9

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!

edited Jul 30, 2017 at 19:48

answered Jul 30, 2017 at 5:21

Mr. Xcoder

42.1k9 gold badges77 silver badges214 bronze badges

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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

9

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jul 30, 2017 at 15:31

Endenite

4,04110 silver badges28 bronze badges

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

Add a comment |

Erik the Outgolfer · Accepted Answer · 2017-07-30 09:05:33Z

7

Python 2, 48 bytes

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

Try it online!

answered Jul 30, 2017 at 9:05

Erik the Outgolfer

40.3k5 gold badges39 silver badges120 bronze badges

\$\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\$
– Erik the Outgolfer
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\$
– Erik the Outgolfer
Jul 30, 2017 at 9:17

| Show 1 more comment

Brad Gilbert b2gills · Accepted Answer · 2017-07-30 14:07:15Z

5

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

edited Jul 30, 2017 at 14:07

answered Jul 30, 2017 at 13:42

Brad Gilbert b2gills

13.1k1 gold badge17 silver badges33 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

Bash + coreutils, 20

nl|sort -nk2|cut -f1

Try it online.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jul 31, 2017 at 0:51

Digital Trauma

70.9k9 gold badges107 silver badges256 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

djhurio · Accepted Answer · 2017-07-31 07:42:40Z

4

R, 5 bytes

There is a builtin function for this.

order

edited Jul 31, 2017 at 7:42

answered Jul 30, 2017 at 8:28

djhurio

1,1535 silver badges13 bronze badges

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

Add a comment |

G B · Accepted Answer · 2017-07-31 08:21:48Z

4

Ruby, 40 bytes

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

Try it online!

answered Jul 31, 2017 at 8:21

G B

19.7k1 gold badge19 silver badges50 bronze badges

Add a comment |

Sanchises · Accepted Answer · 2017-07-30 08:51:01Z

3

MATL, 2 bytes

&S

Try it online!

Input and output are implicit.

edited Jul 30, 2017 at 8:51

answered Jul 30, 2017 at 8:43

Sanchises

9,3661 gold badge34 silver badges61 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

J, 2 bytes

/:

Try it online!

Zero-based indexing.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jul 30, 2017 at 15:47

Tikkanz

2011 silver badge3 bronze badges

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

Add a comment |

Sanchises · Accepted Answer · 2017-08-05 21:32:35Z

3

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.

edited Aug 5, 2017 at 21:32

answered Jul 30, 2017 at 14:16

Sanchises

9,3661 gold badge34 silver badges61 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jul 30, 2017 at 14:27

Adalynn

6,0621 gold badge15 silver badges36 bronze badges

Add a comment |

Jakob · Accepted Answer · 2017-09-03 01:14:19Z

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

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). — Nevay, Aug 16, 2017 at 18:23

Renzo · Accepted Answer · 2017-07-30 08:12:06Z

2

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!

answered Jul 30, 2017 at 8:12

Renzo

2,52811 silver badges22 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2017-07-30 13:22:19Z

2

Clojure, 39 bytes

#(map key(sort-by val(zipmap(range)%)))

answered Jul 30, 2017 at 13:22

NikoNyrh

2,6118 silver badges8 bronze badges

\$\begingroup\$ Translated to Perl 6 {map *.key,(sort *.value,(0..* Z=> @_))} \$\endgroup\$
– Brad Gilbert b2gills
Jul 30, 2017 at 13:51

Add a comment |

Erik the Outgolfer · Accepted Answer · 2017-07-30 13:28:03Z

2

CJam, 12 bytes

{ee{1=}$0f=}

Try it online!

answered Jul 30, 2017 at 13:28

Erik the Outgolfer

40.3k5 gold badges39 silver badges120 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2017-07-30 15:07:30Z

2

MATLAB / Octave, 29 bytes

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

Try it online!

edited Jul 30, 2017 at 15:07

answered Jul 30, 2017 at 12:35

Luis Mendo

102k9 gold badges128 silver badges362 bronze badges

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

Add a comment |

Arnauld · Accepted Answer · 2017-07-30 15:29:21Z

2

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

answered Jul 30, 2017 at 15:29

Arnauld

180k17 gold badges167 silver badges609 bronze badges

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

Add a comment |

Sherlock9 · Accepted Answer · 2017-07-31 08:39:07Z

2

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!

answered Jul 31, 2017 at 8:39

Sherlock9

12.1k1 gold badge27 silver badges68 bronze badges

Add a comment |

ბიმო · Accepted Answer · 2017-08-01 13:41:33Z

2

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]

edited Aug 1, 2017 at 13:41

answered Aug 1, 2017 at 5:11

ბიმო

16.6k2 gold badges39 silver badges102 bronze badges

Add a comment |

Xanderhall · Accepted Answer · 2017-08-21 17:28:34Z

2

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.

answered Aug 21, 2017 at 17:28

Xanderhall

1,2866 silver badges14 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 5, 2018 at 19:46

12Me21

6,5611 gold badge20 silver badges40 bronze badges

Add a comment |

Luis Mendo · Accepted Answer · 2018-11-06 11:25:48Z

2

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!

edited Nov 6, 2018 at 11:25

answered Jul 30, 2017 at 16:43

Luis Mendo

102k9 gold badges128 silver badges362 bronze badges

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

Add a comment |

Erik the Outgolfer · Accepted Answer · 2017-07-30 13:30:43Z

1

05AB1E, 4 bytes

ā<Σè

Try it online!

answered Jul 30, 2017 at 13:30

Erik the Outgolfer

40.3k5 gold badges39 silver badges120 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2017-08-01 03:11:28Z

1

Pari/GP, 16 bytes

a->vecsort(a,,1)

Try it online!

answered Aug 1, 2017 at 3:11

alephalpha

40.5k7 gold badges52 silver badges151 bronze badges

Add a comment |

WebSmithery · Accepted Answer · 2017-08-06 14:09:22Z

1

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.

answered Aug 6, 2017 at 14:09

WebSmithery

2211 silver badge3 bronze badges

1

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

Add a comment |

sergiol · Accepted Answer · 2017-08-16 17:36:52Z

1

Tcl, 21 bytes

(0-indexed)

puts [lsort -indi $L]

Try it online!

answered Aug 16, 2017 at 17:36

sergiol

3,3781 gold badge13 silver badges31 bronze badges

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

Add a comment |

Get the indices of an array after sorting

35 Answers 35

Dyalog APL, 1 byte

Example

Jelly, 1 byte

Haskell, 43 42 bytes

Python 2, 56 bytes

Javascript (ES6), 39 bytes

Python 2, 48 bytes

Perl 6, 27 21 bytes

Expanded:

Bash + coreutils, 20

Swift 4, 82 bytes

Explanation

R, 5 bytes

Ruby, 40 bytes

MATL, 2 bytes

J, 2 bytes

Octave, 17 bytes

MY, 3 bytes

How?

Java 8, 128 + 19 = 147 bytes

Ungolfed lambda

Notes

Acknowledgments

Common Lisp, 82 bytes

Clojure, 39 bytes

CJam, 12 bytes

MATLAB / Octave, 29 bytes

JavaScript (ES6), 69 bytes

Test cases

Python 3, 52 bytes

Husk, 10 7 bytes

Ungolfed/Explained

Java (OpenJDK 8), 72 bytes

SmileBASIC, 67 bytes

Python 3 with Numpy, 38 26 bytes

05AB1E, 4 bytes

Pari/GP, 16 bytes

PHP, 54 bytes

Tcl, 21 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

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