What Is Selection Sort in Data Structure With Example?

//

Angela Bailey

What Is Selection Sort in Data Structure With Example?

Selection sort is a simple comparison-based sorting algorithm. It works by dividing the input array into two parts: sorted and unsorted.

The sorted part is initially empty, while the unsorted part contains the entire array. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted part and moves it to the sorted part.

The selection sort algorithm can be explained with a simple example:

Example:

Consider an array of integers: [5, 2, 8, 3, 1]. We will sort this array using selection sort.

Step 1:

  • Set the first element as the minimum value.
  • Compare it with all other elements in the array.
  • If any element is smaller than the minimum value, update the minimum value.

In our example, we start with 5 as the minimum value. We compare it with 2, 8, 3, and 1. Since 1 is smaller than 5, we update our minimum value to 1.

Step 2:

  • Swap the minimum value with the first element of the unsorted part of the array.

In our example, we swap 5 with 1 since they are at different positions in the array.

Step 3:

  • Maintain a pointer to keep track of how many elements are already sorted.

In our example, after swapping, we have one element (1) in the sorted part of the array.

Step 4:

  • Repeat steps 1-3 for the remaining unsorted part of the array.

In our example, we repeat steps 1-3 for [2, 8, 3]. After this iteration, we have two elements (1 and 2) in the sorted part of the array.

Step 5:

  • Continue repeating steps 1-4 until all elements are sorted.

In our example, after repeating steps 1-4 for [8, 3] and [8], we have all the elements (1, 2, 3, 5, and 8) in sorted order.

The final sorted array is [1, 2, 3, 5, 8].

The time complexity of selection sort is O(n^2), where n is the number of elements in the input array. This makes it inefficient for sorting large arrays. However, selection sort has some advantages like simplicity and suitability for small arrays or partially sorted arrays.

In conclusion, selection sort is a basic sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted part of an array and placing it in its correct position in the sorted part. While it may not be efficient for large datasets, understanding how selection sort works can help you grasp other more complex sorting algorithms.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy