Data Structures & Algorithms
Table of content:
- What Is Data Structure?
- Key Features Of Data Structures
- Basic Terminologies Related To Data Structures
- Types Of Data Structures
- What Are Linear Data Structures & Its Types?
- What Are Non-Linear Data Structures & Its Types?
- Importance Of Data Structure In Programming
- Basic Operations On Data Structures
- Applications Of Data Structures
- Real-Life Applications Of Data Structures
- Linear Vs. Non-linear Data Structures
- What Are Algorithms? The Difference Between Data Structures & Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Asymptotic Notation?
- How Asymptotic Notation Helps In Analyzing Performance
- Types Of Asymptotic Notation
- Big-O Notation (O)
- Omega Notation (Ω)
- Theta Notation (Θ)
- Little-O Notation (o)
- Little-Omega Notation (ω)
- Summary Of Asymptotic Notations
- Real-World Applications Of Asymptotic Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Big O Notation
- Types Of Time Complexity
- Space Complexity In Big O Notation
- How To Determine Big O Complexity
- Best, Worst, And Average Case Complexity
- Applications Of Big O Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Time Complexity?
- Why Do You Need To Calculate Time Complexity?
- The Time Complexity Algorithm Cases
- Time Complexity: Different Types Of Asymptotic Notations
- How To Calculate Time Complexity?
- Time Complexity Of Sorting Algorithms
- Time Complexity Of Searching Algorithms
- Writing And optimizing An algorithm
- What Is Space Complexity And Its Significance?
- Relation Between Time And Space Complexity
- Conclusion
Table of content:
- What Is Linear Data Structure?
- Key Characteristics Of Linear Data Structures
- What Are The Types Of Linear Data Structures?
- What Is An Array Linear Data Structure?
- What Are Linked Lists Linear Data Structure?
- What Is A Stack Linear Data Structure?
- What Is A Queue Linear Data Structure?
- Most Common Operations Performed in Linear Data Structures
- Advantages Of Linear Data Structures
- What Is Nonlinear Data Structure?
- Difference Between Linear & Non-Linear Data Structures
- Who Uses Linear Data Structures?
- Conclusion
- Frequently Asked Questions
Table of content:
- What is a linear data structure?
- What is a non-linear data structure?
- Difference between linear data structure and non-linear data structure
- FAQs about linear and non-linear data structures
Table of content:
- What Is Sorting In Data Structures?
- What Is Bubble Sort?
- What Is Selection Sort?
- What Is Insertion Sort?
- What Is Merge Sort?
- What Is Quick Sort?
- What Is Heap Sort?
- What Is Radix Sort?
- What Is Bucket Sort?
- What Is Counting Sort?
- What Is Shell Sort?
- Choosing The Right Sorting Algorithm
- Applications Of Sorting
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Bubble Sort Algorithm
- Bubble Sort Algorithm
- Implementation Of Bubble Sort In C++
- Time And Space Complexity Analysis Of Bubble Sort Algorithm
- Advantages Of Bubble Sort Algorithm
- Disadvantages Of Bubble Sort Algorithm
- Applications of Bubble Sort Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Merge Sort Algorithm
- Algorithm For Merge Sort
- Implementation Of Merge Sort In C++
- Time And Space Complexity Analysis Of Merge Sort
- Advantages And Disadvantages Of Merge Sort
- Applications Of Merge Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Selection Sort Algorithm
- Algorithmic Approach To Selection Sort
- Implementation Of Selection Sort Algorithm
- Complexity Analysis Of Selection Sort
- Comparison Of Selection Sort With Other Sorting Algorithms
- Advantages And Disadvantages Of Selection Sort
- Application Of Selection Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Insertion Sort Algorithm?
- How Does Insertion Sort Work? (Step-by-Step Explanation)
- Implementation of Insertion Sort in C++
- Time And Space Complexity Of Insertion Sort
- Applications Of Insertion Sort Algorithm
- Comparison With Other Sorting Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Quick Sort Algorithm
- Step-By-Step Working Of Quick Sort
- Implementation Of Quick Sort Algorithm
- Time Complexity Analysis Of Quick Sort
- Advantages Of Quick Sort Algorithm
- Disadvantages Of Quick Sort Algorithm
- Applications Of Quick Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Heap Data Structure
- Working Of Heap Sort Algorithm
- Implementation Of Heap Sort Algorithm
- Advantages Of Heap Sort
- Disadvantages Of Heap Sort
- Real-World Applications Of Heap Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Counting Sort Algorithm
- Conditions For Using Counting Sort Algorithm
- How Counting Sort Algorithm Works?
- Implementation Of Counting Sort Algorithm
- Time And Space Complexity Analysis Of Counting Sort
- Comparison Of Counting Sort With Other Sorting Algorithms
- Advantages Of Counting Sort Algorithm
- Disadvantages Of Counting Sort Algorithm
- Applications Of Counting Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Shell Sort Algorithm
- Working Of Shell Sort Algorithm
- Implementation Of Shell Sort Algorithm
- Time Complexity Analysis Of Shell Sort Algorithm
- Advantages Of Shell Sort Algorithm
- Disadvantages Of Shell Sort Algorithm
- Applications Of Shell Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is The Binary Search Algorithm?
- Conditions For Using Binary Search
- Steps For Implementing Binary Search
- Iterative Method For Binary Search With Implementation Examples
- Recursive Method For Binary Search
- Complexity Analysis Of Binary Search Algorithm
- Iterative Vs. Recursive Implementation Of Binary Search
- Advantages & Disadvantages Of Binary Search
- Practical Applications & Real-World Examples Of Binary Search
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Linked List In Data Structures?
- Types Of Linked Lists In Data Structures
- Linked List Operations In Data Structures
- Advantages And Disadvantages Of Linked Lists In Data Structures
- Comparison Of Linked Lists And Arrays
- Applications Of Linked Lists
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Singly Linked List In Data Structure?
- Insertion Operations On Singly Linked Lists
- Deletion Operation On Singly Linked List
- Searching For Elements In Single Linked List
- Calculating Length Of Single Linked List
- Practical Applications Of Singly Linked Lists In Data Structure
- Common Problems With Singly Linked Lists
- Conclusion
- Frequently Asked Questions (FAQ)
Table of content:
- What Is A Linked List?
- Reverse A Linked List
- How To Reverse A Linked List? (Approaches)
- Recursive Approach To Reverse A Linked List
- Iterative Approach To Reverse A Linked List
- Using Stack To Reverse A Linked List
- Complexity Analysis Of Different Approaches To Reverse A Linked List
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Graph Data Structure?
- Importance Of Graph Data Structures
- Types Of Graphs In Data Structure
- Types Of Graph Algorithms
- Application Of Graphs In Data Structures
- Challenges And Complexities In Graphs
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Tree Data Structure?
- Terminologies Of Tree Data Structure:
- Different Types Of Tree Data Structures
- Basic Operations On Tree Data Structure
- Applications Of Tree Data Structures
- Comparison Of Trees, Graphs, And Linear Data Structures
- Advantages Of Tree Data Structure
- Disadvantages Of Tree Data Structure
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Dynamic Programming?
- Real-Life Example: The Jigsaw Puzzle Analogy
- How To Solve A Problem Using Dynamic Programming?
- Dynamic Programming Algorithm Techniques
- Advantages Of Dynamic Programming
- Disadvantages Of Dynamic Programming
- Applications Of Dynamic Programming
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Sliding Window Algorithm
- How Does The Sliding Window Algorithm Works?
- How To Identify Sliding Window Problems?
- Fixed-Size Sliding Window Example: Maximum Sum Subarray Of Size k
- Variable-Size Sliding Window Example: Smallest Subarray With A Given Sum
- Advantages Of Sliding Window Technique
- Disadvantages Of Sliding Window Technique
- Conclusion
- Frequently Asked Questions
Table of content:
- Introduction To Data Structures
- Data Structures Interview Questions: Basics
- Data Structures Interview Questions: Intermediate
- Data Structures Interview Questions: Advanced
- Conclusion
What Is Selection Sort Algorithm? Explained With Code Examples

Sorting is a fundamental operation in computer science, and one of the simplest sorting techniques is the Selection Sort algorithm. It follows a straightforward approach: repeatedly finding the smallest (or largest) element from an unsorted section and swapping it with the first unsorted element. While not the most efficient sorting method for large datasets, its simplicity makes it a great choice for learning how sorting works at a basic level.
In this article, we will explore the working of the Selection Sort algorithm, its time complexity, implementation in different programming languages, and key advantages and limitations.
Understanding The Selection Sort Algorithm
Selection Sort is a simple and intuitive sorting algorithm that works by repeatedly finding the smallest (or largest) element from the unsorted part of the array and swapping it with the first unsorted element. This process continues until the entire array is sorted.
How Selection Sort Works
- Start with the first element and assume it is the smallest.
- Scan the rest of the array to find the actual smallest element.
- Swap the smallest element found with the first element.
- Move to the next position and repeat the process for the remaining unsorted part of the array.
- Continue until the array is fully sorted.
Real-Life Analogy
Imagine you are organizing books on a shelf in ascending order of size. You start by picking the smallest book (shortest in height) and placing it in the first position. Then, you find the next smallest and place it in the second position. You continue this process until all books are in order. This is exactly how Selection Sort works with different data structures!
Algorithmic Approach To Selection Sort
Selection Sort follows a straightforward approach to sorting an array. Let's first look at the pseudo-code, followed by an explanation of its key steps.
Pseudo-code For Selection Sort
SelectionSort(arr, n):
for i from 0 to n-2: // Loop over each element except the last
min_index = i // Assume the first element of the unsorted part is the smallest
for j from i+1 to n-1: // Find the minimum in the unsorted part
if arr[j] < arr[min_index]:
min_index = j
Swap arr[i] and arr[min_index] // Place the smallest element at its correct position
Key Steps In The Working Of The Algorithm
1. Initialize Outer Loop (i from 0 to n-2)
- The loop runs from the first element to the second-last element since the last element will already be sorted after all iterations.
- We assume the first element of the unsorted section (arr[i]) is the minimum.
2. Find the Minimum Element in the Remaining Array
- A second loop (j from i+1 to n-1) scans the unsorted part of the array.
- If an element smaller than arr[min_index] is found, update min_index to store its index.
3. Swap the Found Minimum Element with the First Unsorted Element
- After finding the smallest element in the unsorted part, swap it with arr[i] to place it in its correct position.
4. Repeat the Process Until the Entire Array is Sorted
- The outer loop progresses, shrinking the unsorted part, until the whole array is sorted.
Implementation Of Selection Sort Algorithm
Below is the C++ implementation of the Selection Sort algorithm.
Code Example:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i; // Assume first unsorted element is the smallest
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j; // Update the index of the minimum element
}
}
// Swap the found minimum element with the first element of the unsorted part
swap(arr[i], arr[min_index]);
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
selectionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37
Explanation:
In the above code example-
- We start by including the necessary header file <iostream> to use input-output operations. The using namespace std; statement allows us to use standard library functions without prefixing them with std::.
- The selectionSort() function sorts an array using the Selection Sort algorithm. It takes an array and its size as parameters.
- In each iteration of the outer loop, we assume the first unsorted element is the smallest. We store its index in min_index.
- The inner loop iterates through the remaining unsorted elements to find the actual smallest element in that part of the array. If a smaller element is found, we update min_index to its position.
- After finding the minimum element in the unsorted part, we swap it with the first unsorted element, ensuring that the sorted portion of the array expands with each iteration.
- The printArray() function is a helper function that prints all elements of the array separated by spaces, followed by a newline.
- In main(), we define an array {29, 10, 14, 37, 13} and calculate its size using sizeof(arr) / sizeof(arr[0]).
- We print the original array before sorting using the printArray() function.
- We call selectionSort() to sort the array in ascending order.
- After sorting, we print the updated array to show the sorted result.
- The program returns 0, indicating successful execution.
Complexity Analysis Of Selection Sort
The table below summarizes the time and space complexity of the Selection Sort algorithm in different scenarios.
Case |
Time Complexity |
Explanation |
Best Case (Sorted Array) |
O(n²) |
Even if the array is already sorted, Selection Sort still compares every element to find the minimum. No swaps occur, but comparisons remain O(n²). |
Average Case (Random Order) |
O(n²) |
Regardless of input, Selection Sort always performs (n-1) + (n-2) + ... + 1 = O(n²) comparisons. |
Worst Case (Reversed Order) |
O(n²) |
The algorithm must scan and swap elements in every iteration, making it still O(n²). |
Best/Worst/Average Swaps |
O(n) |
At most, there are (n-1) swaps, as only one swap per iteration occurs. |
Space Complexity |
O(1) |
Selection Sort is an in-place sorting algorithm, meaning it requires no extra space apart from the given array. |
Stable? |
No |
Selection Sort is not stable, as swapping non-adjacent elements may disrupt the relative order of equal elements. |
Adaptive? |
No |
Selection Sort does not take advantage of partially sorted arrays—it always performs O(n²) comparisons. |
Comparison Of Selection Sort With Other Sorting Algorithms
The table below compares Selection Sort with other common sorting algorithms based on key parameters like time complexity, space complexity, stability, and adaptiveness.
Sorting Algorithm |
Best Case |
Average Case |
Worst Case |
Space Complexity |
Stable? |
Adaptive? |
Selection Sort |
O(n²) |
O(n²) |
O(n²) |
O(1) (In-place) |
No |
No |
O(n) |
O(n²) |
O(n²) |
O(1) (In-place) |
Yes |
Yes |
|
O(n) |
O(n²) |
O(n²) |
O(1) (In-place) |
Yes |
Yes |
|
Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) (Extra Space) |
Yes |
No |
Quick Sort (Avg.) |
O(n log n) |
O(n log n) |
O(n²) (Worst) |
O(log n) (In-place) |
No |
Yes |
Heap Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) (In-place) |
No |
No |
Counting Sort |
O(n + k) |
O(n + k) |
O(n + k) |
O(k) (Extra Space) |
Yes |
No |
Radix Sort |
O(nk) |
O(nk) |
O(nk) |
O(n + k) (Extra Space) |
Yes |
No |
Key Takeaways:
- Selection Sort is inefficient for large datasets due to its O(n²) time complexity.
- Merge Sort, Quick Sort, and Heap Sort are more efficient with O(n log n) time complexity.
- Bubble Sort and Insertion Sort are adaptive, meaning they perform better on nearly sorted data.
- Stable Sorting Algorithms (like Merge Sort, Bubble Sort, and Counting Sort) maintain the order of equal elements.
Advantages And Disadvantages Of Selection Sort
Let's explore the strengths and weaknesses of Selection Sort.
Advantages Of Selection Sort:
- Simple and Easy to Implement: The algorithm is straightforward and does not require complex logic.
- In-Place Sorting Algorithm: It requires only O(1) extra space, meaning it does not need additional memory beyond the input array.
- Performs Well on Small Datasets: For small arrays, Selection Sort can be a viable option due to its simplicity.
- Works Well When Memory Writes Are Costly: Since it performs at most (n-1) swaps, it minimizes writes compared to Bubble Sort or Insertion Sort, making it useful in scenarios like Flash memory where write operations are expensive.
Disadvantages Of Selection Sort:
- Time Complexity is Always O(n²): Regardless of whether the input is sorted or not, Selection Sort always performs O(n²) comparisons, making it inefficient for large datasets.
- Not a Stable Sort: If there are equal elements, their relative order might change due to swapping, which can cause issues in some applications.
- Not Adaptive: Selection Sort does not take advantage of already sorted or partially sorted data, unlike Insertion Sort, which performs O(n) in the best case.
- Slower Compared to Other Sorting Algorithms: Sorting algorithms like Merge Sort, Quick Sort, and Heap Sort perform much better on large datasets with an average time complexity of O(n log n).
Application Of Selection Sort
Some of the common applications of the selection sort algorithm are:
- Small datasets – Since Selection Sort has a time complexity of O(n²), it is best suited for small datasets where its simplicity outweighs efficiency concerns.
- Embedded systems – Due to its minimal memory requirements and in-place sorting nature, Selection Sort is useful in memory-constrained environments like microcontrollers.
- Teaching sorting concepts – Selection Sort is often used in educational settings to introduce sorting algorithms due to its simple logic and step-by-step element swapping.
- Sorting linked lists – Although Selection Sort is not the best choice for arrays, it works well with linked lists since swapping nodes requires only pointer adjustments, avoiding unnecessary data movement.
- Selecting top k elements – When we only need the smallest or largest k elements, Selection Sort can be useful since it finds the smallest elements in each iteration.
- Stable environments – In cases where data movement cost is minimal and simplicity is preferred over speed, Selection Sort is a viable option.
Conclusion
Selection Sort is a simple yet inefficient sorting algorithm that works by repeatedly selecting the smallest element and placing it in its correct position. While it is easy to understand and implement, its O(n²) time complexity makes it impractical for large datasets. It is not adaptive, meaning it does not benefit from partially sorted data, and it is also not stable, which can impact sorting when dealing with duplicate values.
Despite its limitations, Selection Sort is useful in scenarios where memory writes are expensive, as it performs fewer swaps compared to other quadratic-time algorithms like Bubble Sort. However, for larger datasets, more efficient sorting algorithms like Merge Sort, Quick Sort, or Heap Sort should be preferred.
Frequently Asked Questions
Q. Why is Selection Sort called "Selection" Sort?
Selection Sort gets its name from the way it selects the smallest (or largest) element from the unsorted part of the array and places it in its correct position in each iteration. The process involves repeatedly selecting the minimum element and moving it to the correct position, hence the name Selection Sort.
Q. What is the worst-case time complexity of Selection Sort?
The worst-case time complexity of Selection Sort is O(n²). This happens when the array is sorted in the reverse order because the algorithm still performs (n-1) + (n-2) + ... + 1 comparisons, which sums up to O(n²). Even if the array is already sorted, Selection Sort does not take advantage of it and continues to perform all comparisons.
Q. Is Selection Sort a stable sorting algorithm? Why or why not?
No, Selection Sort is not a stable sorting algorithm. A sorting algorithm is considered stable if it preserves the relative order of equal elements in the sorted output.
For example, consider the following array of tuples where the second value represents an index:
(3, A) (1, B) (3, C) (2, D)
Sorting this using Selection Sort might result in:
(1, B) (2, D) (3, C) (3, A) ❌ (Order of (3, A) and (3, C) changed)
Since Selection Sort swaps non-adjacent elements, it does not guarantee that equal elements remain in their original order, making it unstable.
Q. When is Selection Sort preferred over other sorting algorithms?
Selection Sort is preferred in the following cases:
- When memory writes are expensive: Since it performs at most n-1 swaps, it is useful for cases where minimizing write operations is crucial (e.g., Flash memory, EEPROM).
- For small datasets: Due to its simple implementation, it can be used for sorting small arrays where efficiency is not a major concern.
- When a stable sort is not required: If the relative order of duplicate elements does not matter, Selection Sort can be considered.
However, for large datasets, Merge Sort, Quick Sort, or Heap Sort are better choices due to their O(n log n) time complexity.
Q. How does Selection Sort compare to Bubble Sort and Insertion Sort?
Feature |
Selection Sort |
Bubble Sort |
Insertion Sort |
Best Time Complexity |
O(n²) |
O(n) |
O(n) |
Worst Time Complexity |
O(n²) |
O(n²) |
O(n²) |
Space Complexity |
O(1) |
O(1) |
O(1) |
Stable? |
No |
Yes |
Yes |
Adaptive? |
No |
Yes |
Yes |
Swaps Performed |
O(n) |
O(n²) |
O(n) |
- Insertion Sort is adaptive, meaning it performs well on nearly sorted arrays (O(n) in best case).
- Bubble Sort is stable, meaning it preserves the order of equal elements, while Selection Sort is not.
- Selection Sort is better than Bubble Sort in terms of fewer swaps, but it still has O(n²) comparisons.
For efficiency, Insertion Sort is preferable when dealing with small or nearly sorted datasets.
Suggested Reads:
- Difference Between Hashing And Encryption Decoded
- 53 Frequently Asked Linked List Interview Questions With Answers 2024
- Data Structure Interview Questions For 2024 [With Detailed Answers]
- Tree Topology | Advantages & Disadvantages In Computer Network
- Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions
I’m a Computer Science graduate with a knack for creative ventures. Through content at Unstop, I am trying to simplify complex tech concepts and make them fun. When I’m not decoding tech jargon, you’ll find me indulging in great food and then burning it out at the gym.
Comments
Add commentLogin to continue reading
And access exclusive content, personalized recommendations, and career-boosting opportunities.

Subscribe
to our newsletter
Kartik Deshmukh 1 day ago
Divyansh Shrivastava 4 days ago
Archana Ba Parmar 1 week ago
Amritesh Kumar 1 week ago
Mihir Kumar Ranjan 2 weeks ago
Mradulakshi Manu 2 weeks ago