Implement Selection sort easily in your program

Selection sort is a simple comparison-based sorting algorithm. It works by dividing the input array into a sorted and an unsorted part. In each iteration, it selects the smallest (or largest) element from the unsorted part and moves it to the sorted part. This process is repeated until the entire array is sorted.

How Selection Sort Works

Let's understand the steps involved in the selection sort algorithm:

Step 1: Start with the first element in the array, which is considered the smallest element.

Step 2: Traverse through the remaining elements of the array to find the minimum element.

Step 3: If a smaller element is found, update the minimum element.

Step 4: After traversing the entire unsorted part of the array, swap the minimum element with the first element of the unsorted part. This places the minimum element in its correct position in the sorted part of the array.

Step 5: Repeat steps 2 to 4 for the remaining unsorted part of the array until the entire array is sorted.

Implementation Steps

Let's dive into the implementation of the selection sort algorithm:

Step 1: Prompt the user to enter the size of the array by using the input() function and convert it to an integer using int() function. Store the value in a variable n.

Step 2: Create an empty list called arr to store the elements of the array.

Step 3: Create a loop that iterates n times using the range() function. Inside the loop, prompt the user to enter each element of the array one by one using the input() function, convert it to an integer using int() function, and append it to the arr list.

Step 4: Create a nested loop that iterates through the array elements. The outer loop iterates from index 0 to n-1, and the inner loop iterates from the next element after the current index to n.

Step 5: Inside the nested loop, compare the element at index i with the element at index j. If the element at index i is greater than the element at index j, perform the following steps to swap the elements without using a temporary variable:

Add the element at index j to the element at index i.

Assign the difference of the new element at index j and the original element at index i to the element at index i.

Assign the difference of the new element at index i and the original element at index j to the element at index j.

Step 6: After the nested loop completes, the array will be sorted in ascending order.

Step 7: Create a loop to iterate through each element in the sorted array. Print each element using the print() function and the end parameter to specify a space character as the separator.

Step 8: Run the program and enter the size of the array and its elements when prompted. The program will sort the elements using the selection sort algorithm and display the sorted array.

By following these implementation steps, you can effectively sort an array in ascending order using the selection sort algorithm in Python.

Code

n=int(input("Enter size of array: "))
arr = []

for i in range(n):
    arr.append(int(input()))

print('Unsorted Array: ')
for i in arr:
    print(i, end=" ")

for i in range(n-1):
    for j in range(i+1, n):
        if(arr[i] > arr[j]):
            arr[j] += arr[i]
            arr[i] = arr[j] - arr[i]
            arr[j] -= arr[i]

print('Sorted Array: ')
for i in arr:
    print(i, end=" ")

Example

Enter size of array: 5
64
25
12
22
11
Unsorted Array: 64 25 12 22 11
Sorted Array: 11 12 22 25 64

Time Complexity

The selection sort algorithm has a time complexity of O(n^2), where n is the number of elements in the array. This makes it inefficient for large arrays. However, it performs well for small arrays or when the auxiliary space is limited.

Conclusion

Selection sort is a simple and intuitive sorting algorithm that can be implemented easily in Python. Although it has a time complexity of O(n²), it can be a good choice for small arrays or situations where auxiliary space is limited. Understanding the selection sort algorithm is essential for any programmer's toolkit when working with sorting algorithms.