Selection Sort Algorithm In Data Structures and Algorithms using Python

Selection Sort Algorithm In Data Structures and Algorithms using Python

Selection Sort Algorithm is one of the easiest sorting algorithms in Data Structures. It is a comparison-based sorting algorithm. It is used to arrange the elements of an array (in ascending order). In this article, we’re going to see how we can implement selection sort in data structures using the Python programming language.


For Example

INPUT Array     –  16   12   96   42   21

OUTPUT Array –  12   16   21   42   96


Table of Contents:

  1. How does the Selection sort algorithm work?
  2. Algorithm
  3. Pseudocode of selection sort
  4. Selection sort algorithm in Python
  5. Selection sort algorithm in C++
  6. Time Complexity of Selection sort
  7. Space Complexity of Selection Sort
  8. In-place behavior
  9. Is Selection sort an in-place sorting algorithm?
  10. Is the Selection sort show adaptive nature?
  11. Features

Working of Selection Sort Algorithm


In Selection Sort, the given array is divided into two parts – the sorted part and the unsorted part. The sorted part is at the left end of the array and the unsorted part is at the right end of the array respectively.

At the beginning of the algorithm, the sorted part is completely empty and the unsorted part consists of the whole array. But as algo proceeds, the elements that are being sorted becomes a part of the sorted array, and the remaining subarray comes under the unsorted part.



In this sorting algorithm, with every passing iteration, the least valued or the minimum element from the unsorted array is selected, using the linear search technique after that the selected element is swapped with the first element of that array. The new element added at the beginning becomes a part of the sorted array.


Let us understand this with an example.

Consider the given array of elements  –  12     45     67     2      3







Algorithm


Selection_Sort ( array a, length n)

Step 1: Start loop from i = 0 to n-2

Step 2: Select smallest element among a[i] , … a[n-1]

Step 3: Swap element with a[i]


Pseudocode


function selection sort
A[]    : array of elements
n       : number of elements of an array

for i=1 to n-1
/* fix first element of the array as minimum */
min=i

/*check for the smallest element by comparing
with all the other elements */

for j=i+1 to n
if A[j] < A[min] then
min=j
end if
end for

/* swap the minimum element with the first element
of the array */
if index_min!=i then
swap A[min] amd A[i]
end if

end for

end function

Selection sort python code


Code:


#Code by Copyassignment.com
# function
def selection_sort(A):
    for i in range(len(A)): 
    # Finding the minimum element in remaining unsorted array 
        min_idx = i 
        for j in range(i+1, len(A)): 
            if A[min_idx] > A[j]: 
                min_idx = j 
                  
        # Swapping A[i] with minimum element         
        A[i], A[min_idx] = A[min_idx], A[i] 

#Driver Code
arr = [12,45,67,2,3,9]
selection_sort(arr)   #Calling Function

print("Final array after sorting :\n")
for i in range(len(arr)):
    print(arr[i])    #Printing array after sorting

Output:

Final array after sorting :

2
3
9
12
45
67

Selection sort algorithm in C++


Code:


// Code by violet-cat-415996.hostingersite.com

#include <iostream>
using namespace std;

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void Selection_Sort(int arr[], int n)
{
    int min_idx;

    // moving boundary of unsorted sub array 
    for (int i = 0; i < n - 1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swapping A[i] element with minimum element
        swap(&arr[min_idx], &arr[i]);
    }
}

// Driver program to test above functions
int main()
{
    int n;
    cout << "Enter the size of array : " << endl; //Taking size of array
    cin >> n;
    int arr[n];

    cout << "Enter " << n << " elements:\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i]; //Taking elements of array

    Selection_Sort(arr, n); //Calling Function

    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " "; //Printing sorted array
    return 0;
}

Output:

Enter the size of array : 
4
Enter 4 elements:
32 54 76 87
Sorted array: 
32 54 76 87 


Time complexity of selection sort


Time Complexity – In an algorithm, the time complexity is defined as the amount of time taken by the algorithm to completely run and execute all its operations is known as the time complexity of an algorithm.

Selection Sort Algorithm has a time complexity of O(n2) for all the three cases as explained below.

  1. Best-Case Complexity – Best case is when all the elements of the original array are already sorted. But, even in this case, the algorithm will perform all the comparison operations for each and every element of the array. Thus, its time complexity will remain the same i.e., O(n2).
  2. Average-Case Complexity – This is the generalized amount of time taken by the algorithm for all the possible averaged inputs. Here, again some of the swapping operations and all the comparison operations will be performed for the elements of the array. As a result, the time complexity will remain the same i.e., O(n2).
  3. Worst-Case Complexity – Worst case is considered when the given array is reversely sorted i.e., all the elements in descending order. This is the case where all the sorting operations and all the comparison operations will be performed for all the elements of the array. Thus, time complexity, in this case, will be again O(n2).

Space complexity


Space Complexity – For an algorithm, space complexity is defined as the memory space occupied by it to run and execute all its operations.

In this algorithm, all the elements are swapped within the space of a single array, given initially and does not require any extra memory space or array or any other data structure for its execution except one variable temp, which is used to store the element being swapped at a temporary location. Thus, it has a space complexity of O(1).


In-place sorting algorithm?


Yes, Selection sort is an in-place sorting algorithm because it does not require any other array or data structure to perform its operations. All the swapping operations are done within a single array.

Stable sorting algorithm?


No, Selection Sort is an unstable sorting algorithm because it works on the principle of initially finding the minimum element from the list and then putting it at its correct position by swapping it with the element which is present at the beginning of the unsorted array. Due to this swapping, the element present in the later part of the array will come at the beginning even if they have the same value.


Let us understand this with an example –

Input    – 4A   5   3   2   4B   1

Output – 1   2   3   4B   4A   5

If it would have been a stable sorting algorithm then the output would be   1   2   3   4A   4B   5

Note: Subscripts are added only for the purpose of understanding.


Adaptive sorting algorithm?


No, it is a non-adaptive sorting algorithm because even if some of the elements of the array are sorted itself, the Selection Sort Algorithm will not take into account the ‘already sorted’ elements and it will reorder them as all the comparisons would be made to confirm their sortedness.


Features of selection sort


  • It is the second slowest sorting algorithm after bubble sort because it occupies memory space for a longer time. Therefore, it is not suitable for large data sets.
  • Selection Sort Algorithm can be applied on linked list data structure as well.
  • It is preferably used when the cost of performing writing operations to memory is taken into consideration like in the case of flash memory.

Thanks for reading!

If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends and enemies!

Happy Coding!


Introduction to Searching Algorithms: Linear Search Algorithm

Bubble Sort Algorithm In Data Structures & Algorithms using Python

Merge Sort Algorithm in Python

Binary Search in python

Sorting Algorithms and Searching Algorithms in Python

Shutdown Computer with Voice in Python

Tic Tac Toe Python

Guess the Number Python


Share:

Author: Ayush Purawr