Selection Sort

 

 

 

Selection Sort 선택정렬

 

Selection sort searches for the smallest element among the unsorted elements sort them in ascending order and places them in order from the first index of the array.

 

 

 

Solution in Java

public class Main {
    public static void main(String[] args) {
        int arr[] = {37, 15, 8, 22, 10}; //required {8, 10, 15, 22, 37} in ascending order.
 
        selectionSort(arr);
        showArr(arr);
    }
 
    private static void selectionSort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) { //전체 배열 돌기 마지막은 어차피 정렬이 완료되어있을테니 끝까지 돌 필요없으니 length - 1
            int min = i; //제일 작은 수에 해당하는 variable
            for (int j = i + 1; j < arr.length; j++) { //제일 작은 수 찾기는 전체를 돌어서 찾아야하니 length 만큼 도는 것이 맞다.
                if (arr[j] < arr[min])
                    min = j;
            }
            //swap
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
 
    private static void showArr(int arr[]) {
        for (int data : arr) {
            System.out.print(data + ", "); //8, 10, 15, 22, 37,
 
        }
    }
}

 

 

Big-O notation for Selection Sort is O(n²) 

               Why?

 

n - 1 + n - 2 + ... + 2 + 1 

                 +                    // Sum the total number of steps

1 + 2 + ... + n - 2 + n - 1  

                /2

                 =

       n x (n - 1) / 2 

                 =

         1/2(n² - n) 

              n² - n //Remove constant

              O(n²) //Leave only larger value. 'n²' is larger than 'n'

 

 

 

 

Solution in Javascript

let arr = [3,4,1,6,2];

function Selection(arr){
    for(let i = 0; i < arr.length; i++){
        let min = i;

        //index no
        for(let j = i+1; j < arr.length; j++){
            if(arr[j] < arr[min]){
                min = j;
            }
        }

        //swipe
        if(i !== min){
            const newMin = arr[min];
            arr[min] = arr[i];
            arr[i] = newMin;
        }
    }
    console.log(arr); // [1,2,3,4,6]
}

Selection(arr);

 

 

 

Reference

https://zeddios.tistory.com/20

https://www.geeksforgeeks.org/selection-sort/