Selection sort
1.Problem:
Sort the given array using Selection Sort in ascending order.
Input:
arr = {29, 10, 14, 37, 13}
Output:
10 13 14 29 37
Algorithm:
1. Start from the first element of the array.
2. Assume it is the minimum in the unsorted part of the array.
3. Compare this minimum with the rest of the elements.
4. If you find a smaller element, update the minimum index.
5. After finishing one pass, swap the first element with the minimum.
6. Repeat this process for all elements until the array is sorted.
Pseudocode:
SelectionSort(arr, n)
for i = 0 to n - 2
minIndex = i
for j = i + 1 to n - 1
if arr[j] < arr[minIndex]
minIndex = j
swap arr[i] and arr[minIndex]
Program:
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
// Find the index of the minimum element in the unsorted part
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
// Swap the found minimum element with the first element
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
2.Problem:
Sort the given array in descending order using Selection Sort.
Input:
arr = {12, 7, 25, 3, 18}
Output:
25 18 12 7 3
Algorithm:
1. Start from the first element of the array.
2. Assume it is the maximum in the unsorted part of the array.
3. Compare this maximum with the rest of the elements.
4. If you find a bigger element, update the max index.
5. Swap the current element with the found maximum.
6. Repeat for all positions.
Pseudocode:
SelectionSortDescending(arr, n)
for i = 0 to n - 2
maxIndex = i
for j = i + 1 to n - 1
if arr[j] > arr[maxIndex]
maxIndex = j
swap arr[i] and arr[maxIndex]
Program:
#include <stdio.h>
void selectionSortDescending(int arr[], int n) {
int i, j, maxIndex, temp;
for (i = 0; i < n - 1; i++) {
maxIndex = i;
// Find the index of the maximum element in the unsorted part
for (j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
// Swap the found maximum element with the first element
temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
int main() {
int arr[] = {12, 7, 25, 3, 18};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSortDescending(arr, n);
printf("Sorted array in descending order: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
3.Find the k-th Smallest Element:
Problem:
Find the 3rd smallest element in the array using Selection Sort.
Input:
arr = {50, 10, 60, 30, 20}, k = 3
Sorted Array:10 20 30 50 60
Output:
3rd smallest element = 30
Algorithm:
1. Perform Selection Sort to sort the array in ascending order.
2. After sorting, the k-th smallest element will be at index k-1 (since indexing starts at 0).
3. Return the element at index k-1.
Pseudocode:
FindKthSmallest(arr, n, k)
for i = 0 to k - 1
minIndex = i
for j = i + 1 to n - 1
if arr[j] < arr[minIndex]
minIndex = j
swap arr[i] and arr[minIndex]
return arr[k - 1]
Note: We sort only up to the k-th position (partial selection sort) for efficiency.
Program:
#include <stdio.h>
int findKthSmallest(int arr[], int n, int k) {
int i, j, minIndex, temp;
// Partial selection sort - only first k elements sorted
for (i = 0; i < k; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
// Swap
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
// Return k-th smallest element
return arr[k - 1];
int main() {
int arr[] = {50, 10, 60, 30, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int result = findKthSmallest(arr, n, k);
printf("%dth smallest element = %d\n", k, result);
return 0;
4.Problem:
Count Swaps:
Sort the array and count the number of swaps made during Selection Sort.
Input:
arr = {3, 2, 1}
Output:
Sorted array: 1 2 3
Total swaps: 2
Algorithm:
1. Use the selection sort algorithm to sort the array in ascending order.
2. Every time a swap is performed, increase the swap counter by 1.
3. At the end, print the sorted array and the total number of swaps.
Pseudocode:
SelectionSortWithSwaps(arr, n)
swapCount = 0
for i = 0 to n - 2
minIndex = i
for j = i + 1 to n - 1
if arr[j] < arr[minIndex]
minIndex = j
if minIndex != i
swap arr[i] and arr[minIndex]
swapCount = swapCount + 1
return swapCount
Program:
#include <stdio.h>
int selectionSortWithSwaps(int arr[], int n) {
int i, j, minIndex, temp;
int swapCount = 0;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
if (minIndex != i) {
// Perform swap
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
swapCount++;
return swapCount;
int main() {
int arr[] = {3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int swaps = selectionSortWithSwaps(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
printf("\nTotal swaps: %d\n", swaps);
return 0;
}
5.Problem:
Sort Only Even Numbers:
Sort only the even numbers in the array using Selection Sort. Keep odd numbers in the same position.
Input:
arr = {7, 4, 6, 3, 2}
Even Numbers: 4, 6, 2 → Sorted → 2, 4, 6
Odd Positions Stay Same
Output:
72436
Algorithm:
1. Create a separate list of even numbers and store their indices.
2. Sort the even numbers using selection sort.
3. Place the sorted even numbers back into their original indices.
4. Leave odd numbers untouched.
Pseudocode:
SortOnlyEvens(arr, n)
evenValues = []
evenIndices = []
for i = 0 to n-1
if arr[i] % 2 == 0
append arr[i] to evenValues
append i to evenIndices
// Selection Sort on evenValues
for i = 0 to len(evenValues) - 2
minIndex = i
for j = i + 1 to len(evenValues) - 1
if evenValues[j] < evenValues[minIndex]
minIndex = j
swap evenValues[i] and evenValues[minIndex]
for i = 0 to len(evenIndices) - 1
arr[evenIndices[i]] = evenValues[i]
Program:
#include <stdio.h>
void sortOnlyEvens(int arr[], int n) {
int evenValues[100], evenIndices[100];
int count = 0;
// Step 1: Collect even numbers and their indices
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) {
evenValues[count] = arr[i];
evenIndices[count] = i;
count++;
}
// Step 2: Selection sort on evenValues
for (int i = 0; i < count - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < count; j++) {
if (evenValues[j] < evenValues[minIndex]) {
minIndex = j;
// Swap
int temp = evenValues[i];
evenValues[i] = evenValues[minIndex];
evenValues[minIndex] = temp;
// Step 3: Place sorted even values back to original positions
for (int i = 0; i < count; i++) {
arr[evenIndices[i]] = evenValues[i];
int main() {
int arr[] = {7, 4, 6, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
sortOnlyEvens(arr, n);
printf("Output: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
6.Problem:
Sort Array of Characters:
Input a character array and sort alphabetically.
Input:
arr = {'d', 'a', 'c', 'b'}
Algorithm:
1. Use selection sort to sort characters in ascending (alphabetical) order.
2. Compare characters based on their ASCII values.
3. Swap when a smaller character is found.
Pseudocode:
SelectionSortChar(arr, n)
for i = 0 to n - 2
minIndex = i
for j = i + 1 to n - 1
if arr[j] < arr[minIndex]
minIndex = j
swap arr[i] and arr[minIndex]
Program:
#include <stdio.h>
void selectionSortChar(char arr[], int n) {
int i, j, minIndex;
char temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
// Swap
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
int main() {
char arr[] = {'d', 'a', 'c', 'b'};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSortChar(arr, n);
printf("Sorted characters: ");
for (int i = 0; i < n; i++) {
printf("%c ", arr[i]);
return 0;
