#=======================================================================
# Author: Isai Damier
# Title: Selection Sort
# Project: geekviewpoint
# Package: algorithm.sorting
#
# Statement:
# Given a disordered list of integers (or any other items),
# rearrange the integers in natural order.
#
# Sample Input: [18,5,3,1,19,6,0,7,4,2,5]
# Sample Output: [0,1,2,3,4,5,5,6,7,18,19]
#
# Time Complexity of Solution:
# Best O(n^2); Average O(n^2); Worst O(n^2).
#
# Approach:
# Selection sort is a step up from insertion sort from a memory
# viewpoint. It only swaps elements that need to be swapped. In terms
# of time complexity, however, insertion sort is better.
#=======================================================================
def selectionsort( aList ):
for i in range( len( aList ) ):
least = i
for k in range( i + 1 , len( aList ) ):
if aList[k] < aList[least]:
least = k
swap( aList, least, i )
def swap( A, x, y ):
tmp = A[x]
A[x] = A[y]
A[y] = tmp
import unittest
from algorithms import sorting
class Test( unittest.TestCase ):
def testSelectionsort( self ):
A = [18, 5, 100, 3, 1, 19, 6, 0, 7, 4, 2]
sorting.selectionsort( A )
for i in range( 1, len( A ) ):
if A[i - 1] > A[i]:
self.fail( "selectionsort method fails." )