Understading a quicksort python implementation

Question

I found this code online.

def quick_sort(items):
""" Implementation of quick sort """
if len(items) > 1:
    pivot_index = len(items) / 2
    smaller_items = []
    larger_items = []
    for i, val in enumerate(items):
        if i != pivot_index:
            if val < items[pivot_index]:
                smaller_items.append(val)
            else:
                larger_items.append(val)

    quick_sort(smaller_items)
    quick_sort(larger_items)
    items[:] = smaller_items + [items[pivot_index]] + larger_items

The one line that gives me trouble is the last one. I believe it's basic concatenation, however, when I change "items[:]" to "items", the algorithm fails. What is special about the [:] at the end of the list?

If anyone one can help, I would really appreciate. Thank you in advance!

This is slice assignment, see e.g. http://stackoverflow.com/q/10623302/3001761 — jonrsharpe, Dec 07 '14 at 09:02

score 2 · Accepted Answer · answered Dec 07 '14 at 08:56

2

This is in-place assignment, without replacing the list object with a new object. This way, the output is placed in the original list and can be read by the caller.

answered Dec 07 '14 at 08:56

Photon

3,182
1
15
16

Oh wow, that's really cool. I really haven't seen this anywhere else before despite thinking that I know a lot of about python. Additionally, may I ask if this is application to dict and tuple? – David Tran Dec 07 '14 at 09:05
I'm not sure. Try and see. :-) – Photon Dec 07 '14 at 09:11
1

No. It's not applicable to `dict` because `dict`s don't support slice indexing, and it's not applicable to `tuple` because tuples are immutable. – PM 2Ring Dec 07 '14 at 09:25

Understading a quicksort python implementation

1 Answers1