Selection Sort 구현해보기

아주 기본적인 문법들을 이용한 문제들을 지나고 나니

내가 컬렉션 프레임워크에 대해 전혀 모르고 있으며 그것이 치명적이라는 것을 깨닫게 됐다.

 

특히 재귀함수를 활용하지 않으면 구현하기 어려운 문제들을 만나게 됐다.

어렴풋이 재귀함수의 개념으로 실행해주는 무언가가 필요한데.. 라고 느끼기는 했지만

실제로 그것을 구현하지는 못했고, 계속 붙잡고 있기 보다는 보고 배우고 익히는게 효율적일 것 같아 강의를 봤다.

 

 

 

 

군더더기 없이 깔끔한 강의였다.

보고 이해한 뒤에 스스로 작성해봤는데 약간의 삐걱거림이 있었다.

재귀호출하는 함수의 실행 기준 if문의 조건을 배열의 length 보다 1 작게 하여

마지막에서 두번째 녀석까지만 비교를 수행하도록 해야 하는 점을 간과했다.

그리고 최소값 자체가 아니라 최소값을 가진 index를 갱신하는 것을 놓쳤다.

두 가지를 보완하고 나니 문제 없이 작동하는 것을 확인할 수 있었다.

 

정렬 실행 전과 후

 

아래는 코드이다.

package test;
 
public class SelectionSortTest {
 
    // 오름차순 정렬을 실행할 int배열 array를 파라메타로 받는 메소드 선언 
    private void selectionSort(int[] array) {
        //그 메소드는 다시 int배열 array와 int를 파라메타로 받는 메소드를 호출
        selectionSort(array, 0);
    }
 
    //호출된 메소드. 이 녀석은 배열의 길이만큼 돌면서 재귀적으로 계속 호출된다.
    private void selectionSort(int[] array, int start) {
 
        // 맨뒤에서 두번째 녀석까지만 실행하면 맨 뒤 녀석과 비교하기 때문에 -1해준다
        if(start < array.length-1) { 
 
            // 비교 시작점으로 전달받은 start를 최소값 비교 기준 index로 선언한다.
            int indexOfMinValue = start;
            
            // start를 기준으로 배열을 돌면서 최소값을 갖고 있는 index를 갱신한다. 
            for(int i=start; i<array.length; i++) {
                if(array[indexOfMinValue] > array[i]) {
                    indexOfMinValue = i;
                }
            }
            
            // 배열과 그 배열 내 스왑할 두 인자의 인덱스를 파라메타로 넘겨주어 swap한다.
            swap(array, start, indexOfMinValue);
            
            // sorting을 시작할 index start에 1을 더하여 재귀호출한다.
            selectionSort(array, start+1);
            // start값 즉 탐색을 실행하는 기준이 배열의 맨뒤에서 두번째까지만 실행되고
            // 배열의 맨마지막 녀석의 index와 start의 값이 같아지면 이 메소드는 종료된다.
            // 그리고 selectionSort(int[] array)로 돌아가서 이 메소드도 종료된다.
        }
    }
    
    // 배열과, 값을 맞바꿈할 두 인자의 index를 파라메타로 받아서 swap해주는 메소드
    private void swap(int[] array, int firstIndex, int secondIndex) {
        int temp = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = temp;
    }
    
    // 배열을 인자로 받아서 index 오름차순으로 출력해주는 메소드
    private void printArray(int[] array) {
        System.out.print("{");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if(!(i==array.length-1)) System.out.print(", ");
        }
        System.out.println("}");
    }
    
    
    public static void main(String[] args) {
        // 오름차순 정렬할 배열을 준비한다.
        int[] a = {5,4,3,2,1};
        // static 선언 안 해서 객체 먼저 생성해야 한다.
        SelectionSortTest s = new SelectionSortTest();
        // 정렬 전에 출력하기
        s.printArray(a);
        // 정렬하기. 인자를 두 개 받는 함수를 다시 호출하면서 파라메타로 0을 추가한다.
        // 그 뒤 마지막에서 두번째 녀석까지 정렬을 수행한 뒤에 재귀호출이 종료된다.
        s.selectionSort(a);
        // 정렬 이후 출력
        s.printArray(a);
    }    
    
}