Selection Sort in Data Structures

Selection Sort in Data Structures

06 Jun 2024
Intermediate
3.14K Views
17 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms Free Course

Selection Sort in Data Structures: An Overview

Selection Sort is a simple sorting algorithm that repeatedly finds the smallest element and places it at its correct sorted position. In this DSA tutorial, we will learn its features, working, implementation, etc. To further enhance your understanding and application of selection sort, consider enrolling in the Dsa Training to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Selection Sort in Data Structures?

Selection sort is an in-place comparison sort algorithm. It divides the given list or array into two parts, sorted and unsorted. Initially, the sorted part is empty. The algorithm selects the smallest element from the unsorted list in each iteration and places it at the end of the sorted list. This process is repeated until we get a sorted list, and there are no more elements left in the unsorted sublist. After every iteration, the size of the sorted sublist increases, and that of the unsorted sublist decreases.

Selection Sort Algorithm

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort
According to the algorithm,
  1. Obtain the list or array to be sorted.
  2. Set the current index as the starting index. This represents the beginning of the unsorted portion of the list.
  3. Traverse the rest of the unsorted portion to find the smallest element.
  4. Swap the smallest element found with the element at the current index.
  5. Increment the current index by one, moving the boundary of the sorted and unsorted portions of the list.
  6. Check if the current index is less than the length of the list - 1. If it is, go back to the 3rd step. If it's not, the list is now sorted in ascending order.
  7. End the process.

Working of Selection Sort Algorithm

  1. Set the first element as minimum. 7, 20, 9, 15, 8

    Select first element as minimum

  2. Compare the minimum with the second element. If the second element is smaller than the minimum, assign the second element as minimum.
    • Compare minimum with the third element. Again, if the third element is smaller, assign minimumit to the third element otherwise do nothing. The process goes on until the last element.
    • Compare minimum with the remaining elements

  3. After each iteration, the minimum is placed in the front of the unsorted list.

  4. For each iteration, indexing starts from the first unsorted element. Steps 1 to 3 are repeated until all the elements are placed in their correct positions.

    The first iteration

    The second iteration

    The third iteration

    The fourth iteration

Read More - Data Structure Interview Questions and Answers

Implementation of Selection Sort in Different Languages in Data Structures


def selectionSort(array, size):
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
            # To sort in descending order, change > to < in this line
            # Select the minimum element in each loop
            if array[i] < array[min_idx]:
                min_idx = i

        # Put the minimum element at the correct position
        (array[step], array[min_idx]) = (array[min_idx], array[step])

def print_list(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()
    
arr = [7, -5, 20, 9, 15, 8, -9,]
size = len(arr)

# Print the original array
print('Original Array:', end=" ")
print_list(arr)

# Call the selectionSort function
selectionSort(arr, size)

# Print the sorted array in ascending order
print('Sorted Array in Ascending Order:', end=" ")
print_list(arr)
    

public class SelectionSort {

    public static void selectionSort(int[] array, int size) {
        for (int step = 0; step < size; step++) {
            int minIdx = step;

            for (int i = step + 1; i < size; i++) {
                // To sort in descending order, change > to < in this line
                // Select the minimum element in each loop
                if (array[i] < array[minIdx]) {
                    minIdx = i;
                }
            }

            // Put the minimum element at the correct position
            int temp = array[step];
            array[step] = array[minIdx];
            array[minIdx] = temp;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, -5, 20, 9, 15, 8, -9};
        int size = arr.length;

        // Print the original array
        System.out.print("Original Array: ");
        printArray(arr);

        // Call the selectionSort function
        selectionSort(arr, size);

        // Print the sorted array in ascending order
        System.out.print("Sorted Array in Ascending Order: ");
        printArray(arr);
    }
}
    


 // Selection sort in C++

 #include <iostream>
 using namespace std;
 
 // function to swap the the position of two elements
 void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
 }
 
 // function to print an array
 void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
   cout << array[i] << " ";
  }
  cout << endl;
 }
 
 void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
   int min_idx = step;
   for (int i = step + 1; i < size; i++) {
 
    // To sort in descending order, change > to < in this line.
    // Select the minimum element in each loop.
    if (array[i] < array[min_idx])
     min_idx = i;
   }
 
   // put min at the correct position
   swap(&array[min_idx], &array[step]);
  }
 }
 
 // driver code
 int main() {
  int arr[] = {7, -5, 20, 9, 15, 8, -9};
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "Original array is: ";
   printArray(arr, size);
  selectionSort(arr, size);
  cout << "Sorted array in Acsending Order:";
  printArray(arr, size);
 }
    

Output

Original array is: 7 -5 20 9 15 8 -9 
Sorted array in Acsending Order:-9 -5 7 8 9 15 20   

Complexity Analysis of Selection Sort Algorithm

  1. Time Complexity
    CaseTime Complexity
    Best

    O(n)

    Average

    O(n^2)

    Worst

    O(n^2)

  2. Space Complexity: The space complexity of the selection sort algorithm is O(1). We have used a fixed number of variables, and we do not need any extra memory space apart from the loop variables and auxiliary variables that include temp, size, and minidx.

Applications of Selection Sort Algorithm

  1. Small Data Sets: Selection sort is best suited for small data sets, where the number of elements is relatively small. For such data sets, the time complexity is not a big issue, and it can provide a simple and efficient solution.
  2. Embedded Systems: Selection sort is also used in embedded systems, where memory and processing power are limited. It is a simple algorithm that can be implemented in a small amount of code, making it a good choice for embedded systems.
  3. Testing Other Sorting Algorithms: Selection sort is often used to test other sorting algorithms. Since selection sort is one of the simplest sorting algorithms, it is easy to implement and can be used as a benchmark to compare the performance of more complex sorting algorithms.
  4. Partially Sorted Data: Selection sort performs well on partially sorted data. If a large portion of the input data is already sorted, selection sort will not perform unnecessary swaps, resulting in faster sorting times
  5. When Swapping is Costly: If the cost of swapping elements is high (for instance, when dealing with large records and small keys), selection sort can be efficient because it minimizes the number of swaps.

Advantages of Selection Sort Algorithm

  1. Simplicity:The selection sort is easy to understand and implement, making it a good choice for beginners or situations where simplicity is preferred over efficiency.
  2. Space efficiency: Selection sort requires minimal additional space beyond the input array, as it performs in-place sorting.
  3. Performance on small datasets: Selection sort has a relatively low overhead compared to more advanced sorting algorithms, making it suitable for small datasets with a few hundred or thousand elements.

Disadvantages of Selection Sort Algorithm

  1. Time complexity: The time complexity is O(n^2). This means that the algorithm becomes very slow as the size of the input array grows. For large arrays, selection sort can take a long time to complete.
  2. Not stable: Selection sort is not a stable sorting algorithm. It does not preserve the relative order of items with equal keys
  3. Not optimal: Selection sort is not an optimal sorting algorithm. An optimal sorting algorithm can sort any input array in the minimum possible number of comparisons and swaps. However, selection sort does not always achieve the minimum number of comparisons and swaps required to sort an array.
Summary

So, here we saw every aspect of the selection sort algorithm in data structures. It must not have been difficult to understand as it's one of the easiest sorting algorithms. Just make sure you are thorough with arrays in data structures. To apply your knowledge of the selection sort algorithm, enroll in our Best Data Structures And Algorithms Course.

Similar Sorting Algorithms

FAQs

Q1. How many swaps does the selection sort algorithm make?

The selection sort algorithm makes n-1 swaps in the worst case and zero swaps in the best case. Therefore, it never makes more than O(n) swaps.

Q2. Is the selection sort algorithm faster than bubble sort?

Both selection sort and bubble sort have a worst-case complexity of O(n^2). However, the selection sort algorithm is still faster than bubble sort in the worst-case scenario when “memory write” is a costly operation. This is because selection sort makes fewer swaps compared to bubble sort.

Q3. Is the Selection Sort Algorithm in place?

Yes, the Selection Sort Algorithm is an in-place algorithm, as it does not require extra space.

Q4. Does the Selection sort algorithm perform comparisons?

Yes, selection sort is a comparison-based algorithm.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
ASP.NET Core Certification Training Jul 15 MON, WED, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jul 15 MON, WED, FRI
Filling Fast
07:00AM to 08:30AM (IST)
Get Details
Azure Master Class Jul 20 SAT, SUN
Filling Fast
03:00PM to 05:00PM (IST)
Get Details
ASP.NET Core Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Software Architecture and Design Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Solution Architect Certification Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Azure Developer Certification Training Jul 28 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Data Structures and Algorithms Training with C# Jul 28 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Angular Certification Course Aug 11 SAT, SUN
Filling Fast
09:30AM to 11:30AM (IST)
Get Details
ASP.NET Core Certification Training Aug 24 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this