[Sort] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

[출처: 위키]

개념: 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다. 

전체 원소 중에서 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환 하는 방식이다.

라고... 이렇게 말하면 다들 이해 안가시죠??!

그림으로 쉽게 보도록 하겠습니다!

맨 처음 정렬을 하기 위한 요런 숫자들이 있다고 칩시다.

 

당연히 2, 8, 10 이런 순서로 만들고 싶죠?? 

근질근질 하시죠??

​자 그럼 시작해 보도록 하것습니다요~

---

1단계:

맨 처음은!! 첫 원소(값)가 가장 작은 값을 찾습니다!! 아래 처럼!!

69 라는 숫자가 2 라는 가장 작은 값을 찾았네요!! 

찾고 나서 자리를 바꿔 줍니다!!

* 물론 2를 찾기 전에 69는 10과 30도 비교해 봤습니다. 

---

1 단계(phase) 끝입니다!

---

2단계:

그럼 아래처럼 되어 있는 상태 입니다.

네. 여기서 저 괄호가 들어간 부분만 정렬 한다는 거죠!!!

그럼 다시 정렬을 하면!

괄호 내에서 첫 번째 원소(값) 10이 8이라는 가장 작은 숫자를 찾았네요!

두 값을 바꿔줍니다!!

---

여기까지 2 단계(phase) 끝입니다! 

---

3단계:

2 단계까지 끝난 상태는 아래와 같습니다!!

점점 정렬할 부분이 줄어들고 있죠~?

계속 진행해 보도록 핪!!!!

괄호 내의 첫 원소 30이 가장 작은 값인 10을 찾았네요~!

두 값의 위치를 바꿔줍니다!!

 

---

여기까지 3 단계(phase) 끝입니다! 

 

점점 캡쳐뜨는데 힘이 부치지만 힘내서 마무리 짓도록 하겠습니다!!

---

4단계:

3단계가 끝난 상태는 아래와 같습니다!

 

인자 3개의 원소만 정렬해주면 됩니다!!!

방법은 첫 원소가!!! 가장 작은 값이랑 자리를 바꾸는 방식!!

해서! 69라는 값이 16과 자리를 바꿉니다!!

before:

 

after:

 

---

여기까지 4 단계(phase) 끝입니다!

---

5단계:

4 단계까지 끝나면 아래와 같아요~

인제 뭐 2갠데 걍 바꾸면 정렬 완료겠죠?~?

  

위의 요걸 아래처럼 바꾸면 정렬 끝 !!!

 

---

이렇게 해서 정렬이 끝났습니다...

이 선택 정렬(Selection Sort)의 시간 복잡도(Time Complexity)는 아래와 같습니다!

Best, Worst, Average 모두다

입니다...

왜 냐 면

이니까요...

복잡도 계산은 왜 그런지 보다는 여러분은 Best와 Worst 정도가 빅오표기법으로 어떻게 되느냐 

정도만 아시면 되니깐 부연설명은 안하겠습니다...

그럼 코드를 한번 봅시다요!

Java로 짜봤습니다~

SelectionMain.java와 SelectionSort.java로 나눴습니다.

먼저, SelectionMain.java

package Selection;
 
public class SelectionMain {
    public static void main(String[] args) {
        int [] arr = {69, 10, 30, 2, 16, 8}; // 정렬 전 배열
        
        SelectionSort.selectionSort(arr);
    }
}
 

 

여기에 아까 정렬 전의 숫자가 그대로 있죠???

다음은 SelectionSort.java

 

 
package Selection;
 
 
public class SelectionSort {
    public static void selectionSort(int [] arr) {
        int min = 0; // 최저 값을 담을 요소
        
        for (int i = 0; i < arr.length - 1; i++) {
            min = i; // 첫번째 요소를 선택
            
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) // 첫번째 요소와 가장 적은 값을 찾는 비교 연산 
                    min = j;
            }
            swap(arr, min, i); 
            System.out.println("선택 정렬 " + (i + 1) + " 단계: ");
            printArr(arr);
        }
    }
    
    public static void swap(int [] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    public static void printArr(int [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
 

이렇게 작성 후, 실행한 결과 아래와 같아요~