Python Program for Selection Sort

What is selection sort ?

Selection sorting is based on the idea of finding the minimum element or maximum element in an unsorted list of elements and then putting each elements in correct position in order to get sorted list of elements.

In the i'th pass, we select the record with lowest key among array[i],..., array[n] and we swap it with array[i]. As a result after i passes, the lowest records will occupy array[1],..., array[i] in sorted order.

Selection Sorting Steps

Selection Sorting Time complexity

Selection sorting time complexity is O(N^2). here N is the number of elements in the list, (N−1)(N−1) + (N−2)(N−2) + ... + 1 = (N(N−1))/2 comparisons.

Selection Sort Python Program

#!/usr/bin/python                                                               
                                                                                
def swap(list_vals, min_val_index, i):                                          
    temp = list_vals[min_val_index];                                            
    list_vals[min_val_index] = list_vals[i];                                    
    list_vals[i] = temp;                                                        
                                                                                
def selection_sort(list_vals):                                                  
    num_of_elements = len(list_vals);                                           
                                                                                
    #  reduces the each inner iteration loop size by one.                       
    for i in range(0, num_of_elements-1):                                       
        # position of minimum element in the list                               
        # Assuming first element to be the minimum                              
        min_val_index = i;                                                      
        # finds minimum value position in the list of elements.                 
        for j in range(i+1, num_of_elements):                                   
            if (list_vals[j] < list_vals[min_val_index]):                       
                min_val_index = j;                                              
                                                                                
        swap(list_vals, min_val_index, i);                                      
                                                                                
    return list_vals;                                                           
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorted list elements: %s" % str(selection_sort(list_vals)));  

$ python selection_sort.py
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]

Selection Sort Python Program using maximum element

#!/usr/bin/python                                                               
                                                                                
def swap(list_vals, max_val_index, i):                                          
    temp = list_vals[max_val_index];                                            
    list_vals[max_val_index] = list_vals[i];                                    
    list_vals[i] = temp;                                                        
                                                                                
def selection_sort(list_vals):                                                  
    num_of_elements = len(list_vals);                                           
                                                                                
    #  reduces the each inner iteration loop size by one.                       
    for i in range(0, num_of_elements-1):                                       
        # position of maximum element in the list                               
        # Assuming first element to be the maximum                              
        max_val_index = i;                                                      
        # finds maximum value position in the list of elements.                 
        for j in range(i+1, num_of_elements):                                   
            if (list_vals[j] < list_vals[max_val_index]):                       
                max_val_index = j;                                              
                                                                                
        swap(list_vals, max_val_index, i);                                      
                                                                                
    return list_vals;                                                           
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [30, 10, 20, 70, 60, 80, 50, 40];                               
    print("Collection before sorting: %s" % str(list_vals));                    
    print("Sorted list elements: %s" % str(selection_sort(list_vals)));    

$ python selection_sort.py
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorted list elements: [10, 20, 30, 40, 50, 60, 70, 80]