Extra 5% OFF Use Code: OL05
Free Shipping over ₹999

Selection Sort

Selection Sort

Selection Sort is a simple sorting algorithm that divides the input array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements of the array. The algorithm repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the beginning (or end) of the sorted part. This process continues until the entire array is sorted.

Here’s how the Selection Sort algorithm works:

Algorithm:

  1. Divide the input array into two parts: the sorted part and the unsorted part.
  2. Find the smallest element in the unsorted part.
  3. Swap the smallest element with the first element of the unsorted part, effectively adding it to the sorted part.
  4. Repeat steps 2 and 3 for the remaining unsorted part of the array until the entire array is sorted.
#include <stdio.h>

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    int i, j, min_index;

    // Traverse through all array elements
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted part
        min_index = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }

        // Swap the found minimum element with the first element
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

Original array: 
64 25 12 22 11 
Sorted array: 
11 12 22 25 64 

Code Explanation

1. selectionSort Function

void selectionSort(int arr[], int n) {
    int i, j, min_index;
 
    // Traverse through all array elements
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted part
        min_index = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
 
        // Swap the found minimum element with the first element
        int temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}
  • Purpose: Sorts the array in ascending order using the Selection Sort algorithm.
  • How it works:
    1. The outer loop (i) iterates through the array from the first element to the second-to-last element.
    2. For each iteration of the outer loop:
      • The inner loop (j) finds the index of the smallest element in the unsorted part of the array (from i+1 to n-1).
      • The min_index variable keeps track of the index of the smallest element found.
    3. After finding the smallest element, it swaps it with the element at the current position (i).
    4. This process continues until the entire array is sorted.

2. printArray Function

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
  • Purpose: Prints the elements of the array.
  • How it works:
    • Iterates through the array and prints each element followed by a space.
    • After printing all elements, it adds a newline (\n) for better readability.

3. main Function

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}
  • Purpose: Drives the program.
  • How it works:
    1. Declares and initializes an array arr with unsorted integers.
    2. Calculates the size of the array (n) using sizeof(arr) / sizeof(arr[0]).
    3. Prints the original array using the printArray function.
    4. Calls the selectionSort function to sort the array.
    5. Prints the sorted array using the printArray function.

Key Points

  1. Selection Sort:
    • Time Complexity: O(n²) in all cases (worst, average, and best).
    • Space Complexity: O(1) (in-place sorting).
    • It is a simple but inefficient sorting algorithm for large datasets.
  2. How Selection Sort Works:
    • Divides the array into a sorted and an unsorted part.
    • Repeatedly selects the smallest element from the unsorted part and swaps it with the first element of the unsorted part.
    • The sorted part grows from left to right.
  3. Swapping:
    • A temporary variable (temp) is used to swap two elements.

    Leave a Reply

    Your email address will not be published.

    Need Help?