Selection sort algorithm is a simple and efficient sorting algorithm that is commonly used for sorting small data sets. It works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the sorted portion of the array. In this article, we will explain in detail what selection search algorithm is, how it works, and provide examples of implementing the algorithm using Python code.

What is Selection Search Algorithm?

Selection sort algorithm is a sorting algorithm that works by repeatedly finding the smallest element from the unsorted portion of the array and placing it at the beginning of the sorted portion of the array. It is called selection sort because it selects the smallest element from the unsorted portion and places it at the beginning of the sorted portion. The algorithm works in-place, meaning that it sorts the array by modifying the array itself, without the need for additional memory.

Selection sort algorithm has a time complexity of O(n^2), which means that it is not efficient for sorting large data sets. However, it is efficient for sorting small data sets, and it has the advantage of being simple and easy to understand.

How Selection Sort Algorithm Works?

Selection sort algorithm works by dividing the array into two portions, sorted and unsorted. Initially, the sorted portion is empty, and the unsorted portion contains all the elements of the array. The algorithm then searches for the minimum element from the unsorted portion and swaps it with the first element of the unsorted portion. This places the minimum element at the beginning of the sorted portion and reduces the size of the unsorted portion by one element. The algorithm then repeats this process until the entire array is sorted.

The following are the steps involved in implementing selection sort algorithm:

1. Set the first element of the array as the minimum element.
2. Compare the minimum element with the next element in the array.
3. If the next element is smaller than the minimum element, set the next element as the minimum element.
4. Repeat steps 2 and 3 until the end of the array is reached.
5. If the minimum element is not the first element of the array, swap the minimum element with the first element of the array.
6. Repeat steps 1 to 5 until the entire array is sorted.

Selection Sort Algorithm Implementation in Python

The following is an example of implementing selection sort algorithm using Python:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

The above code defines a function named selection_sort that takes an array as input and returns the sorted array. The function iterates over the array using a for loop and selects the minimum element from the unsorted portion of the array using another for loop. It then swaps the minimum element with the first element of the unsorted portion, thereby placing the minimum element at the beginning of the sorted portion. The function repeats this process until the entire array is sorted.

Example of Selection Sort Algorithm Implementation

The following is an example of implementing selection sort algorithm using Python:

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)

The above code creates an array of integers and passes it to the selection_sort function defined earlier. It then prints the sorted array.

The output of the above code will be:

Sorted array is: [11, 12, 22, 25, 64]

The above code sorts the array in ascending order using selection sort algorithm and prints the sorted array.

Advantages and Disadvantages of Selection Sort Algorithm

Selection sort algorithm has the following advantages:

• Simple and easy to understand
• In-place sorting algorithm, meaning that it sorts the array without requiring additional memory
• Works efficiently for small data sets

However, selection sort algorithm has the following disadvantages:

• Not efficient for large data sets due to its time complexity of O(n^2)
• Performs poorly when the data is already partially sorted
• Not stable, meaning that it does not preserve the order of equal elements in the array

Conclusion

Selection sort algorithm is a simple and efficient sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the sorted portion of the array. It is a popular algorithm for sorting small data sets due to its simplicity and efficiency. In this article, we have explained in detail what selection sort algorithm is, how it works, and provided examples of implementing the algorithm using Python code.

FAQs

1. What is the time complexity of selection sort algorithm?

• The time complexity of selection sort algorithm is O(n^2).

2. What is the space complexity of selection sort algorithm?

• The space complexity of selection sort algorithm is O(1).

3. Is selection sort algorithm stable?

• No, selection sort algorithm is not stable.

4. What is the best use case for selection sort algorithm?

• Selection sort algorithm is efficient for sorting small data sets.

5. Can selection sort algorithm be used for sorting large data sets?

• No, selection sort algorithm is not efficient for sorting large data sets.

For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear