Selection Sort Python

Question

This may seem like a simple question but when I attempted to implement selection sort in Python, I do not get a sorted list. Is there something wrong with my implementation? The subsetting may be a problem.

source = [4,2,1,10,5,3,100]
for i in range(len(source)):
  mini = min(source[i:]) #find minimum element
  min_index = source[i:].index(mini)-1 #find index of minimum element
  source[i:][min_index]= source[i:][0] #replace element at min_index with first element
  source[i:][0] = mini                  #replace first element with min element
print source

possible duplicate of [selection sort in python](http://stackoverflow.com/questions/14685915/selection-sort-in-python) — Michael Edenfield, Mar 10 '13 at 16:04

score 14 · Accepted Answer · edited Mar 05 '13 at 22:32

I think there were a couple issues.

First, when your do source[i:], I believe that returns a new array of the sub-elements requested and not part of the original array, thus if you modify it, your don't modify the original. Second, you were subtracting 1 from an index when you shouldn't.

source = [4,2,1,10,5,3,100]
for i in range(len(source)):
    mini = min(source[i:]) #find minimum element
    min_index = source[i:].index(mini) #find index of minimum element
    source[i + min_index] = source[i] #replace element at min_index with first element
    source[i] = mini                  #replace first element with min element
print source

This gives:

[1, 2, 3, 4, 5, 10, 100]

instead of finding min_index from source[1:].index try finding by source.index, this would simplify your next step of swap, just swap using source[i],source[min_index] = source[min_index], source[i]. — frp farhan, Mar 08 '18 at 12:52

steveha · Answer 2 · 2013-03-05T23:08:05.927

Here is how I would rewrite your code. Of course in Python I would just use list.sort() to sort a list, but here is a selection sort in Python.

We make a generator expression that returns tuples of (value, i) for a value and its index from the list. Then when min() evaluates to find minimum, it finds the lowest tuple value; since the value comes first in the tuple before the index, the value will be the important part, and min() will find the lowest value. (If there is a tie, min() will use the second part of the tuple, the index, as a tie-breaker. But for sort we don't care how ties are broken.)

Now, instead of searching through the sub-list to find the min value, and then searching through it again to figure out the index, we search through it once and get both min value and index.

But we don't actually care about the min value; we care about the index. So after min() is done, we just throw away the actual value but keep the index. Adjust the index to be correct in the whole list (not in the slice of the list) and then we can swap.

We use the standard Python idiom for swapping two values. Python will build a tuple object to be the intermediate, then unpack this tuple into the left-hand-side.

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    genexp = ((n, i) for i, n in enumerate(lst[i_sortpos:]))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)

EDIT: And here is a refinement of the above. A slice from a list actually allocates a new list; our code here doesn't need a new list, it just needs a convenient way to examine a sublist. The itertools module offers a function, islice(), that returns an iterator that iterates over a slice of a list. This avoids repeatedly creating and destroying lists as we examine each sublist.

I believe this is the most efficient way to do selection sort in Python. (You could get rid of the part where we bind the generator expression to the name genexp and save a few microseconds... just make the call to min() a long one-liner. But it's not really worth the loss of readability.)

import itertools as it

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    # Use it.islice() for to look at sublist.
    genexp = ((n, i) for i, n in enumerate(it.islice(lst, i_sortpos, len(lst))))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)

Is `_, i_min = min(genexp)` not wrong **?** `min(genexp)` will consider index also to compare, may should be rectified something as `min(genexp, lambda key: key[0])` ... thought I learned quite a lot from your answer. Thanks! — Grijesh Chauhan, Sep 28 '13 at 18:29
@GrijeshChauhan I discussed the issue you raised, in the second paragraph. `min()` on tuples will compare the items at index 0 in the tuple, but then use the items at index 1 in case of a tie; for sorting we don't care how the tie is resolved, so it works fine. By the way, Python provides a cool feature you can use instead of that lambda expression: `operator.itemgetter()` is a slightly faster way to get an item from a particular index. — steveha, Sep 30 '13 at 06:43

score 1 · Answer 3 · edited Nov 01 '17 at 10:30

def selectionSort(List_):
    for i in range(len(List_)):`
        #track the current smallest value
        smallIndex = i
            #loop from the current smallest value
            for j in range(i+1,len(List_))
                if List_[j] < List_[smallIndex]:
                    #if new value is less that our smallest value,change 
                    #smallest value to this
                    smallIndex = j
            if smallIndex != i:
                #swap the values
                List_[smallIndex],List_[i] = List_[i],List_[smallIndex]
    #return sorted list
    return List_

score 0 · Answer 4 · answered Oct 18 '15 at 21:05

0

def ss(l):    
    for i in range(0,len(l)):
        d=l.index(min(l[i:]))        
        c=l[i]
        l[i]=min(l[i:])
        l[d]=c
        print(l)  #it prints each step of selection sort
y=[10,9,1,5,0,6]
ss(y)

answered Oct 18 '15 at 21:05

Vibhore Gupta

1
1

[0, 9, 1, 5, 10, 6] [0, 1, 9, 5, 10, 6] [0, 1, 5, 9, 10, 6] [0, 1, 5, 6, 10, 9] [0, 1, 5, 6, 9, 10] [0, 1, 5, 6, 9, 10] #this is output – Vibhore Gupta Oct 18 '15 at 21:05
Can you explain your answer please ? – Zulu Oct 18 '15 at 23:10
what i m doing is taking min value of list and replacing it with first element and replacing the first element with min value element.So only changes occur in position of min value and first element and rest of element remains same.Now when 2nd time loop will work it will start from 2nd position of list and same thing happens till end.There for only one loop required.For graphical analysis visit the below link link: : http://www.cs.armstrong.edu/liang/animation/web/SelectionSort.html – Vibhore Gupta Oct 19 '15 at 03:57

score 0 · Answer 5 · answered Jan 03 '17 at 20:07

def selSort(L):
    """
    Find the smallest element in the list and put it (swap it) in the first location, 
    Find the second element and put it (swap it) in the second locaiton, and so on. 

    """
    for i in range(len(L) - 1):
        minIndx = i
        minVal= L[i]
        j = i + 1
        while j < len(L):
            if minVal > L[j]:
                minIndx = j
                minVal= L[j]
            j += 1
        temp = L[i]
        L[i] = L[minIndx]
        L[minIndx] = temp 
    return L

Call:

print( selSort([120,11,0,1,3,2,3,4,5,6,7,8,9,10]) )

Output

[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 120]

score 0 · Answer 6 · answered Feb 13 '17 at 10:36

0

s = [1,8,4,9,3,6,2]
for i in range(len(s)):
    maxi = max(s[0:len(s)-i])     #find max element
    tempi = s.index(maxi)         # find index of max element
    temp = s[len(s)-1-i]          #assign last element as temp
    s[len(s)-1-i] = maxi          #put max element in last position
    s[tempi] = temp               # put the element initially at last in its new 

print s

answered Feb 13 '17 at 10:36

Himanshu Soni

11
2

Two problems: 1. `max` function is better reimplemented to make `max` and `index` one operation, since the built in `max` and `index` are both O(n) operations. 2. You can use multi-value assignment instead creating an extra temp variable to swap the largest and the tail elements. – dotslashlu May 23 '18 at 07:22

score 0 · Answer 7 · 2019-09-27T06:11:06.867

Find the position(first and last), swap the elements if last is lower.

nums = [4,2,1,10,5,3,100]
def sort(nums):
     ###Find the position and now first 0th element is sorted and rest is unsorted
    #Second iteration first 2 element is sorted
    for i in range(len(nums)-1):
        miniposition = i
        for j in range(i,len(nums)):
            if nums[j] < nums[miniposition]:
                miniposition = j
        temp = nums[i]
        nums[i] = nums[miniposition]
        nums[miniposition] = temp
sort(nums)
print (nums)

First iteration(swapped 4 and 1) [1, 2, 4, 10, 5, 3, 100]

[1, 2, 4, 10, 5, 3, 100]
[1, 2, 3, 10, 5, 4, 100]
[1, 2, 3, 4, 5, 10, 100]
[1, 2, 3, 4, 5, 10, 100]
[1, 2, 3, 4, 5, 10, 100]

Other way

nums = [4,2,1,10,5,3,100]
i = 0
while i<len(nums):
    #smallest element in the sublist
    smallest = min(nums[i:])
    #index of smallest element
    index_of_smallest = nums.index(smallest)
    #swapping
    nums[i],nums[index_of_smallest] = nums[index_of_smallest],nums[i]
    i=i+1
print (nums)

score 0 · Answer 8 · answered Jul 17 '21 at 17:47

a slight variation of the solution provided

def selection_sort(l):
i = 0
while i < len(l):
    minium_value = min(l[i:]) # minium value at ith iteration
    minium_value_index = l[i:].index(minium_value) # minium value index at i th iteration

    if minium_value < l[i]: # if the current value already min, skip
        l[i + minium_value_index] = l[i] # put current value in min value's index - swap 1
        l[i] = minium_value # set current value with min value- swap 2
    i += 1

return l

score 0 · Answer 9 · edited Mar 24 '22 at 06:01

0

def selection_sort_min(): # sorting number

    for i in range(len(num)-1):
        current_min_index = i
        for j in range(i+1,len(num)):
            if  num[j] < num[current_min_index] :
                current_min_index = j
        num[i],num[current_min_index] = num [current_min_index],num[i]
    print(num)
num = [23,89,12,0,3,7,33]

selection_sort_min()

edited Mar 24 '22 at 06:01

Samsul Islam

2,581
2
17
23

answered Aug 25 '21 at 03:20

Nazmul Hassan Riaz

19
4

this is essentially a copy of @Amjad's answer. Stop necrobumping, please... – H. Doebler Aug 25 '21 at 22:37

score -1 · Answer 10 · answered Feb 19 '16 at 21:36

-1

here is what I think is a good way to sort a list of numbers and I hope it helps:

list=[5,4,3,1,6,8,10,9]
listsorted=[]
for i in range(len(list)):
    x=min(list)
    list.remove(x)
    listsorted.append(x)
print listsorted

and the result will be [1, 3, 4, 5, 6, 8, 9, 10]

answered Feb 19 '16 at 21:36

urnatatio

1

1

But the algorithm is not doing a in place sort which is the purpose of selection sort – sri85 May 10 '16 at 15:50

score -1 · Answer 11 · answered Oct 28 '17 at 17:54

I think the "accepted" answer here is unhelpful. If we look at e.g.

mini = min(source[i:]) #find minimum element
min_index = source[i:].index(mini) #find index of minimum element

not only is this inefficient in terms of creating list slices unnecessarily, but they are searched unnecessarily. It's reasonably concise but I don't think it's the best solution.

score -2 · Answer 12 · edited May 13 '15 at 06:22

-2

def Selection_Sort(Sarray):
    length = len(Sarray)
    i = 0
    j = 0
    for i in range(length):
        j = i+1
        for j in range(length):
            if Sarray[i] < Sarray[j]
                t = Sarray[i]
                Sarray[i] = Sarray[j]
                Sarray[j] = t
        j = j+1
        i = i+1

    return Sarray

edited May 13 '15 at 06:22

hamidfzm

4,595
8
48
80

answered Apr 16 '15 at 10:18

user4795998

1

Please put some description of how your answer finds the problem in the code in the question, not just an alternate implementation of the selection sort. – John Colanduoni Apr 16 '15 at 10:37

David Yachnis · Answer 13 · 2015-07-16T11:45:26.410

-2

Code of select sort from MIT online course .

def selSort(L):
    for i in range(len(L) - 1):
        minIndx = i
        minVal = L[i]
        j = i+1
        while j < len(L):
            if minVal > L[j]:
                minIndx = j
                minVal = L[j]
            j += 1
        if minIndx != i:
            temp = L[i]
            L[i] = L[minIndx]
            L[minIndx] = temp

edited Jul 16 '15 at 11:45

answered Jul 16 '15 at 08:35

David Yachnis

484
5
14

Yang Wang · Answer 14 · 2015-08-25T05:14:40.243

-2

def selectSort(L):
  for i in range(len(L)):
    print L
    minIndex = i
    minValue = L[i]
    j = i + 1
    while j < len(L):
        if minValue > L[j]:
            minIndex = j
            minValue = L[j]  
        j +=1
    temp = L[i]
    L[i] = L[minIndex]
    L[minIndex] = temp

edited Aug 25 '15 at 05:14

answered Aug 25 '15 at 05:07

Yang Wang

580
4
14

Selection Sort Python

14 Answers14

Linked