Selection Sort in Design and Analysis of Algorithms (DAA)

Java Program for Selection Sort

public class SelectionSort
{
    static void selectionSort(int arr[])
    {
        int n = arr.length;

        for(int i = 0; i < n - 1; i++)
        {
            int min = i;

            for(int j = i + 1; j < n; j++)
            {
                if(arr[j] < arr[min])
                {
                    min = j;
                }
            }

            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

    public static void main(String args[])
    {
        int arr[] = {64,25,12,22,11};

        selectionSort(arr);

        System.out.println("Sorted Array:");

        for(int value : arr)
        {
            System.out.print(value + " ");
        }
    }
}

Python Program for Selection Sort

arr = [64, 25, 12, 22, 11]

n = len(arr)

for i in range(n):

    min_index = i

    for j in range(i + 1, n):

        if arr[j] < arr[min_index]:
            min_index = j

    arr[i], arr[min_index] = arr[min_index], arr[i]

print("Sorted Array:")

for value in arr:
    print(value, end=" ")

PHP Program for Selection Sort

Sorted Array: 11 12 22 25 64 

Time Complexity Analysis of Selection Sort

Time Complexity is the amount of time taken by an algorithm to execute with respect to the size of the input. Selection Sort always searches the entire unsorted portion of the array to find the smallest element. Therefore, the number of comparisons remains almost the same irrespective of whether the array is already sorted or completely unsorted.

Why is the Time Complexity O(n²)?

For an array of n elements, Selection Sort performs:

(n − 1) + (n − 2) + (n − 3) + ... + 2 + 1

Total comparisons:

n(n − 1) / 2

Therefore, the overall time complexity is:

O(n²)

Space Complexity

Selection Sort requires only one temporary variable for swapping elements. Therefore, the extra memory required does not depend on the input size.

Number of Comparisons

Number of Swaps

Unlike Bubble Sort, Selection Sort performs at most one swap during each pass. Hence, the maximum number of swaps is:

n − 1

Advantages of Selection Sort

• Simple and easy to understand.
• Easy to implement.
• Requires only O(1) extra memory.
• Performs fewer swaps than Bubble Sort.
• Suitable for small datasets.
• Useful for teaching sorting concepts.
• Works well when memory is limited.

Disadvantages of Selection Sort

• Time complexity is O(n²).
• Not suitable for large datasets.
• Not a stable sorting algorithm.
• Not adaptive.
• Performs unnecessary comparisons even for sorted arrays.

Applications of Selection Sort

Although Selection Sort is not commonly used for large-scale applications, it is useful in the following situations.

• Educational purposes.
• Sorting small datasets.
• Embedded systems with limited memory.
• When swapping is expensive.
• Interview and competitive programming practice.

Selection Sort vs Bubble Sort

Selection Sort vs Insertion Sort

Complexity Summary

Solved Example

Sort the following array in ascending order using Selection Sort.

29    10    14    37    13

Final Sorted Array: 10 13 14 29 37

AKTU Previous Year Examination Questions

1. Explain the Selection Sort algorithm with a suitable example.
2. Write the algorithm and analyze the time complexity of Selection Sort.
3. Differentiate between Selection Sort and Bubble Sort.
4. Why is Selection Sort called an in-place sorting algorithm?
5. Perform Selection Sort on a given array.
6. Explain the Best, Average and Worst Case complexities of Selection Sort.
7. Why is Selection Sort not considered a stable sorting algorithm?

Viva Questions

1. What is Selection Sort?
2. Why is it called Selection Sort?
3. Is Selection Sort an in-place sorting algorithm?
4. Is Selection Sort stable?
5. What is the Best Case Time Complexity?
6. What is the Worst Case Time Complexity?
7. How many passes are required for n elements?
8. What is the maximum number of swaps?
9. Why is Selection Sort not adaptive?
10. Which sorting algorithm performs fewer swaps—Bubble Sort or Selection Sort?

Interview Questions

1. Explain the working of Selection Sort.
2. What is the difference between Selection Sort and Insertion Sort?
3. Why is Selection Sort inefficient for large datasets?
4. Can Selection Sort be made stable? Explain.
5. Where is Selection Sort practically used?
6. What are the advantages of Selection Sort over Bubble Sort?
7. Which sorting algorithm would you choose for nearly sorted data?
8. What is the space complexity of Selection Sort?
9. How many comparisons are performed in Selection Sort?
10. Is Selection Sort a divide-and-conquer algorithm? Why?

Multiple Choice Questions (MCQs)

Practice Questions

1. Sort the array 45, 12, 89, 34, 23 using Selection Sort.
2. Write the Selection Sort algorithm in C.
3. Explain the dry run of Selection Sort using an example.
4. Differentiate Selection Sort and Bubble Sort.
5. Derive the time complexity of Selection Sort.
6. Explain why Selection Sort is not adaptive.
7. Write a Java program for Selection Sort.
8. Implement Selection Sort in Python.

Key Takeaways

• Selection Sort repeatedly selects the smallest element.
• One element reaches its final position after every pass.
• It performs O(n²) comparisons.
• It requires only O(1) auxiliary space.
• It performs at most (n−1) swaps.
• It is an in-place sorting algorithm.
• It is not stable.
• It is not adaptive.
• It is suitable for small datasets.
• It is frequently asked in AKTU examinations and placement interviews.

Summary

Selection Sort is one of the simplest sorting algorithms used in Design and Analysis of Algorithms. The algorithm repeatedly selects the smallest element from the unsorted portion of the array and places it in its correct position. Although its time complexity is O(n²), its simplicity, low memory requirement, and small number of swaps make it an important algorithm for academic learning. Understanding Selection Sort also provides a strong foundation for learning more advanced sorting techniques such as Merge Sort, Quick Sort, and Heap Sort.

❮ Previous    Next ❯