정렬 - Selection Sort

<Selection Sort>

<서론>

내가 프로그래밍 로직에 눈 뜨게 해준 소중한 알고리즘이다.

 

물론 자바를 배우는 지금은 동적할당인 Vector 클래스를 이용해서

Sort() 메소드만 사용하면 단 한 줄 만으로 Sort가 되지만 중요한건

프로그래밍 로직을 이해하기 위해 만들어 보는 것이다.

 

 

<본론>

우선 처리순서와 어떠한 알고리즘으로 돌아가는지 간단히 생각해보자.

Selection Sort는 Sort 중에 가장 단순하면서 가장 느린 Sort이다.

 

첫번째 자리부터 일일이 하나하나 찾아가서 조건이 맞으면 큰 수를

오른쪽으로 보내는 로직이다. 그럼 일단 왼쪽 오른쪽 바꾸는 로직이 필요하겠군.

 

변수 : a[배열], temp

연산자 : >  (왼쪽이 크면)

 

실행문

-  temp = a[i]

    a[i] = a[j]

    a[j] = temp

또는

- a[i] ^= a[j]

    a[j] ^= a[i]

    a[i] ^= a[j]

 

(배열 좌측과 우측을 뒤바꾸는 실행문)

 

클래스 : System.in, Scanner 등등

 

우선 임의의 수 5개를 적어보자.

1004, 40, 486, 50, 20

 

 Selection Sort는 일일이 하나하나 비교하는 거니깐..

1004와 40을 비교하고.. 다음은 1004와 486을 비교, 다음 50, 20 이렇게 비교..

그럼 1부터 5까지 실행하는 제어문이 필요하겠군.. 만만한게 for 다..

 

for(int i=0; i<5; i++) {

처리

}

 

뭐 요런 형태겠군.. 근데 하나로는 안될 거고..

for(int i=0; i<5; i++) {

    for(int j=i; j<5; j++) {

    }

}

이렇게 처리해야겠지?

 

아참... 근데 (1번째) > (1번째)가 아니라 (1번째) > (2번째) 부터 시작을 해야 되고

마지막엔 (4번째) > (5번째) 로 비교를 끝내야 하니까 옵션을 좀더 주면

 

for(int i=0; i<5-1; i++) {

    for(int j=i+1; j<5; j++) {

    }

}

 

대략 이정도가 되겠군... 일단은 생각했던걸 적어보자..

 

int a[] = {1004, 40, 486, 50, 20};
int temp;
for(int i=0; i<a.length-1; i++) {
    for(int j=i+1; j<a.length; j++) {
        if(a[i] > a[j]) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}
for(int i : a) {
    System.out.print(i + "  ");
}

 

야호~ 다 만들었다~