Selection Sort in Data Structures

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

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

   

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.

   

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.

   

   

   

   

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

   Case	Time 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

• Bubble Sort
• Merge Sort
• Quick Sort
• Insertion Sort