Python Tutorial
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 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.
#!/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]
#!/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]
Python Tutorial
Privacy Policy | Copyright2020 - All Rights Reserved. | Contact us
| Report website issues in Github
| Facebook page
| Google+ page