How Do You Create a Selection Sort in Data Structure?

How Do You Create a Selection Sort in Data Structure?

Sorting is an essential operation in data structures that arranges elements in a specific order. One popular sorting algorithm is the selection sort.

In this tutorial, we will explore how to create a selection sort using a step-by-step approach.

Understanding Selection Sort

Selection sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: sorted and unsorted.

The sorted part is initially empty, while the unsorted part contains all the elements.

The algorithm repeatedly selects the smallest element from the unsorted part and moves it to the end of the sorted part. This process continues until the unsorted part becomes empty, and all elements are sorted.

Implementation Steps:

Step 1: Find the minimum element

To begin with, we need to find the minimum element in the unsorted part of the list. We can achieve this by iterating through each element and keeping track of the minimum value encountered so far.

function findMin(arr) {
  let minIndex = 0;
  let minValue = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minIndex = i;
      minValue = arr[i];
    }
  }
  
  return minIndex;
}

Step 2: Swap with first unsorted element

Once we have found the minimum element, we swap it with the first unsorted element. This ensures that the minimum element is now at its correct position in the sorted part of the list.

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

Step 3: Repeat until the list is sorted

We repeat steps 1 and 2 until the entire list becomes sorted. At each iteration, the size of the unsorted part decreases by one, while the sorted part grows from left to right.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = findMin(arr.slice(i)) + i;
    swap(arr, i, minIndex);
  }
  
  return arr;
}

Example Usage:

Let's see the selection sort in action with an example:

const unsortedArray = [5, 9, 2, -3, 10];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // Output: [-3, 2, 5, 9, 10]

Conclusion

Selection sort is a straightforward yet effective algorithm for sorting elements in a data structure. By iteratively selecting and swapping elements based on their values, we can achieve a sorted list.

Remember to use this algorithm when dealing with small or partially sorted lists.

Now that you have learned how to create a selection sort in data structure using JavaScript, feel free to experiment and apply this knowledge to your own projects.