[정렬] 선택정렬

정렬

정렬 알고리즘	정의	시간복잡도
삽입	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식	O(N) ~ O(N^2)
버블	데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식	O(N^2)
선택	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식	O(N^2)
퀵	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식	O(NlogN) ~ O(N^2)
힙	이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식	O(NlogN)
병합	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식	O(NlogN) + 추가적인 메모리 필요
기수	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식	O(N) + 추가적인 메모리 필요

 

선택정렬이란?

선택정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법입니다.
선택정렬은 구현 방법이 복잡하고, 시간복잡도도 O(N^2)으로 효율적이지 않습니다.
(코딩테스트에서는 직접적인 문제로 출제되지 않는 편)

 

선택정렬 과정

• 1, 3, 4, 2, 5 를 선택정렬로서 정렬하기
  • 빨간색 : 정렬이 완료된 숫자
  • 파란색 : 정렬을 해야할 숫자

순번	과정
첫번째	1	3	4	2	5
두번째	1	2	4	3	5
세번째	1	2	3	4	5
완성	1	2	3	4	5

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다
2. 남은 정렬 부분에서 가장 앞에있는 데이터와 선택된 데이터를 swap 한다
3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다
4. 전체 데이터 크기만큼 index가 커질 때까지 , 즉 남은 정렬 부분이 없을 때까지 반복한다

 

선택정렬 구현

• 두번째 반복문에서, 정렬해야하는 범위에서 최솟값 인덱스를 찾는다
• 범위에서 가장 앞에있는 인덱스와 최솟값 인덱스가 다르다면, swap()을 진행한다
• 정렬이 완료된 후, 출력

public class App {
    private static final int SIZE = 5;
    public static void main(String[] args) throws Exception {
        
        int []arr = {1,3,4,2,5};
        
        for(int i =0; i<SIZE; i++){
            int minIdx = i;
            for(int j = i+1; j< SIZE; j++){
                if (arr[minIdx] > arr[j]){
                    minIdx = j;
                }
            }
            if(i != minIdx){
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }

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