[알고리즘] 선택 정렬(Selection sort) 알아보기

안녕하세요🌟

이번 포스팅은 저번에 이어서 정렬 알고리즘의 [선택 정렬]에 대해서 알아보도록 하겠습니다.

* 다양한 정렬 알고리즘

1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 병합 정렬
5. 퀵 정렬
6. 힙 정렬

---

---

선택 정렬(Selection Sort)

---

• 주어진 배열(데이터) 속에서 전체 순회를 하여 최솟값을 찾고, 해당 최솟값을 배열의 맨 앞 데이터와 위치 교환
• 이와 같이 순회를 돌면서 최소값을(디센딩 방식은 최댓값을) 찾고 선택하여 교체하며 정렬하는 방식
• 단, 앞으로 이동한 최소값들은 다음 순회 때 순회 대상에서 제외됨

어떻게 보면 버블 정렬과 유사합니다.

 

01. 그림으로 방식 이해하기

어센딩 방식을 예시로 들었습니다.

 

1) 아래 그림처럼 정렬되지 않은 데이터를 가진 배열이 있습니다.

• 인덱스 0번인 8부터 인덱스 4의 7까지 전체 순회를 합니다.
• 전체 순회를 진행하면서 가장 작은 데이터, 즉 최솟값을 구합니다.
• 해당 최소값과 인덱스 0번과 자리를 교체합니다.

2) 앞 과정과 동일하게 최솟값을 찾기 위해 다시 순회합니다. 이때 인덱스 0번은 제외시킵니다.

• 따라서 인덱스 1번인 4부터 인덱스 4까지 다시 순회합니다.
• 다음은 1을 제외한 최소값 3을 찾았으므로 인덱스 1번인 4와 자리를 교체합니다.

 

3) 교체가 완료되면 인덱스 0번과 1번을 제외해서 앞 과정을 또 반복합니다.

 

4) 총 4번의 순회를 완료하여 정렬이 완료된 모습입니다.

---

02. 코드 구현

참고 클래스 : Collections.swap
-> Java.util 의 클래스
-> Collections.swap(List<?> list, int i, int j);
-> list의 index i와 index j 의 자리를 바꿈.

참고 클래스 : Math.random
-> Java.lang 의 클래스
-> Math.random()
-> 0 이상 1 미만의 부동 소수점 값을 가져올 수 있음 => 0.12

 

1) 정렬 메서드 구현

public ArrayList<Integer> sort(ArrayList<Integer> dataList) {

    for(int i = 0; i < dataList.size(); i++) { // outter

        Integer MinNum = i; // 최소 값을 가진 index

        for(int j = i ; j < dataList.size() ; j++) { // inner

			// MinNum 인덱스의 값이 j 인덱스의 값보다 클 때
            if(dataList.get(MinNum) > dataList.get(j)) {
                
                // MinNum 인덱스를 j 인덱스로 대입(변경)
                MinNum = j;
            }
        }

        Collections.swap(dataList, i, MinNum);
    }
    
	// 정렬된 배열을 반환
    return dataList;
}

• 정렬되지 않은 배열을 메소드의 매개변수로 받습니다.
• outter for문에서 배열의 사이즈만큼 순회를 할 것임을 알 수 있습니다.
• 가장 먼저 최소값을 배열의 인덱스 0번으로 지정합니다.
• inner for문을 통해서 배열을 순회하면서 최솟값을 구합니다.
• 최솟값에 해당하는 인덱스가 MinNum으로 저장되고, Collections.swap을 통해서 i와 MinNum 자리를 교체합니다.
• 순회가 모두 완료되면 정렬이 다 되면서 이를 반환합니다.

2) 실행

public static void main(String[] args) {

    ArrayList<Integer> dataList = new ArrayList<>();

    dataList.add(1);
    dataList.add(3);
    dataList.add(5);
    dataList.add(2);
    dataList.add(10);
    dataList.add(25);
    dataList.add(18);

    System.out.println(dataList); // [1,3,5,2,10,25,18]

    SelectionSort sortTest = new SelectionSort();

    System.out.println(sortTest.sort(dataList)); // [1,2,3,5,10,18,25]
}

 

결과는 예상한대로 정렬이 되어서 나오게 됩니다.

---

03. 시간 복잡도

선택 정렬의 시간 복잡도는 버블 정렬과 동일하게 O(N^2)입니다.

마찬가지로 이중 반복문을 진행하기 때문에 동일하게 되는데요. 조금 더 자세하게 보도록 하겠습니다.

위 그림 설명에서 5개의 데이터를 가진 배열이 있었는데요. 정렬을 하기 위해 총 4번을 순회하고, 각 순회마다 최솟값을 찾기 위한 순회 횟수가 점점 줄어드는 것을 알 수 있습니다. 즉 정렬을 위해 값들 서로가 총 10번 비교하게 되었습니다.

이를 일반화했을 때 버블 정렬과 동일하게 (N-1) + (N-2) + (N-3) + ... + 1 이와 같이 되고, N개의 데이터를 등차수열 공식으로 나타내면 N ( N -1) / 2 가 되면서, 최고차항만 나타내면서 계수를 제외하는 빅오 표기법에 따라 시간 복잡도는 O(n^2)가 됩니다.