[알고리즘] 선택정렬 (Selection Sort)

선택 정렬

 

오름차순 정렬을 한다고 하면, n개의 데이터가 있는 배열에서

 

첫 번째 데이터를 선택하고, 두 번째 부터 n번째 배열을 첫 번째 데이터와 비교하면서 가장 작은 값의 데이터를 찾는다.

 

찾았다면, 그 데이터와 첫 번째 데이터의 위치를 서로 바꾼다.

 

이 과정을 첫 번째 데이터부터 n-1번째 데이터까지 반복한다.

 

[Java Code] 

public class EEE {

 public static void main(String args[]){

   int array[]= {1,3,4,6,2,8};

   selectionSort(array);



   for(int i=0; i<array.length; i++){

     System.out.println(array[i]);

   }

 }



 public static void selectionSort(int[] array){

   for(int i=0; i<array.length-1; i++){

     int minIndex= i;

     for(int j= i+1; j<array.length; j++){

       if(array[minIndex]> array[j]){

         minIndex= j;

       }

     }

     int temp= array[minIndex];

     array[minIndex]= array[i];

     array[i]= temp;

   }

 }

}

[Javascript Code]

const input = [13, 5, 11, 7, 23, 15];

const solution = () => {
    const arr = input;
    for (let l = 0; l < arr.length; l++){
        let minIndex = l;
        for (let k = l + 1; k < arr.length; k++){
            if (arr[minIndex] > arr[k]) {
                minIndex = k;
            }
        }

        if (minIndex !== l) {
            const temp = arr[minIndex];
            arr[minIndex] = arr[l];
            arr[l] = temp;
        }
    }
    return arr;
};
console.time();
console.log(solution());
console.timeEnd();

 

첫 번째 데이터에서 비교를 n-1번 하고

 

두 번째 데이터에서 비교를 n-2번 하고

 

... n-1번째 데이터에서 비교를 1번 하므로

 

총 비교 횟수는 (n-1)* (n-1 + 1)/2 이므로

 

선택 정렬의 시간 복잡도(Time Complexity)는 O(n^2)이 된다.