Hi everyone, inside this article we will see the concept about Selection Sort Analysis.
Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from an unsorted list and moving it to the beginning of the list.
The algorithm divides the input list into two parts: the sorted sublist, which is initially empty, and the unsorted sublist, which contains all the remaining elements. The selection sort algorithm then repeatedly selects the smallest element from the unsorted sublist and adds it to the sorted sublist until the entire list is sorted.
Algorithm of Selection Sort
Here is the step-by-step process for selection sort:
- Start with an unsorted list of n elements.
- Find the minimum element in the unsorted list.
- Swap the minimum element with the first element in the unsorted list.
- Move the boundary of the sorted sublist one element to the right.
- Repeat steps 2-4 until the entire list is sorted.
Selection sort has a time complexity of O(n^2) in both the worst case and average case. This is because the algorithm requires n-1 passes over the list to fully sort it, and each pass requires finding the minimum element in the unsorted sublist, which takes O(n) time.
Here is the selection sort algorithm in pseudocode:
function selectionSort(list):
n = length(list)
for i from 0 to n-1:
min_index = i
for j from i+1 to n-1:
if list[j] < list[min_index]:
min_index = j
if min_index != i:
swap(list[i], list[min_index])
return list
In this algorithm, we use two nested loops to iterate over the list and find the minimum element in the unsorted sublist. We also use an index min_index to keep track of the index of the minimum element, and we swap the minimum element with the first element in the unsorted sublist. Finally, we return the sorted list after all passes are complete.
How does Selection Sort Work?
Let’s walk through an example of how selection sort works on an unsorted list of integers:
Unsorted list: [5, 3, 8, 4, 2]First pass:
- Find the minimum element in the unsorted sublist [5, 3, 8, 4, 2], which is 2.
- Swap 2 with the first element in the unsorted sublist, which is 5.
- The sorted sublist now contains the first element of the original list, which is 2. The unsorted sublist now contains [5, 3, 8, 4].
Sorted sublist: [2]
Unsorted sublist: [5, 3, 8, 4]Second pass:
- Find the minimum element in the unsorted sublist [5, 3, 8, 4], which is 3.
- Swap 3 with the second element in the unsorted sublist, which is 5.
- The sorted sublist now contains the first two elements of the original list, which are 2 and 3. The unsorted sublist now contains [5, 8, 4].
Sorted sublist: [2, 3]
Unsorted sublist: [5, 8, 4]Third pass:
- Find the minimum element in the unsorted sublist [5, 8, 4], which is 4.
- Swap 4 with the third element in the unsorted sublist, which is 8.
- The sorted sublist now contains the first three elements of the original list, which are 2, 3, and 4. The unsorted sublist now contains [5, 8].
Sorted sublist: [2, 3, 4]
Unsorted sublist: [5, 8]Fourth pass:
- Find the minimum element in the unsorted sublist [5, 8], which is 5.
- Swap 5 with the fourth element in the unsorted sublist, which is 8.
- The sorted sublist now contains the first four elements of the original list, which are 2, 3, 4, and 5. The unsorted sublist now contains [8].
Sorted sublist: [2, 3, 4, 5]
Unsorted sublist: [8]Fifth pass:
- Find the minimum element in the unsorted sublist [8], which is 8.
- Swap 8 with the fifth element in the unsorted sublist, which is itself.
- The sorted sublist now contains all five elements of the original list, in sorted order. The unsorted sublist is now empty.
Sorted sublist: [2, 3, 4, 5, 8]
Unsorted sublist: []The algorithm is now complete, and the final sorted list is [2, 3, 4, 5, 8].
Example
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;
// Swap function
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of
// unsorted subarray
for (i = 0; i < n - 1; i++)
{
// Find the minimum element in
// unsorted array
min_idx = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[min_idx])
min_idx = j;
}
// Swap the found minimum element
// with the first element
if (min_idx != i)
swap(&arr[min_idx], &arr[i]);
}
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
{
cout << arr[i] << " ";
cout << endl;
}
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
The above program will output:
Sorted array:
11
12
22
25
64 Complexity Analysis of Selection Sort
The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This is because the algorithm uses nested loops to iterate over the array and compare elements.
The outer loop runs n-1 times, because the last element in the array will be in its correct position after n-1 passes. The inner loop runs n-1 times on the first pass, n-2 times on the second pass, and so on, until it runs 1 time on the last pass. On average, the inner loop runs (n-1)/2 times for each pass.
The total number of comparisons made by the algorithm can be expressed as the sum of the first n-1 integers, which is (n-1)(n)/2. This means that the time complexity of selection sort is O(n^2) in the worst case and in the average case.
The space complexity of selection sort is O(1), because the algorithm sorts the array in place and does not require any additional memory.
Where is the Selection sort algorithm used?
Selection sort is a simple sorting algorithm that is easy to implement and understand, but it is not very efficient for large datasets. Therefore, it is typically used for educational purposes or for sorting small datasets.
Selection sort can be useful in situations where the data is already mostly sorted or nearly sorted, because it performs well in these cases. It is also useful in situations where the cost of swapping elements is high, such as with linked lists, because it minimizes the number of swaps needed to sort the data.
Advantages of Selection Sort Algorithm:
- Simple and easy to implement: The algorithm is easy to understand and implement as it does not involve complex logic.
- Memory efficient: Selection sort is an in-place sorting algorithm, meaning that it sorts the elements in the input array itself, without using any extra memory.
- Stable: The algorithm maintains the relative order of equal elements, which means that it is stable.
Disadvantages of Selection Sort Algorithm:
- Slow for large datasets: Selection sort has a time complexity of O(n^2), which means that it is not efficient for large datasets. It requires a lot of time to sort large arrays.
- Not suitable for partially sorted arrays: If the input array is partially sorted, the algorithm still performs the same number of comparisons, which makes it inefficient.
- Inefficient for complex data structures: Selection sort is not efficient for complex data structures such as linked lists or trees, as it requires random access to the elements.
- Not optimal for parallel processing: The algorithm cannot be easily parallelized, which means that it is not optimal for parallel processing.
We hope this article helped you to understand Selection Sort Analysis in a very detailed way.
Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.
If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.