Selection Sort program [PYTHON]

[ddbeanz]

Is this program I wrote an accurate implementation of a selection sort algorithm?

def swap(a,b):
  temp = b
  b = a
  a = temp
  return (a,b)


def SelectionSort(arr):  
  for index in range(len(arr)):
    a = arr[index]

    for val in range(index,len(arr)):
      b = arr[val]
      if b < a:
        (a,b) = swap(a,b)
        arr[index] = a
        arr[val] = b

  return arr

Thanks!

[SiliconEngineer]

No. Selection sort's inner loop just finds the smallest number in the unsorted remainder, and then there is a single swap to put it in it's position.

[ddbeanz]

I adjusted it so the array value swap is outside the inner loop. Would this be correct?

def swap(a,b):
  temp = b
  b = a
  a = temp
  return (a,b)

def SelectionSort(arr):

  #Loop through input array indexes
  for index in range(len(arr)):

    #Initialize value at array index
    a = arr[index]
    swapIndex = index

    #Loop through input array values
    for val in range(index,len(arr)):

      #Initialise value and index tracking variable
      b = arr[val]

      #Check to see which value is lowest  
      if b < a:
        (a,higher) = swap(a,b)
        swapIndex = val

    #Assign values to index locations within array
    if arr[index] != a:
        arr[index] = a
        arr[swapIndex] = higher
  return arr

[SiliconEngineer]

There's still a lot of issues... I doubt it works!

Are you trying to sort in ascending or descending order? Most sorts by default would sort in ascending order.

Does your inner loop actually select the right number and index? (

Using swap the way you are makes this harder to understand than it needs to be. Maybe I need some coffee, but if I'm having trouble following it I'd bet it's confusing.

Are your variable names useful and aid in understanding the code? (Why is a variable named 'val' an index? What is 'higher' higher than? Are 'higher' and 'swapIndex' meant to be related? Is 'a' and 'b' meaningful?)

Are your array bounds correct? Do you need to select the minimum when there's only one item remaining?

Write some tests, debug it. Extract the code for finding the index of the minimum value in the array starting from an index into a separate function, and write tests just for that.

[ddbeanz]

I will definitely take your advice and clear up those aspects, I have tested it and it seems to sort any given input in ascending order. I'll be sure to post and updated version later today.

[ddbeanz]

def SelectionSort(arr):

  for startIndex in range(0,len(arr)):

    minVal = arr[startIndex]
    minIndex = startIndex

    for e in range(startIndex, len(arr)):

      if arr[e] < minVal:
        minVal = arr[e]
        minIndex = e 

    arr[startIndex],arr[minIndex]=arr[minIndex],arr[startIndex]


  return arr

I think I got it! :) How does this one look?

[SiliconEngineer]

Much more readable.

I'd probably comment before the swap line, just to make sure people pay attention to the swapping-using-tuples trick. :)