Subject Name
Topperworld.in
Selection Sort
Selection Sort is a simple comparison-based sorting algorithm. It works
by repeatedly selecting the smallest (or largest, depending on the order)
element from the unsorted part of the array and swapping it with the first
element of the unsorted part. This process continues until the entire array
is sorted. While Selection Sort is not the most efficient sorting algorithm,
it's easy to understand and implement.
The array is passed through (n-1) times and the smallest element
is placed in its respective position in the array as detailed below:
Pass 1: Find the location j of the smallest element in the array x [0], x[1],
. . . . x[n-1],
and then interchange x[j] with x[0]. Then x[0] is sorted.
Pass 2: Leave the first element and find the location j of the smallest
element in the
sub-array x[1], x[2], . . . . x[n-1], and then interchange x[1] with x[j].
Then
x[0], x[1] are sorted.
Pass 3: Leave the first two elements and find the location j of the smallest
element in
the sub-array x[2], x[3], . . . . x[n-1], and then interchange x[2] with x[j].
Then x[0], x[1], x[2] are sorted.
Pass (n-1): Find the location j of the smaller of the elements x[n-2] and
x[n-1], and then interchange x[j] and x[n-2]. Then x[0], x[1], . . . . x[n-
2] are sorted. Of course, during this pass x[n-1] will be the biggest element
and so the entire array is sorted.
Subject Name
1 2 3 4 5 6 7 8 9 Remarks
65 70 75 80 50 60 55 85 45 find the first smallest element
i j swap a[i] & a[j]
45 70 75 80 50 60 55 85 65 find the second smallest element
i j swap a[i] and a[j]
45 50 75 80 70 60 55 85 65 Find the third smallest element
i j swap a[i] and a[j]
45 50 55 80 70 60 75 85 65 Find the fourth smallest element
i j swap a[i] and a[j]
45 50 55 60 70 80 75 85 65 Find the fifth smallest element
i j swap a[i] and a[j]
45 50 55 60 65 80 75 85 70 Find the sixth smallest element
i j swap a[i] and a[j]
45 50 55 60 65 70 75 85 80 Find the seventh smallest element
i j swap a[i] and a[j]
45 50 55 60 65 70 75 85 80 Find the eighth smallest element
i J swap a[i] and a[j]
45 50 55 60 65 70 75 80 85 The outer loop ends.
Algorithm:
Algorithm:void SelectionSort (int a[], int n)
{
int i,j, temp, min;
for (i=0; i<n-1; i++)
{
min = i;
for (j=i+1; j<n; j++)
if (a[j] < a[min])
{
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
Subject Name
1. Start with the first element as the current minimum.
2. Iterate through the unsorted portion of the array (starting from the
second element), and find the smallest element.
3. Swap the smallest element found with the first element of the
unsorted portion.
4. Move the boundary between the sorted and unsorted portions one
position to the right.
5. Repeat steps 2-4 until the entire array is sorted.
Java Implementation:
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int 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 part
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
Subject Name
System.out.print(num + " ");
}
}
}
➔Complexity Analysis:
• Time Complexity: Selection Sort has a time complexity of O(n^2),
where n is the number of elements in the array. This is because for
each element in the array, you need to find the smallest element in
the remaining unsorted portion, which takes approximately n/2
comparisons on average.
• Space Complexity: Selection Sort has a space complexity of O(1),
as it only requires a constant amount of additional memory to
perform the swaps and keep track of indices.
Overall, while Selection Sort is easy to understand, it's not efficient for large
arrays due to its quadratic time complexity. More advanced sorting
algorithms like Merge Sort or Quick Sort are generally preferred for larger
datasets
