Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

selection
sort
python

How to implement selection sort in Python

Educative Answers Team

Selection Sort algorithm is an in-place comparison-based algorithm. The algorithm divides the array into two segments:

  • The sorted part at the left end.
  • The remaining unsorted part at the right end.

The algorithm involves finding the minimum or maximum element in the unsorted portion of the array and then placing it in the correct position of the array.

How does a selection sort work?

Given an array, we need to sort it using Selection Sort. Hence, we must select the smallest element in the array.
1 of 7

Implementation

Now that we know how the algorithm works in theory, let’s see how to write the code to implement it.

def selectionSort(array):
  n = len(array)
  for i in range(n):
    # Initially, assume the first element of the unsorted part as the minimum.
    minimum = i

    for j in range(i+1, n):
      if (array[j] < array[minimum]):
        # Update position of minimum element if a smaller element is found.
        minimum = j

    # Swap the minimum element with the first element of the unsorted part.     
    temp = array[i]
    array[i] = array[minimum]
    array[minimum] = temp
    
  return array

# Driver code
array = [13, 4, 9, 5, 3, 16, 12]
print(selectionSort(array))

Understanding the algorithm

The code above shows how to write Selection Sort in Python. Now let’s understand it in detail.

  • The first for loop traverses the whole of the array. It initially sets the minimum to be the index of the first element in the unsorted array.

  • The inner for loop traverses the remaining portion of the array to find the position of the minimum value in this portion. Once complete, it swaps the minimum value in the unsorted portion with the first value of the unsorted portion.

  • It repeats the procedure by moving to the next value in the list and considering it to be the new minimum.


RELATED TAGS

selection
sort
python
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring