Python: Selection Sort

Question

I would like to convert the following JAVA code to python (am a beginner in Python)

public void selectionSort(int[] arr) {
      int i, j, minIndex, tmp;
      int n = arr.length;
      for (i = 0; i < n - 1; i++) {
            minIndex = i;
            for (j = i + 1; j < n; j++)
                  if (arr[j] < arr[minIndex])
                        minIndex = j;
            if (minIndex != i) {
                  tmp = arr[i];
                  arr[i] = arr[minIndex];
                  arr[minIndex] = tmp;
            }
      }
}

This is what I wrote but it doesn't work and I cannot figure out what am I doing wrongly

A = [86, 2,4 ,5, 6122, 87]

def selectionSort(a):
    n = len(a)
    print ("n = ", n)
    for i in range (0, n-1):
        minIndex = i
        j = i+1
        for j in range (0, n):
            if(a[j] < a[minIndex]):
                minIndex = j
        if minIndex != i:
            tmp = a[i]
            a[i] = a[minIndex]
            a[minIndex] = tmp



selectionSort(A)
print(A)

Please help me understand why

What is `j = i + 1` supposed to be for? Immediately after you assign it, you rewrite it with 0. — Wooble, Mar 01 '13 at 17:58
@Fredrik If the OP is learning to program and learning python it may be a good exercise. — Bakuriu, Mar 01 '13 at 18:00
@Bakuriu - I'm just saying that learning python in a pythonic way is superior to learning python by mimicking java... — Fredrik Pihl, Mar 01 '13 at 18:08

Abhijit · Answer 1 · 2013-05-28T07:09:04.343

Change the two lines

j = i+1
for j in range (0, n):

to

for j in range (i+1, n):

to match

for (j = i + 1; j < n; j++)

other nitpicks

swapping in python is elegantly done as

a[i], a[minIndex] = a[minIndex], a[i]

and the entire block

    minIndex = i
    for j in range (i+1, n):
        if(a[j] < a[minIndex]):
            minIndex = j
    if minIndex != i:
        a[i], a[minIndex] = a[minIndex], a[i]

can be refactored as

    minIndex = min(range(i,n), key = partial(getitem, a))
    a[i], a[minIndex] = a[minIndex], a[i]

provided you import partial from functools and getitem from operator

from functools import partial
from operator import getitem

So your final version would look something like

from functools import partial
from operator import getitem
def selectionSort(a):
    n = len(a)
    for i in range (n-1):
        minIndex = min(range(i,n), key = partial(getitem, a))
        a[i], a[minIndex] = a[minIndex], a[i]

seeing which at the end would make you wonder if converting Java Code to Python as an exercise was indeed a good way to learn Python

Your final version is incorrect, since you swap unconditionally. I get `[2, 4, 5, 87, 86, 6122]` with your code — mensi, Mar 01 '13 at 18:32
@mensi: On the contrary, the swap may be unconditional but the problem was with the index to the range, it should had been `i` instead of `i+1` — Abhijit, Mar 01 '13 at 18:35

mensi · Accepted Answer · 2013-03-01T18:25:56.887

0

for j in range (0, n)

is not the same as in Java, where you use i+1 to start.

A more pythonic way to implement selection sort could look like this:

A = [86, 2,4 ,5, 6122, 87]
def selectionSort(a):
    # Go through all positions except the last one 
    # (that one will automatically be correct)
    for index in range(len(a)-1):
        value = a[index]
        # enumerate all (index, value) pairs from the rest of the list 
        # and take the pair with the smallest value
        min_subindex, min_value = min(enumerate(a[index+1:]), key=lambda x: x[1])
        if min_value < value:
            a[index] = min_value
            a[min_subindex + index + 1] = value

selectionSort(A)
print(A) # [2, 4, 5, 86, 87, 6122]

edited Mar 01 '13 at 18:25

answered Mar 01 '13 at 17:58

mensi

9,580
2
34
43

enumerate forms a list of tuples but why does it take a[index+1]: as an argument ? – Haya Raed Mar 02 '13 at 00:26
`some_list[x:y:z]` is list slicing, explained in [this StackOverflow Question](http://stackoverflow.com/questions/509211/the-python-slice-notation). The idea is to only enumerate the rest of the list. – mensi Mar 02 '13 at 10:04
min_subindex will have the same value as min_value ? – Haya Raed Mar 02 '13 at 11:15
I ran the code and I knew that min_subindex will give the index of the min_value .. so basically min_subindex is the first value of the tuple – Haya Raed Mar 02 '13 at 14:15
@HayaRaed yes, `a, b = some_tuple` will put `some_tuple[0]` into `a` and `some_tuple[1]` into b. It also works for more than just two values. – mensi Mar 02 '13 at 14:42

score 0 · Answer 3 · answered Mar 01 '13 at 17:59

Issues:

When you do j in range(0, n-1) it will start the loop at 0 instead of i+1.

Use

for j in range(i+1, n-1)

Working code:

A = [86, 2,4 ,5, 6122, 87]

def selectionSort(a):
    n = len(a)
    print ("n = ", n)
    for i in range (0, n-1):
        minIndex = i
        for j in range (i+1, n):
            if(a[j] < a[minIndex]):
                minIndex = j

        if minIndex != i:
            a[i], a[minIndex] = a[minIndex], a[i]

selectionSort(A)
print(A)

Thank You SO MUCHHH!!!! you were right , it started looping at 0 and everything got messed up — Haya Raed, Mar 01 '13 at 18:12

Python: Selection Sort

3 Answers3