Skip to main content

Selection Sort


Selection sort is a simple sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. It is called selection sort because it repeatedly selects the smallest element of the unsorted portion of the array and moves it to its correct position in the sorted portion of the array.

The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This makes it inefficient for large arrays and it is not a good choice for sorting large datasets. However, selection sort is easy to understand and implement, and it is useful for educational purposes and for small arrays.

One of the advantages of selection sort is that it makes fewer swaps than other sorting algorithms such as bubble sort. This makes it more efficient in terms of memory writes, which can be important in some situations.

Another advantage of selection sort is that it is a stable sorting algorithm, meaning that it preserves the relative order of elements with the same value. This means that if there are multiple elements with the same value in the array, their order will not change after sorting.

In conclusion, selection sort is a simple sorting algorithm that is easy to understand and implement, but it is not a good choice for large arrays due to its poor time complexity. However, it has some advantages such as making fewer swaps and being a stable sorting algorithm.

ALGORITHM:

The algorithm works as follows:
  1. Start by dividing the array into two parts: the sorted portion, which starts as an empty list, and the unsorted portion, which is the entire array.
  2. Find the minimum element from the unsorted portion of the array.
  3. Swap the minimum element found in step 2 with the first element of the unsorted portion of the array.
  4. Move the boundary between the sorted and unsorted portions one element to the right.
  5. Repeat steps 2 to 4 until all elements of the array have been moved to the sorted portion.

PSEUDO CODE:

Here is the pseudo code for the selection sort algorithm:


In the above pseudo code, A is the list of elements to be sorted, n is the number of elements in the list, i and j are loop variables, and minIndex is the index of the minimum element found in the inner loop. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

PYTHON CODE:

Here is an implementation of the selection sort algorithm in Python:


In this implementation, arr is the list of elements to be sorted. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

JAVA CODE:

Here is the Java code for the Insertion Sort algorithm:


In this implementation, the arr array is passed to the selectionSort method, which sorts the array in place. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

C CODE:

Here is an implementation of the selection sort algorithm in C:


In this implementation, the arr array and its length n are passed to the selection_sort function, which sorts the array in place. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

C++ CODE:

Here is an implementation of the selection sort algorithm in C++:


In this implementation, the arr vector is passed to the selection sort function, which sorts the vector in place. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

JAVASCRIPT CODE:

Here is an implementation of the selection sort algorithm in JavaScript:


In this implementation, the arr array is passed to the selection Sort function, which sorts the array in place. The outer loop iterates n-1 times, and for each iteration, the inner loop finds the index of the minimum element in the unsorted portion of the list. If the minimum element is not already in its correct position, it is swapped with the first element of the unsorted portion. The boundary between the sorted and unsorted portions of the list is then moved one element to the right. The inner loop repeats until all elements have been moved to the sorted portion of the list.

Comments

Post a Comment

Popular posts from this blog

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5,...

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...