selection Sort Algorithm

The Selection Sort Linked List Algorithm is an efficient sorting technique that operates on a linked list data structure. This algorithm sorts the elements in a linked list by iteratively selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion. The main idea behind this algorithm is to divide the list into two parts: the sorted part, which starts as an empty list, and the unsorted part. The algorithm repeatedly selects the minimum (or maximum) 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 the sorted part contains all the elements in the desired order. In the context of a linked list, the selection sort algorithm involves updating the pointers of the nodes to rearrange the elements, rather than swapping the elements themselves. The algorithm starts by initializing a pointer to the current minimum (or maximum) element and traverses the list, comparing each element with the current minimum. If a smaller (or larger) element is found, the pointer is updated to point to the new minimum (or maximum) element. Once the end of the list is reached, the minimum (or maximum) element is moved to the sorted portion by updating the appropriate pointers. This process is repeated until the entire list is sorted. While the selection sort algorithm has a time complexity of O(n^2) for both average and worst-case scenarios, which is not optimal compared to other sorting algorithms, it still proves to be a simple and intuitive method for sorting linked lists.
/* The selection sort algorithm sorts an array by repeatedly finding the minimum element
 *(considering ascending order) from unsorted part and putting it at the beginning. The
 *algorithm maintains two subarrays in a given array.
 *1) The subarray which is already sorted.
 *2) Remaining subarray which is unsorted.
 *
 *In every iteration of selection sort, the minimum element (considering ascending order)
 *from the unsorted subarray is picked and moved to the sorted subarray.
 */

function selectionSort (items) {
  var length = items.length
  for (var i = 0; i < length - 1; i++) {
    // Number of passes
    var min = i // min holds the current minimum number position for each pass; i holds the Initial min number
    for (var j = i + 1; j < length; j++) { // Note that j = i + 1 as we only need to go through unsorted array
      if (items[j] < items[min]) { // Compare the numbers
        min = j // Change the current min number position if a smaller num is found
      }
    }
    if (min !== i) {
      // After each pass, if the current min num != initial min num, exchange the position.
      // Swap the numbers
      [items[i], items[min]] = [items[min], [items[i]]]
    }
  }
}

// Implementation of Selection Sort

var ar = [5, 6, 7, 8, 1, 2, 12, 14]
// Array before Sort
console.log(ar)
selectionSort(ar)
// Array after sort
console.log(ar)

LANGUAGE:

DARK MODE: