Everything You Need To Know About Selection Sort | Codeityweb

How to Implement Selection Sort In Python and Java

Selection sort is a sorting algorithm in which we select the minimum or maximum element from the array and place it to its appropriate starting position in every iteration.

 

Algorithm:

• "i" is the iterator of outer loop and "j" is the iterator of inner loop.
  
• We run two loops outer loop will run from 0 to length of the array and the inner loop will run from i+1 to length of array "i " is the iterator of outer loop
• At every iteration we select  "i"th element as minimum element.
• In the inner loop we check if the "j" th element is smaller than the minimum element then we  make the minimum element as "j" th element.
• After the iteration we swap the values of "i" th element and minimum element.
• We repeat the steps until the array is sorted.

 

Working of Selection Sort:

To Understand the technique properly lets run the algorithm on sample array

arr = [15, 10, 4, 20, 1] 

In our Bubble Sort Post we have explained the working using an example of students of different height .

Their students asks each other and compare their heights and if their is proper comparison then they swap their positions , and finally at the end the students are sorted as per their heights.

So here as well we will consider the same example , but In this case their is a monitor who will sort the students and not the students themselves.

Initial Students position:

So now the monitor arrives and see the students now he decides to use Selection Sort to Sort the students from smallest to highest heights.

 

Iteration 1:

• Now the monitor don't have access to all students heights so he considers 1st student Height 15 unit as the smallest height student and he starts comparing his height with the 2nd student  Height 10 unit he sees that he is smaller than the previous smaller height student so the considers student with Height 10 unit as smallest student.
• Again the monitor compares height of 3rd student with the minimum height student , He found that he is again smaller than the previous student. 4<10 , So he make him as smallest height student.
•  He check Height 20 with minimum so far i.e 4 , but 20>4 so the keep 4 as smallest.
  
• Finally he reaches the last student and compare his height with the minimum height , he sees that student with Height 1 unit is smaller than Minimum height student so far, so he considers him as smallest. 
• So now he has checked all students height and found the student with Height 1 unit is smallest , so he swaps his position with the student at 1st position because he was looking for 1st position only.

 

Thus after first Iteration the students become:As you can see now the smallest height student is at its right position.

 

Iteration 2:

• Now the monitor searches for the student who can fit at the position 2 ,so he repeats the same process.
• He found that Height 4 unit is the next smallest height so he places him their.

Thus after Second Iteration the students become:As you can see now the next smallest height student is at its right position.

 

Iteration 3: 

In this iteration he finds the student to fit at position 3 since student with Height 10 unit is the right student and he is already at his right position, so their is no swapping needed.

 

Iteration 4:

 

Now similarly he finds right student at position 4 and places him their.

 

 

Iteration 5:

 As all students are at their appropriate position no swapping is done in this iteration and Now you can see that all students are sorted in ascending order of their heights.

 

 Selection Sort  Java:

-
public class SelectionSort{


public void sort(int arr[]) {
    int min = 0;
    for (int i = 0; i < arr.length; i++) {
        min = i;
        for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
        min = j;
    }
}
    int temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
    System.out.println("Iteration : " + (i + 1));
    print(arr);
    }
}


public static void print(int arr[]) {

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


public static void main(String[] args) {

    int arr[] = { 15, 10, 4, 20, 1 };
    System.out.print("Array Before : ");
    print(arr);
    new SelectionSort().sort(arr);
    System.out.print("Array After: ");
    print(arr);
    }
}



-

Output:

Selection Sort  Python:

-
def selectionSort(arr):
    for i in range(len(arr)):
        min = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min]:
                min = j
                arr[i], arr[min] = arr[min], arr[i]
        print(arr)


if __name__ == "__main__":
    arr = [15, 10, 4, 20, 1]
    print("List Before Sorting:", arr)
    selectionSort(arr)
    print("List After Sorting", arr)

 -

 Output:

 

Parameter Check:

 

Worst Case Performance(Time-Complexity): О(n²),Due to Two nested loops to                                                                                 understand it in short.

Worst Case Space Complexity(Space-Complexity): O(1) auxiliary Space

Is it Stable: No

 

 

Related Posts:

• Bubble Sort 

• Bubble Sort In Python

 

 

Conclusion:

In this way we can sort arrays in java and python , sorting string array can also be done using the same code just the difference will be in the comparison of two strings as it is different then comparing two integers.