자바 선택정렬

참고 링크

 

 

 

 

 

선택정렬

 

총 비교횟수

n(n-1)/2

 

최상	평균	최악
O(n^2)	O(n^2)	O(n^2)

 

/*
선택정렬

선택정렬이란 네개의 수가 정렬되지 않은채로 있다면,
첫째, 첫번째값과나머지값 중 제일 작은 수와 자리를 바꾼다.
둘째, 두번재값과 나머지값중 제일 작은 수와 자리를 바꾼다.
셋째, 세번째값과 나머지값중 제일 작은 수와 자리를 바꾼다.
정렬 끝
 */
package algorithm;

public class SelectionSort {
    public static void main(String[] args){
        int[] e = {95, 75, 85, 100, 50};
        int i, j ,a;
        int tmp; //교환 임시변수
//교환법 : 선택정렬(오름차순)
        i = 0;
        System.out.println("시작값");
        for(a = 0; a<5 ; a++) {
            System.out.print(" " + e[a]);
        }
        System.out.println();
        System.out.println("정렬 시작");

        do {
            j = i+1; //시작값 i+1;
            do {
                if(e[i] > e[j]) {
                    tmp = e[i];
                    e[i] = e[j];
                    e[j] = tmp;
                }
                j++;
            }while(j<5); //내부반복(변화) : 각 단계에서의 비교횟수.
            i++;
            for(a = 0; a<5 ; a++) {
                System.out.print(" " + e[a]);
            }
            System.out.println();
        }while(i<4);    //외부반복 고정 : 총 단계(회전)수
        for(a = 0; a<5 ; a++) {
            System.out.print(" " + e[a]);
        }
        System.out.println();// 줄변경(다음 줄로 커서 이동)
        System.out.println("정렬끝");
    }
}

선택정렬

선택정렬이란 네개의 수가 정렬되지 않은채로 있다면,
첫째, 첫번째값과나머지값 중 제일 작은 수와 자리를 바꾼다.
둘째, 두번재값과 나머지값중 제일 작은 수와 자리를 바꾼다.
셋째, 세번째값과 나머지값중 제일 작은 수와 자리를 바꾼다.
정렬 끝

 

 

|출력

시작값
 95 75 85 100 50
정렬 시작
 50 95 85 100 75   //   95와 50이 바뀜
 50 75 95 100 85   //   95와 75가 바뀜
 50 75 85 100 95   //   95와 85가 바뀜
 50 75 85 95 100   //   95와 100이 바뀜
 50 75 85 95 100
정렬끝

 

 

선택정렬 장점

- 자료 이동횟수가 정해져있다.

 

선택정렬 단점

- 안정성을 만족하지 않는다.

- 값이 같은 경우 위치 변경될 수 있다.