Write the algorithm for selection sort and explain its time and space complexity.

Question

Suresh Chand · Accepted Answer

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right. This algorithm is not suitable for large data sets as its average and worst-case complexities are of Ο(n2), where n is the number of items. Algorithm: Step 1: Start Step 2: Select the first element of the list (i.e., Element at first position in the list). Step 3: Compare the selected element with all the other elements in the list. Step 4: In every comparision, if any element is found smaller than the selected element (for Ascending order), then both are swapped. Step 5: Repeat the same procedure with element in the next position in the list till the entire list is sorted. Step 6: End Time Complexity: The inner loop executes for (n-1) times when i = 0, (n-2) times when i = 1, and so on. Time complexity = (n-1) + (n-2) + (n-3) + ................... + 2 + 1 = O(n2) There is no best-case linear time complexity for this algorithm, but the number of swap operations is reduced greatly. Space Complexity: The space complexity of the Selection sort is O(1). This is because we use only constant extra space such as: 2 variables to enable swapping of elements. One variable to keep track of the smallest element in an unsorted array. Hence, in terms of space complexity, the Selection sort is optimal as the memory requirements remain the same for every input.

Write the algorithm for selection sort and explain its time and space complexity.

Leave your Answer:

Hits Counter

Question

Write the algorithm for selection sort and explain its time and space complexity.

Leave your Answer: