19

Suppose I have a list [2, 4, 1, 3, 5].

I want to sort the list just from index 1 to the end, which gives me [2, 1, 3, 4, 5]

How can I do it in Python?

(No extra spaces would be appreciated)

7
  • 1
    I'm curious: Why do you want this? Jan 20, 2020 at 5:52
  • I'm trying to make a next_permutation() in python
    – nwice13
    Jan 20, 2020 at 6:01
  • Do you really need to sort for that, though? Not just reverse? Jan 20, 2020 at 6:04
  • Yup, reverse is ok, but I just curious to ask about sorting this way.
    – nwice13
    Jan 20, 2020 at 6:07
  • Also see stackoverflow.com/q/2272819/12671057 Jan 20, 2020 at 6:15

5 Answers 5

18

TL;DR:

Use sorted with a slicing assignment to keep the original list object without creating a new one:

l = [2, 4, 1, 3, 5]
l[1:] = sorted(l[1:])
print(l)

Output:

[2, 1, 3, 4, 5]

Longer Answer:

After the list is created, we will make a slicing assignment:

l[1:] = 

Now you might be wondering what does [1:], it is slicing the list and starts from the second index, so the first index will be dropped. Python's indexing starts from zero, : means get everything after the index before, but if it was [1:3] it will only get values that are in between the indexes 1 and 3, let's say your list is:

l = [1, 2, 3, 4, 5]

If you use:

print(l[1:])

It will result in:

[2, 3, 4, 5]

And if you use:

print(l[1:3])

It will result in:

[2, 3]

About slicing, read more here if you want to.

And after slicing we have an equal sign =, that just simply changes what's before the = sign to what's after the = sign, so in this case, we use l[1:], and that gives [2, 3, 4, 5], it will change that to whatever is after the = sign.

If you use:

l[1:] = [100, 200, 300, 400]
print(l)

It will result in:

[1, 100, 200, 300, 400]

To learn more about it check out this.

After that, we got sorted, which is default builtin function, it simple sorts the list from small to big, let's say we have the below list:

l = [3, 2, 1, 4]

If you use:

print(sorted(l))

It will result in:

[1, 2, 3, 4]

To learn more about it check this.

After that we come back to our first topic about slicing, with l[1:], but from here you know that it isn't only used for assignments, you can apply functions to it and deal with it, like here we use sorted.

6
  • 1
    That's good, also similar to another answer below, but also require some extra memory
    – nwice13
    Jan 20, 2020 at 5:45
  • @nwice13 It is sorting in place, that's what you want, i think this is your best bet Jan 20, 2020 at 5:46
  • @U10-Forward-ReinstateMonica seconded. For the inplace operation, this is the answer.
    – Chris
    Jan 20, 2020 at 5:47
  • @nwice13 You are confusing two things, slicing and slice-based assignment. The expression x[:] creates a slice, implicitly calling x.__getitem__, whereas the statement x[:] = b is slice assignment, which calls x.__setitem__
    – Ch3steR
    Jan 20, 2020 at 5:50
  • If I didn't get wrong, the expression x[:] would just create a slice object but not the entire new list?
    – nwice13
    Jan 20, 2020 at 5:59
12

Maybe temporarily put something there that's smaller than the rest? Should be faster than the other solutions. And gets as close to your "No extra spaces" wish as you can get when using sort or sorted.

>>> tmp = l[0]
>>> l[0] = float('-inf')
>>> l.sort()
>>> l[0] = tmp
>>> l
[2, 1, 3, 4, 5]


Benchmarks

For the example list, 1,000,000 iterations (and mine of course preparing that special value only once):

  sort_u10 0.8149 seconds
sort_chris 0.8569 seconds
 sort_heap 0.7550 seconds
sort_heap2 0.5982 seconds   # using -1 instead of -inf

For 50,000 lists like [int(x) for x in os.urandom(100)]:

  sort_u10 0.4778 seconds
sort_chris 0.4786 seconds
 sort_heap 0.8106 seconds
sort_heap2 0.4437 seconds   # using -1 instead of -inf

Benchmark code:

import timeit, os

def sort_u10(l):
    l[1:] = sorted(l[1:])

def sort_chris(l):
    l = l[:1] + sorted(l[1:])

def sort_heap(l, smallest=float('-inf')):
    tmp = l[0]
    l[0] = smallest
    l.sort()
    l[0] = tmp

def sort_heap2(l):
    tmp = l[0]
    l[0] = -1
    l.sort()
    l[0] = tmp

for _ in range(3):
    for sort in sort_u10, sort_chris, sort_heap, sort_heap2, sort_rev:
        number, repeat = 1_000_000, 5
        data = iter([[2, 4, 1, 3, 5] for _ in range(number * repeat)])
        # number, repeat = 50_000, 5
        # data = iter([[int(x) for x in os.urandom(100)] for _ in range(number * repeat)])
        t = timeit.repeat(lambda: sort(next(data)), number=number, repeat=repeat)
        print('%10s %.4f seconds' % (sort.__name__, min(t)))
    print()
5
  • A bit cheating, but very good thought!
    – nwice13
    Jan 20, 2020 at 6:08
  • Whenever you see "Should be faster" but no benchmarks... I'd expect it to be slightly (probably non-detecably) slower, as it requires an extra iteration to sort the extra value, compared to the slicing method.
    – Baldrickk
    Jan 20, 2020 at 14:01
  • @Baldrickk but you don't have the extra list creation / memory usage. I would also expect this solution to be faster. It at least beats the other solution when it comes to space complexity.
    – Glenn D.J.
    Jan 20, 2020 at 14:03
  • @GlennDJ Yeah, that's what I thought as well. Added benchmarks now. Jan 20, 2020 at 15:27
  • Nice benchmarks, thanks.
    – Baldrickk
    Jan 21, 2020 at 13:14
9

Use sorted with slicing:

l[:1] + sorted(l[1:])

Output:

[2, 1, 3, 4, 5]
3
  • That is good. However, as far as I know, sorted and slicing would give me a completely new list. What I really want is sorting in place
    – nwice13
    Jan 20, 2020 at 5:38
  • Something that is similar to C++ STL: sort(a[i].begin() + 1, a.end())
    – nwice13
    Jan 20, 2020 at 5:40
  • If you need to sort with O(1) auxiliary space, you are going to have to implement a sorting algorithm yourself (or use one from a third-party library). Even the "in-place" list.sort method uses O(n) auxiliary space; see stackoverflow.com/questions/48759175/…
    – kaya3
    Jan 20, 2020 at 18:56
3

For the special case that you actually have, according to our comments:

Q: I'm curious: Why do you want this? – Heap Overflow
A: I'm trying to make a next_permutation() in python – nwice13
Q: Do you really need to sort for that, though? Not just reverse? – Heap Overflow
A: Yup, reverse is ok, but I just curious to ask about sorting this way. – nwice13

I'd do that like this:

l[1:] = l[:0:-1]
2

You can define your own function in python using slicing and sorted and this function (your custom function) should take start and end index of the list.

Since list is mutable in python, I have written the function in such a way it doesn't modify the list passed. Feel free to modify the function. You can modify the list passed to this function to save memory if required.

def sortedList(li, start=0, end=None):
        if end is None:
                end = len(li)
        fi = []
        fi[:start] = li[:start]
        fi[start:end] = sorted(li[start:end])
        return fi


li = [2, 1, 4, 3, 0]
print(li)
print(sortedList(li, 1))

Output:

[2, 1, 4, 3, 0]
[2, 0, 1, 3, 4]
0

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