 Python Tutorial

# 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,..., 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)));
```
Output:
```\$ 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)));
```
Output:
```\$ 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]
```

Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page     ^