Selection Sort In C, C++, Java, Python With Examples

Q: How does selection sort work?

Selection Sort works by iteratively finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted region.

Q: Can selection sort be used for sorting linked lists?

Yes, Selection Sort can be adapted for sorting linked lists. However, the swapping operation is not as straightforward in linked lists as it is in arrays.

Q: Is selection sort stable?

No, Selection Sort is not a stable sorting algorithm. A stable sorting algorithm maintains the relative order of equal elements in the sorted output, which Selection Sort may not guarantee.

Q: Does selection sort require additional memory space?

Selection Sort is an in-place sorting algorithm, meaning it doesn't require additional memory space for sorting. It sorts the elements within the given array without using extra storage.

Q: What is the main advantage of selection sort?

The main advantage of Selection Sort is its simplicity. It is easy to understand and implement, making it a suitable choice for educational purposes or small datasets.

Selection Sort in C stands out as a straightforward and effective sorting algorithm. Its methodology involves iteratively pinpointing the smallest (or largest) element within the unsorted section of the list and relocating it to the sorted section.

Selection Sort in C: Selection sort in C is a sorting algorithm employed in data structures to arrange a list or an array in a particular order, typically ascending or descending. It works by selecting the lowest (or largest) piece from the unsorted component of the data structure and shifting it to the sorted section iteratively.

This operation is repeated until the data structure is completely sorted. Although selection sort in C is well-known for its ease of use, it may not be as efficient as more complicated sorting algorithms for huge datasets. The “C++ with DSA Course” offered by Physics Wallah promises to empower participants with a comprehensive understanding of C++ programming, emphasizing the application of these skills in the realm of game development.

What is Selection Sort in Data Structure?

Selection sort is a sorting algorithm that operates by repeatedly selecting an element from the unsorted portion of a dataset and comparing it to all other elements. The selected element is then placed at its correct position in the sorted set of elements.

To illustrate this concept, consider a real-world example where students are standing in a school assembly in an unordered manner and need to arrange themselves from shortest to tallest. The algorithm works by selecting the first student and comparing their height to others, replacing them with a shorter student until the shortest one is found.

This process is repeated for each position in the assembly, ensuring that the students are arranged in ascending order of height. The logic and conditions applied during this process constitute the implementation of the selection sort algorithm in C.

Also read: Analysis of Algorithm in Data Structure

How Does the Selection Sort Algorithm Work?

The selection sort algorithm divides the input list into two sections: sorted and unsorted. The sorted section starts out empty, but the unsorted section has all of the items. The method takes the smallest (or largest, depending on the desired order) element from the unsorted section and pushes it to the end of the sorted part each time. This is repeated until the full list has been sorted. Here’s a detailed breakdown of how the Selection Sort algorithm works:

1) Initialization:

The algorithm starts with an empty sorted list and the entire unsorted list.
Set the current element as the minimum.

2) Find the Minimum:

Iterate through the unsorted part of the list to find the minimum element.
Compare each element with the current minimum.
If a smaller element is found, update the minimum.

3) Swap with First Unsorted Element:

Once the minimum element in the unsorted part is found, swap it with the first element in the unsorted part.
The swapped element is now considered part of the sorted list.

4) Expand the Sorted Part:

Expand the sorted part by considering the first element of the unsorted part as the next element to be sorted.

5) Repeat:

Repeat steps 2 to 4 until the entire list is sorted.
The unsorted part becomes smaller with each iteration, and the sorted part grows.

6) Completion:

When the unsorted part becomes empty, the entire list is sorted.

Suppose we have an unsorted list: [64, 25, 12, 22, 11]

Step 1: The minimum is initially set to the first element, which is 64.

Step 2: Iterate through the unsorted part and find that 11 is the minimum.

Step 3: Swap 11 with the first element, so the list becomes [11, 25, 12, 22, 64].

Step 4: Expand the sorted part, and now consider the second element (25) as the minimum.

Step 5: Repeat the process until the list is sorted.

After multiple iterations, the final sorted list is [11, 12, 22, 25, 64]. This demonstrates how the Selection Sort algorithm gradually builds a sorted list by selecting the smallest element in each iteration.

Also read: What is Dev C++? Online, Download, Compiler, Examples

Selection Sort in C Using Function

Here is the selection sort in C using function example:

#include <stdio.h>

// Function to perform selection sort on an array

void selectionSort(int arr[], int n) {

int i, j, minIndex, temp;

for (i = 0; i < n – 1; i++) {

minIndex = i;

// Check elements in the unsorted part to find the minimum

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {

// Update the minimum index if a smaller element is found

minIndex = j;

}

// Swap the found minimum element with the first element

temp = arr[minIndex];

arr[minIndex] = arr[i];

arr[i] = temp;

}

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr) / sizeof(arr[0]);

printf(“Original array: “);

for (int i = 0; i < n; i++) {

printf(“%d “, arr[i]);

}

printf(“\n”);

// Perform selection sort using the function

selectionSort(arr, n);

printf(“Sorted array: “);

for (int i = 0; i < n; i++) {

printf(“%d “, arr[i]);

}

printf(“\n”);

return 0;

}

Selection Sort in C Without Function

To implement Selection Sort in C without using a function, follow these steps:

Declare an array to store the elements.
Use nested loops for iteration.
In the outer loop, iterate through each element.
In the inner loop, find the smallest element in the unsorted part of the array.
Swap the found smallest element with the first element of the unsorted part.
Repeat until the entire array is sorted.

Selection Sort Algorithm

Selection Sort is an easy sorting method that splits an array into sorted and unsorted regions. The method repeatedly chooses the smallest (or largest, depending on the order) element from the unsorted region and swaps it with the unsorted region’s initial element. This is continued until the full array has been sorted.

Example:

Consider the array [64, 25, 12, 22, 11]:

Initial state (unsorted region): [64, 25, 12, 22, 11]
After the first iteration: [11, 25, 12, 22, 64]
After the second iteration: [11, 12, 25, 22, 64]
After the third iteration: [11, 12, 22, 25, 64]
After the fourth iteration: [11, 12, 22, 25, 64]

The array is now sorted in ascending order.

Selection Sort in Java

Selection sort is a straightforward sorting method that splits the input array into sorted and unsorted regions. The Selection sort algorithm is explained in detail below:

1) Divide into Sorted and Unsorted Regions:

Initially, the entire array is considered as the unsorted region.
The sorted area is empty.

2) Find the Minimum Element:

Iterate through the unsorted area to find the minimum element.

3) Swap with First Element of Unsorted Region:

Swap the found minimum element with the first element of the unsorted region.

4) Expand the Sorted Region:

Move the boundary between the sorted and unsorted regions, one element to the right.

5) Repeat:

Repeat steps 2-4 until the entire array is sorted.

Recommended Technical Course

Selection Sort in Python

Below is an explanation of the Selection Sort algorithm in Python:

def selection_sort(arr):

n = len(arr)

# Traverse through all array elements

for i in range(n):

# Assume the first element of the unsorted region is the minimum

min_index = i

# Find the minimum element in the unsorted region

for j in range(i + 1, n):

if arr[j] < arr[min_index]:

min_index = j

# Swap the found minimum element with the first element

arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage:

my_list = [64, 25, 12, 22, 11]

selection_sort(my_list)

print(“Sorted array:”, my_list)

Explanation:

If a smaller element is found, the min_index is updated.
After finding the minimum element in the unsorted region, a swap is performed between the current element (arr[i]) and the minimum element (arr[min_index]).
The process is repeated until the entire array is sorted.
The example demonstrates using the selection_sort function to sort an array (my_list). The sorted array is then printed.

Selection Sort in C++

Selection Sort in C++ is a straightforward sorting algorithm. It repeatedly selects the smallest (or largest) element from an unsorted list and places it at the beginning.

#include <iostream>

// Function to perform selection sort on an array

void selectionSort(int arr[], int n) {

int i, j, minIndex, temp;

for (i = 0; i < n – 1; i++) {

minIndex = i;

// Check elements in the unsorted part to find the minimum

for (j = i + 1; j < n; j++) {

if (arr[j] < arr[minIndex]) {

// Update the minimum index if a smaller element is found

minIndex = j;

}

// Swap the found minimum element with the first element

temp = arr[minIndex];

arr[minIndex] = arr[i];

arr[i] = temp;

}

// Function to print an array

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

std::cout << arr[i] << ” “;

}

std::cout << std::endl;

}

// Driver program to test the selectionSort function

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr) / sizeof(arr[0]);

std::cout << “Original array: “;

printArray(arr, n);

// Perform selection sort

selectionSort(arr, n);

std::cout << “Sorted array: “;

printArray(arr, n);

return 0;

}

This C++ program follows a similar structure to the C version but uses cout and endl for output. The selection sort function performs the selection sort, and the printArray function prints the array elements. The main function demonstrates the usage of these functions on an example array. When you run this program, you’ll see the original and sorted arrays printed in the console.

Complexity of Selection Sort Algorithm

The time complexity of the selection sort algorithm is determined by its nested loops:

The selection sort algorithm consists of two nested loops.
It has a temporal complexity of O(n2) due to the two nested loops, where ‘n’ is the number of elements in the array.
The time complexity is O(n2) in the best-case scenario, where the array is already sorted.
In the Average Case Complexity, when the array elements are in a jumbled order, the time complexity remains O(n^2).
Worst-Case Scenario when array members must be sorted in reverse order, complexity arises. The worst-case time complexity is O(n2) if the array is in descending order and needs to be sorted in ascending order.

The space complexity of the selection sort algorithm is determined by its in-place nature:

Selection sort is an in-place algorithm, meaning it performs all computations within the original array and doesn’t require additional memory space.
It does not use any other arrays or data structures for sorting.
As a result, the space complexity of the selection sort algorithm is O(1), indicating constant space usage.

Also read: 6 Benefits of Using C and C++ for Game Development

Advantages of Selection Sort Algorithm

Here are some advantages of the Selection Sort algorithm:

Simplicity: Selection Sort is one of the simplest sorting algorithms to understand and implement. It involves a straightforward process of repeatedly selecting the minimum (or maximum) element and swapping it with the first element of the unsorted region.
In-Place Sorting: Selection Sort performs in-place sorting, meaning it doesn’t require additional memory space proportional to the input size. It only needs a constant amount of extra memory.
Minimizes Swaps: The algorithm minimizes the number of swaps compared to other sorting algorithms. It swaps elements only when it finds the minimum (or maximum) element, reducing the overall number of exchanges.
Good for Small Datasets: In situations where the dataset is small or the overhead of more complex algorithms outweighs their benefits, Selection Sort can be a reasonable choice due to its simplicity and ease of implementation.
Stable Algorithm: Selection Sort is a stable sorting algorithm. A stable sort preserves the relative order of equal elements in the sorted output.
Adaptive: The performance of Selection Sort can be adaptive in certain scenarios. If the dataset is partially sorted or nearly sorted, the number of comparisons may be reduced, making it more efficient in those cases.

Selection Sort in C Conclusion

The selection sort algorithm, implemented in C, C++, Java, and Python, offers a straightforward yet effective approach to sorting elements in an array. Through the provided examples in each programming language, we observe the consistent logic behind selection sort, emphasizing its simplicity and ease of implementation.

Despite its simplicity, selection sort exhibits certain limitations, particularly its time complexity of O(n^2), making it less efficient than some advanced sorting algorithms for large datasets. However, for small datasets or scenarios where simplicity is prioritized, selection sort remains a viable option.

The code examples presented in C, C++, Java, and Python showcase the adaptability of selection sort across different programming languages. Whether leveraging pointers in C, employing object-oriented concepts in C++, utilizing the rich libraries in Java, or benefiting from Python’s readability, the essence of the selection sort algorithm remains consistent.

Prospective learners are invited to embark on this educational journey to hone their programming skills, particularly in the context of game development. Whether beginners or experienced programmers, the “C++ with DSA Course” offered by Physics Wallah aims to cater to a diverse audience seeking to merge coding expertise with the dynamic world of game creation.

Also read: Java vs C++ Performance, Speed, Efficiency, and More!

FAQs

How does selection sort work?