What Is Selection Sort Algorithm In Data Structures?

The selection sort algorithm, while simple, is remarkably effective. An in-place comparison-based algorithm divides the list into two parts: the sorted part on the left and the unsorted part on the right. Initially, the sorted section is empty, and the unsorted section contains the entire list. This effectiveness is particularly evident when sorting a small list.

In the selection sort, the cost of swapping is irrelevant. Swapping refers to interchanging the positions of two elements in the array. All components must be checked in the selection sort and the cost of writing to memory matters. This is similar to flash memory, where the number of writes/swaps is O(n) instead of O(n2) in bubble sort.

What Is a Selection Sort Algorithm?

Selection sort is a simple comparison-based sorting algorithm that divides the input list into a sorted part at the beginning and an unsorted part at the end. The algorithm repeatedly selects the smallest (or largest, depending on the order) element from the unsorted part and swaps it with the first unsorted element, gradually growing the sorted portion until the entire list is sorted.

• Selection sort is a straightforward and efficient comparison-based sorting algorithm ideal for small datasets.
• Each iteration incrementally builds a sorted section by adding one element at a time.
• The algorithm works by identifying the smallest element in the unsorted portion of the array and swapping it with the first unsorted element, effectively moving it to the front.
• Alternatively, depending on the sorting order desired, the largest element can be selected and placed at the end of the array.
• During each iteration, the selection sort identifies the correct element and positions it appropriately within the sorted section of the array.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

How Does the Selection Sort Algorithm Work?

Selection sort takes the smallest element in an unsorted array and brings it to the front. You’ll review each item (left to right) until you find the smallest one. The first item in the array is now sorted, while the rest of the array is unsorted. Here’s the step-by-step process:

1. Initialization

• Start with an unsorted array or list.
• The array is conceptually divided into two parts: the sorted part, which is initially empty, and the unsorted part, which contains all the elements.

2. Iteration Over the Array

• The algorithm iterates over the array, one element at a time, looking for the smallest element in the unsorted portion during each iteration.

3. Finding the Minimum Element

• In each iteration, assume that the first element of the unsorted portion is the smallest.
• Compare this element with the rest of the elements in the unsorted portion.
• If a smaller element is found, update the smallest element to this new value.

4. Swapping Elements

• After the smallest element in the unsorted portion is found, swap it with the first element of the unsorted portion. This effectively moves the smallest element to its correct position in the sorted portion.

5. Reduce the Unsorted Portion

• After each swap, the boundary between the sorted and unsorted portions moves one element to the right. The sorted portion grows by one element, and the unsorted portion decreases by one.

6. Repeat the Process

• The process is repeated for the remaining unsorted elements. Each time, the next smallest element is selected and moved to the end of the sorted portion.

7. Completion

• The algorithm continues until the entire array is sorted. The array is fully sorted when the unsorted portion is reduced to a single element.

Also Read: A Detailed Guide to Array in C

Let's take a simple example to illustrate how selection sort works. Consider the array: [29, 10, 14, 37, 14].

1. First Iteration

• The unsorted array is [29, 10, 14, 37, 14].
• Find the smallest element in the unsorted portion: 10.
• Swap 10 with the first element (29).
• The array now looks like this: [10, 29, 14, 37, 14].

2. Second Iteration

• The unsorted array is [29, 14, 37, 14].
• Find the smallest element in the unsorted portion: 14.
• Swap 14 with the first element of the unsorted portion (29).
• The array now looks like this: [10, 14, 29, 37, 14].

3. Third Iteration

• The unsorted array is [29, 37, 14].
• Find the smallest element in the unsorted portion: 14.
• Swap 14 with the first element of the unsorted portion (29).
• The array now looks like this: [10, 14, 14, 37, 29].

4. Fourth Iteration

• The unsorted array is [37, 29].
• Find the smallest element in the unsorted portion: 29.
• Swap 29 with the first element of the unsorted portion (37).
• The array now looks like this: [10, 14, 14, 29, 37].

5. Final Array

• The array is now fully sorted: [10, 14, 14, 29, 37].

Time Complexity

Selection sort has a time complexity of O(n²), where n is the number of elements in the array. For each n element, the algorithm makes n-1 comparisons to find the minimum element. This quadratic time complexity makes selection sort less efficient for large datasets than more advanced algorithms like quick sort or merge sort.

Space Complexity

Selection sort is an in-place sorting algorithm, meaning it doesn't require additional storage space apart from the input array. Its space complexity is O(1), as it only uses constant extra memory.

Recommended: Time and Space Complexity in Data Structure

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

Algorithm and Pseudocode of a Selection Sort Algorithm

Algorithm of the Selection Sort Algorithm

The selection sort algorithm is as follows:

Step 1: Set Min to location 0 in Step 1.

Step 2: Look for the smallest element on the list.

Step 3: Replace the value at location Min with a different value.

Step 4: Increase Min to point to the next element

Step 5: Continue until the list is sorted.

Pseudocode of Selection Sort Algorithm

Here's the pseudocode for the selection sort algorithm in C:

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    // Move the boundary of the unsorted portion one element to the right after each iteration
    for (i = 0; i < n-1; i++) {
        // Assume the first element is the minimum
        minIndex = i;
        // Find the minimum element in the unsorted portion of the array
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element of the unsorted portion
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

The Complexity of Selection Sort Algorithm

Here’s a table explaining the different aspects of selection sort algorithms.

Applications of Selection Sort Algorithm

Here are the top five applications of the selection sort algorithm:

1. Selection sort is effective for sorting small datasets where the overhead of more complex algorithms isn't justified. Its simplicity and ease of implementation make it suitable for educational and small-scale applications.
2. Selection sort is an in-place sorting algorithm with a space complexity of O(1). It's helpful in environments with limited memory, where minimizing additional space usage is crucial.
3. Selection sort can be advantageous in scenarios where the cost of writing to memory is significantly higher than reading, such as with flash memory or EEPROM. Compared to algorithms like bubble sort, it minimizes the number of swaps (write operations).
4. Selection sort can be used as the initial pass in more complex sorting algorithms. For instance, hybrid sorting algorithms might sort a small subset of data before applying a more advanced algorithm like quick sort or merge sort to the remainder.
5. Although selection sort is not the most efficient algorithm for finding the kth smallest or largest element, it can be used in small datasets. By running the algorithm up to the k-th iteration, you can directly obtain the desired element without thoroughly sorting the array.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program

Code Implementation of Selection Sort Algorithm

1. C Implementation

Here’s a complete implementation of the selection sort algorithm in C.

#include <stdio.h>
#include <string.h>

// Define the Employee structure
struct Employee {
    int EmployeeID;
    char FirstName[50];
    char LastName[50];
    char BirthDate[11];
    char HireDate[11];
    double Salary;
};

// Function to display employee information
void displayEmployee(struct Employee emp) {
    printf("ID: %d\n", emp.EmployeeID);
    printf("First Name: %s\n", emp.FirstName);
    printf("Last Name: %s\n", emp.LastName);
    printf("Birth Date: %s\n", emp.BirthDate);
    printf("Hire Date: %s\n", emp.HireDate);
    printf("Salary: %.2f\n", emp.Salary);
}

int main() {
    struct Employee emp;
    emp.EmployeeID = 1;
    strcpy(emp.FirstName, "John");
    strcpy(emp.LastName, "Doe");
    strcpy(emp.BirthDate, "1980-01-01");
    strcpy(emp.HireDate, "2020-01-01");
    emp.Salary = 50000.00;

    displayEmployee(emp);

    return 0;
}

2. Python Implementation

In Python, we define a class to represent the ‘Employees’ table and create an instance of this class to represent an employee.

class Employee:
    def __init__(self, employee_id, first_name, last_name, birth_date, hire_date, salary):
        self.EmployeeID = employee_id
        self.FirstName = first_name
        self.LastName = last_name
        self.BirthDate = birth_date
        self.HireDate = hire_date
        self.Salary = salary

    def display(self):
        print(f"ID: {self.EmployeeID}")
        print(f"First Name: {self.FirstName}")
        print(f"Last Name: {self.LastName}")
        print(f"Birth Date: {self.BirthDate}")
        print(f"Hire Date: {self.HireDate}")
        print(f"Salary: {self.Salary}")

emp = Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00)
emp.display()

3. Java Implementation

In Java, we define a class to represent the ‘Employees’ table and create an instance of this class to represent an employee.

public class Employee {
    private int EmployeeID;
    private String FirstName;
    private String LastName;
    private String BirthDate;
    private String HireDate;
    private double Salary;

    public Employee(int employeeID, String firstName, String lastName, String birthDate, String hireDate, double salary) {
        this.EmployeeID = employeeID;
        this.FirstName = firstName;
        this.LastName = lastName;
        this.BirthDate = birthDate;
        this.HireDate = hireDate;
        this.Salary = salary;
    }

    public void display() {
        System.out.println("ID: " + EmployeeID);
        System.out.println("First Name: " + FirstName);
        System.out.println("Last Name: " + LastName);
        System.out.println("Birth Date: " + BirthDate);
        System.out.println("Hire Date: " + HireDate);
        System.out.println("Salary: " + Salary);
    }

    public static void main(String[] args) {
        Employee emp = new Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00);
        emp.display();
    }
}

Advance Your MERN Stack Career in 6 Months!

Full Stack Developer - MERN StackEXPLORE COURSE

4. JavaScript Implementation

In JavaScript, we define a class to represent the ‘Employees’ table and create an instance of this class to represent an employee.

class Employee {
    constructor(employeeID, firstName, lastName, birthDate, hireDate, salary) {
        this.EmployeeID = employeeID;
        this.FirstName = firstName;
        this.LastName = lastName;
        this.BirthDate = birthDate;
        this.HireDate = hireDate;
        this.Salary = salary;
    }

    display() {
        console.log("ID: " + this.EmployeeID);
        console.log("First Name: " + this.FirstName);
        console.log("Last Name: " + this.LastName);
        console.log("Birth Date: " + this.BirthDate);
        console.log("Hire Date: " + this.HireDate);
        console.log("Salary: " + this.Salary);
    }
}
const emp = new Employee(1, "John", "Doe", "1980-01-01", "2020-01-01", 50000.00);
emp.display();

5. C++ Implementation

Here’s a complete implementation of the selection sort algorithm in C++:

#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
    int i, j, minIndex;
    // Move the boundary of the unsorted portion one element to the right after each iteration
    for (i = 0; i < n-1; i++) {
        // Assume the first element is the minimum
        minIndex = i;
        // Find the minimum element in the unsorted portion of the array
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element of the unsorted portion
        swap(arr[minIndex], arr[i]);
    }
}
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Original array: \n";
    printArray(arr, n);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Accelerate your career as a skilled MERN Stack Developer by enrolling in a unique Full Stack Developer - MERN Stack Master's program. Get complete development and testing knowledge on the latest technologies. Contact us TODAY!

Advantages and Disadvantages of Selection Sort Algorithm

Advantages of Selection Sort Algorithm

• The algorithm is easy to understand and implement, making it a good choice for educational purposes and for those new to programming.
• Selection sort sorts the array in place, requiring constant additional memory (O(1) space complexity).
• Selection sort performs fewer swaps than algorithms like bubble sort, which is beneficial when writing to memory, which is costly, such as in flash memory or EEPROM.
• While not the fastest, selection sort can be effective on small datasets where the overhead of more complex algorithms isn't justified.
• The time complexity of the selection sort is O(n²) in all cases (best, average, and worst). It doesn't depend on the initial order of elements, providing predictable performance.
• Unlike other sorting algorithms, selection sort doesn’t require extra memory for auxiliary data structures, making it suitable for systems with limited memory.
• The algorithm progressively builds the sorted portion of the array, making it easier to visualize and debug than other algorithms.
• Selection sort is easy to adapt for sorting in ascending and descending order, requiring only a minor modification in the comparison operation.
• The algorithm can help select the kth smallest or largest element in an unsorted array without thoroughly sorting it.
• Although selection sort is not inherently stable, it can be made stable with slight modifications, such as using linked lists or tracking indices.

Disadvantages of Selection Sort Algorithm

• With a time complexity of O(n²), selection sort is inefficient for large datasets, making it slower than more advanced algorithms like quick sort, merge sort, or heap sort.
• Selection sort does not take advantage of the existing order of elements. It performs the same number of operations regardless of whether the array is partially or fully sorted.
• The algorithm is unstable by default, meaning equal elements may not maintain their original relative order after sorting.
• The algorithm needs better cache performance due to its non-sequential memory access patterns, leading to slower execution on modern processors than algorithms like merge sort or quick sort.
• Selection sort needs to lend itself better to parallelization, making it less suitable for modern multi-core processors than other algorithms that can be parallelized effectively.

Next Steps

This tutorial has provided a comprehensive understanding of the selection sort algorithm, its functionality, and an illustrative example. You've explored the algorithm's pseudocode, its performance in different scenarios, and its practical application. The tutorial culminated in a hands-on demonstration of the selection sort algorithm in action, implemented in popular programming languages such as C, Java, Python, and C++, providing you with a practical understanding of the algorithm.

If you're seeking a comprehensive study that goes beyond Data Structures and Algorithms and covers today's most in-demand programming languages and skills, then Simplilearn's Full Stack Developer—MERN Stack program in collaboration with IBM is the course that will inform and empower you.

FAQs

1. Is Selection Sort Algorithm Stable?

The selection sort algorithm is unstable by default. When a sorting method is stable, equal elements keep their relative order after sorting. The smallest (or largest, depending on the sorting order) element is chosen from the unsorted section of the list for each iteration of the selection sort, and it is swapped out for the initial unsorted element. The algorithm may become unstable because this swapping procedure alters the relative order of equal items. Selection sort is less appropriate for large datasets or situations where stability is critical due to its inherent instability and inefficiency, despite its simplicity and ease of implementation.

2. Is Selection Sort Algorithm In-Place?

In-place sorting is indeed what the selection sort algorithm does. This indicates that other than a few variables needed to track the current index and the minimum element, it doesn't use any more memory than the original array. To sort the array, the algorithm repeatedly chooses the smallest (or largest) element from the unsorted section and replaces it with the initially unsorted element. Since no additional storage is required, this procedure is completed within the array, resulting in a space complexity of 𝑂 (1). Selection sort is less efficient in terms of time complexity than other sorting algorithms for larger datasets, but it is memory economical due to its in-place nature.

3. Why Is Selection Sort O’n 2?

O(n^2) is the runtime complexity of the selection sort due to the nested loops. It finds the minimal value by iterating (n times) through the unsorted elements in each pass. Subsequently, iterating over the full array n times, it replaces the initial member with the minimum. For large datasets, selection sort is inefficient because of this double iteration, which produces about n * n = n^2 comparisons in the worst case.

4. Is Selection Sort a Greedy Algorithm?

Arguably, selection sort is not a greedy algorithm. Choosing the smallest element at each stage makes "greedy" decisions, although this doesn't always result in the best answer. Although a sorted array is produced, it's possible that the minimal selection wasn't made at the best location for the ultimate order. Selection sort performs numerous comparisons on each element, which might not directly impact the final sorted result.  There are more effective sorting algorithms that don't use this kind of repeated selection.