Selection Sort in Python

Introduction

Selection sort in Python is basically an algorithm that sorts out the data in an array in ascending order by finding the minimum element. It does not acquire any extra space and two sub-arrays are maintained in an array for a selection sort in Python without using the function.

Overview

Python is a computer programming language used for building web-based applications. In 1991, Guido Van Rossum created it.

Similar to the sorting function in Microsoft Excel, an algorithm called selection sort is used in Python for arranging and sorting out arrays. Two different sub-arrays are maintained for sorting out the elements in an array. The time complexity of the selection sort is about O(N2).

In every iteration, the minimum element from the unsorted array is taken and swapped into the sorted array.

Working of Selection Sort

Let us look at the following example to understand the selection sort algorithm better:

Example: Array arr[]= {65, 36, 12, 15, 9}

First Pass

For the first element, wherein 65 is presently stored, after traversing the whole unsorted array, it is found that the minimum element in the block is 9.

Thus replacing 65 with 9. After the first iteration, the number 9, which was the last number in the unsorted array, now, tends to be in the first position.

65 36 12 15 9

Swapping Elements

Second Pass

For the second position, after traversing the entire array, it is found that the second lowest element is 12.

The second element in the unsorted array is 36 which is now replaced or swapped by the number 12.

9 36 12 15 65

Third Pass

Similarly, for the third position, after traversing the entire array, it is found that the third lowest element is 15.

The third lowest element 15 is placed after the number 12 in the sorted array.

9 12 36 15 65

Swapping Elements

Fourth Pass

After traversing the array, the fourth-lowest element was found to be 36 and it was placed in the fourth block.

9 12 15 36 65

Last Pass

The number 65, which is the largest number in the array, is automatically sorted.

Finally, you get the sorted array.

Let’s see the implementation of the code

// Function for Selection sort
void selectionSort(int arr[], int n)
{
          int i, j, min_idx;

          // One by one move boundary of
          // unsorted subarray
          for (i = 0; i < n - 1; i ) {

                    // Find the minimum element in
                    // unsorted array
                    min_idx = i;
                    for (j = i 1; j < n; j ) {
                              if (arr[j] < arr[min_idx])
                                        min_idx = j;
                    }

                    // Swap the found minimum element
                    // with the first element
                    if (min_idx != i)
                              swap(arr[min_idx], arr[i]);
          }
}

// Function to print an array
void printArray(int arr[], int size)
{
          int i;
          for (i = 0; i < size; i ) {
                    cout << arr[i] << " ";
                    cout << endl;
          }
}

// Driver program
int main()
{
          int arr[] = {65, 36, 12, 15, 9}
          int n = sizeof(arr) / sizeof(arr[0]);

          // Function Call
          selectionSort(arr, n);
          cout << "Sorted array: \n";
          printArray(arr, n);
          return 0;
}

The code Output:

9,12,15,36,65

Selection Sort Algorithm

Array = [6,7,3,8]
# loop to Traverse through all the elements in the given array
for i in range(len(Array)):
    # setting min_indx equal to the first unsorted element
    min_indx = i
    # Loop to iterate over un-sorted sub-array
    for j in range(i 1, len(Array)):
    #Finding the minimum element in the unsorted sub-array
        if Array[min_indx] > Array[j]:
            min_indx = j
    # swapping the minimum element with the element at min_index to place it at its correct position    
    Array[i], Array[min_indx] = Array[min_indx], Array[i]
# Printing the modified array after the selection sort algorithm is applied


print(Array)

The Code Output:

3,6,7,8

Below is an example of the insertion function in Python.

def insertionSort(arr):
          n = len(arr) # Get the length of the array
          
          if n <= 1:
                    return # If the array has 0 or 1 element, it is already sorted, so return

          for i in range(1, n): # Iterate over the array starting from the second element
                    key = arr[i] # Store the current element as the key to be inserted in the right position
                    j = i-1
                    while j >= 0 and key < arr[j]: # Move elements greater than key one position ahead
                              arr[j 1] = arr[j] 
                              j -= 1
                    arr[j 1] = key 

arr = [12, 10, 15, 8, 2]
insertionSort(arr)
print(arr)

The Output:

[2, 8, 10, 12, 15]

Merge sort in Python

The merge sort algorithms as the name indicates divide the input array into two. After sorting out the two halves, the merge sort merges the two into one.

Assuming that arr[l..m] and arr[m 1..r] are sorted, the merge(arr, l, m, r) key operation merges the two sorted subarrays into a single array.

Selection sort program using Python

Python uses the same selection sort algorithm to sort out the numbers in ascending order. The article below covers the Python code for the selection sort pseudocode.

Time Complexity of Selection Sort

The time complexity of the selection sort is about O(N2). It does not require any additional space for performing the selection sort function.Best case scenario - O(N2) - occurs when the array has already been sorted. The array's number of integers, n, is indicated here.The average case (O(N2)) occurs when the array's items are organized in a random manner without regard to any rules.

When the array needs to be organized in ascending order but is now in descending order, the worst scenario is O(N2).

The time complexity of the selection sort remains unchanged irrespective of the input array’s initial order. It is important to find the minimum element in the array to sort it in the ascending order and that is possible only after the entire array is traversed.

At every step, the selection sort algorithm recognizes the minimum element and places it in the right position.

The above-given table gives the breakdown of the selection sort time complexity.

The total number of comparisons in the selection sort can be calculated as the sum of (n-1) (n-2) (n-3) …… 1.

This can be attributed to n/(n-1)/2 OR n^2

Thus, the time complexity comes to O(n^2).

One can also analyze the time complexity by looking at the number of loops – that is two nested loops in the selection sort.

This in turn comes to n^2.

Python Program for Selection Sort

The given Python code below provides the selection sort algorithm. The time complexity of the selection sort is about O(n^2).

The entire array is traversed before sorting the array in the ascending order. In every iteration, the minimum element is identified and placed in the correct space. This happens continuously unless the complete array is sorted out in the required ascending manner.

Python Program for Selection Sort:

def selectionSort(array, size):
          
          for ind in range(size):
                    min_index = ind

                    for j in range(ind 1, size):
                              # select the minimum element in every iteration
                              if array[j] < array[min_index]:
                                        min_index = j
                    # swapping the elements to sort the array
                    (array[ind], array[min_index]) = (array[min_index], array[ind])

arr = [2, 45, 0, 15, -14, 99, 55, 64, 747]
size = len(arr)
selectionSort(arr, size)
print('The array after sorting in Ascending Order by selection sort is:')
print(arr)

The Output:

[-14, 0, 2, 15, 45, 55, 64, 99, 747]

Conclusion

The array's elements are sorted using selection sort in ascending order. It is a wonderful method to utilize because it takes up less extra space. It is advantageous to employ because it has an O(n) time complexity.

FAQs

1. What is Python?

Web-based apps can be created using the computer language Python. It is a robust and user-friendly language that Guido Van Rossum developed and produced; it is also one of the languages of choice for developers and programmers all over the world.

2. What is a selection sort in Python?

Selection sort is an algorithm in Python that is used to sort elements in the array as per the given specifications such as in ascending order.

3. What is an array in Python?

An array is a collection of data stored in contiguous memory locations.

4. Is Python good for beginners?

Yes, Python has been developed with simple codes and syntax. It’s an easy language and programming makes it quite useful for beginners.

5. What is the time complexity of selection sort in Python?

The time complexity of the selection sort in data structure is about O(N2).

6. What is an insertion sort in Python?

Insertion sort in Python is to sort an array. It compares the element besides the key element and then shifts its place to the correct location.

7. What is the difference between insertion sort and selection sort?

The main difference between insertion sort and selection sort is how they sort out the elements in an array. Insertion sorts compares and shifts places of the elements, whereas, selection sort divides the array into two parts – sorted and unsorted. It swaps the elements from unsorted elements to sorted ones.

8. Does upGrad provide courses on Python?

Yes, Python offers courses on Python which covers everything – from basic coding to complex programming on Python.

Take our Free Quiz on Python

Answer quick questions and assess your Python knowledge

Start Quiz