알고리즘 기초 (선택정렬)

Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다.

선택정렬

---

우리는 보통 정렬되지 않은 배열보다 정렬이 된 배열에서 자료를 더 쉽게 찾을 수 있습니다. 이런 정렬을 위한 알고리즘 중 선택정렬은 배열의 자료중 가장 작은 단위를 찾아 첫번째 위치의 수와 교환하는 방식을 말합니다. 선택정렬은 실행되는 동안 교환 횟수는 줄어들지만 각 자료를 비교하는 횟수는 증가한다는 특징을 가지고 있습니다.

선택정렬의 비교 횟수

---

선택정렬은 버블정렬과 다르게 몇 번의 교환을 해주었는지 교환 횟수 대신 비교 횟수를 기준으로 합니다. 오름차순이 기준이면 최소값을 찾아 왼쪽으로 정렬하고 내림차순이면 최대값을 찾아 오른쪽으로 정렬을 해주면 됩니다. 선택정렬은 n(n-1)/2 이란 비교횟수 연산공식을 가지고 있고 데이터양이 적을때 좋은 성능을 나타내며, 작은 값을 선택하기 위해 비교를 많이 하지만 반대로 교환 횟수는 작습니다. 100개 이상의 자료에 대해서는 성능이 떨어지기도 하며 가장 작은 값과 현재 위치 값을 교환하는 방식은 현재의 값이 뒤쪽 어느 위치에 갈지 알 수 없기에 안정성 또한 보장되지 못하는 단점도 가지고 있습니다.

코드 구현

---

public static void selectionSort(int[] list) {
        int min, i, j, temp;          
        int size = list.length; 


        for (i = 0; i < size - 1; i++) {
            min = i;        
            for (j = i + 1; j < size; j++) {
                if (list[j] < list[min]) { 
                    min = j;
                }
            }
            //swap
            temp = list[min];
            list[min] = list[i];
            list[i] = temp;

            System.out.print("\nSelectionSort "+(i+1)+" 단계 : ");
            for(int z=0; z<size; z++){
                System.out.print(list[z]+" ");
            }
        }
    }

    public static void main(String[] args) {
        int [] list= {23,2,10,5,4,21,6};
        selectionSort(list);
    }

결과

---

참고

---

cs50 x edwith
위키백과