The selection sort algorithm is a simple, yet effective sorting algorithm. A selection-based sorting algorithm is described as an in-place comparison-based algorithm that 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. When sorting a small list, selection sort can be used.

In the selection sort, the cost of swapping is irrelevant, and all elements must be checked. The cost of writing to memory matters in selection sort, just as it does in flash memory (the number of writes/swaps is O(n) as opposed to O(n2) in bubble sort).

## What Is a Selection Sort Algorithm?

- Selection sort is an effective and efficient sort algorithm based on comparison operations.
- It adds one element in each iteration.
- You need to select the smallest element in the array and move it to the beginning of the array by swapping with the front element.
- You can also accomplish this by selecting the most potent element and positioning it at the back end.
- In each iteration, selection sort selects an element and places it in the appropriate position.

Following the definition of the selection sort algorithm, you will now go over the working procedure of the selection sort algorithm in this tutorial.

## How Does the Selection Sort Algorithm Work?

Selection sort works by taking the smallest element in an unsorted array and bringing it to the front. You’ll go through each item (from 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.

- As an example, consider the array depicted below.

- The entire list is scanned sequentially for the first position in the sorted list. You search the whole list and find that 10 is the lowest value in the first position, where 15 is stored.

- As a result, you replaced 15 with 10. After one iteration, the number 10, which happens to be the lowest value on the list, appears at the top of the sorted list.

- You must begin by scanning the rest of the list linearly for the second position, where 30 is located.

- You discovered that 15 is the second lowest value on the list and should be placed second. You must switch these values.

- After two iterations, the two least values are positioned at the beginning in a sorted manner.

The same procedure is followed for the remaining array items.

The following is a visual representation of the entire sorting process.

Moving forward in this tutorial, you will see an algorithm and its pseudocode after understanding the working procedure of a selection sort algorithm.

## 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

The selection sort pseudocode is as follows:

function selection sort array : array of items size : size of list for i = 1 to size - 1 minimum = i // set current element as minimum for j = i+1 to n // check the element to be minimum if array[j] < array[minimum] then minimum = j; end if end for if indexofMinimum != i then //swap the minimum element with the current element swap array[minimum] and array[i] end if end for end function |

You will now look at the performance of the selection sort algorithm in this tutorial.

## The Complexity of Selection Sort Algorithm

The time complexity of the selection sort algorithm is:

- The selection sort algorithm is made up of two nested loops.
- It has an O (n2) time complexity due to the two nested loops.

Best Case Complexity occurs when there is no need for sorting, i.e., the array has already been sorted. The time complexity of selection sort in the best-case scenario is O. (n2).

Average Case Complexity occurs when the array elements are arranged in a jumbled order that is neither ascending nor descending correctly. The selection sort has an average case time complexity of O. (n2).

Worst-case complexity - Worst case occurs when array elements must be sorted in reverse order. Assume you need to sort the array elements in ascending order, but they are in descending order. Selection sort has a worst-case time complexity of O. (n2).

The space complexity of the selection sort algorithm is:

- An in-place algorithm is a selection sort algorithm.
- It performs all computations in the original array and does not use any other arrays.
- As a result, the space complexity is O. (1).

You will now look at some applications of the selection sort algorithm in this tutorial.

## Applications of Selection Sort Algorithm

The following are some applications of how to use selection sort:

- Selection sort consistently outperforms bubble and gnome sort.
- When memory writing is a costly operation, this can be useful.
- In terms of the number of writes ((n) swaps versus O(n2) swaps), selection sort is preferable to insertion sort.
- It almost always far outnumbers the number of writes made by cycle sort, even though cycle sort is theoretically optimal in terms of the number of writes.
- This is important if writes are significantly more expensive than reads, as with EEPROM or Flash memory, where each write reduces the memory's lifespan.

Following an understanding of some applications of the selection sort algorithm, you will now look at code implementation in C.

## Code Implementation of Selection Sort Algorithm

### 1. C Implementation

In C, we use a ‘struct’ to define the structure of the ‘Employees’ table. We create an instance of this ‘struct’ to represent an employee.

```
#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();
}
}
```

### 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();
```

## Advantages and Disadvantages of Selection Sort Algorithm

### Advantages of Selection Sort Algorithm

#### 1. Simple to Understand and Implement

The algorithm is easy to understand and implement, making it a good starting point for beginners learning sorting algorithms.

#### 2. In-Place Sorting

Selection sort does not require additional storage as it sorts the list in place.

#### 3. No Extra Space Required

It has a space complexity of O(1)O(1)O(1), meaning it only needs a constant amount of extra space.

#### 4. Consistent Performance

The time complexity is always O(n2)O(n^2)O(n2), regardless of the input, providing predictable performance.

#### 5. Works Well on Small Lists

Selection sort performs well on small lists and arrays due to its simplicity.

#### 6. No Repeated Swaps

Each element is swapped at most once, reducing the total number of swaps compared to some other algorithms.

#### 7. Suitable for Limited Resources

Its minimal memory usage makes it suitable for systems with limited resources.

#### 8. Stable in Theoretical Sense

It can be modified to be stable, meaning equal elements retain their relative order.

#### 9. Useful for Teaching

It helps in teaching the concept of sorting and algorithm analysis due to its straightforward nature.

#### 10. Minimal Memory Writes

Since it minimizes the number of swaps, it reduces wear on write-limited storage media.

### Disadvantages of Selection Sort Algorithm

#### 1. Inefficient for Large Lists

The O(n2)O(n^2)O(n2) time complexity makes it inefficient for large lists compared to more advanced algorithms like quicksort or mergesort.

#### 2. Not Adaptive

Selection sort does not adapt to the initial order of elements; it performs the same number of comparisons regardless of the input.

#### 3. High Number of Comparisons

It performs n(n−1)/2n(n-1)/2n(n−1)/2 comparisons, which is inefficient compared to other sorting algorithms.

#### 4. Poor Cache Performance

Due to its pattern of accessing memory, it has poor cache performance.

#### 5. Not Stable

By default, selection sort is not a stable sorting algorithm, which means it might change the relative order of equal elements.

#### 6. No Early Termination

Selection sort always goes through all elements, even if the list is already sorted, leading to unnecessary comparisons.

## Next Steps

This tutorial taught you what a selection sort algorithm is and how it works with an example to help you understand it well. Following that, you looked at the algorithm and pseudo code for this algorithm and how it performed in each scenario (best-case, average-case, and worst-case) before moving on to its application and, finally, a practical demonstration of the selection sort algorithm in C.

If you want a more comprehensive study that goes beyond Data Structure and Algorithms and covers the most in-demand programming languages and skills today, Simplilearn’s Full Stack Web Development PG Program in collaboration with Caltech CTME is the course for you. It's time to go out and explore.

If you have any questions about this tutorial, please leave them in the comments section below so that our experts can answer them as soon as possible.

Please stay safe until then and follow the Simplilearn channel.

## FAQs

### 1. Is Selection Sort Algorithm Stable?

The selection sort algorithm is unstable by default. When a sorting method is stable, it indicates that 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 due to this swapping procedure altering 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 from 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 element that was initially unsorted. 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 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 in the worst case produces about n * n = n^2 comparisons.

### 4. Is Selection Sort a Greedy Algorithm?

It is arguable that selection sort is not a greedy algorithm. By choosing the smallest element at each stage, it 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 have a direct impact on the final sorted result. There are more effective sorting algorithms that don't use this kind of repeated selection.