[자료구조] 선택정렬 with JAVA

[자료구조] 선택정렬 with JAVA

 

 

 

• 선택정렬

 - 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다.

 

 [예시]

  1) 기준 위치 첫 번째 - 전체 원소 중 가장 작은 원소를 찾아 선택한 후 첫 번째 원소와 자리를 교환한다.

  2) 기준 위치 두 번째 - 정렬된 첫 번째를 제외한 나머지 원소 중 가장 작은 원소 선택한 후 두 번째 원소와 자리 교환한다.

  3) 기준 위치 세 번째 - 정렬된 1, 2번째를 제외한 나머지 원소 중 가장 작은 원소를 선택한 후 세 번째 원소와 자리를 교환한다.

  ...

 

 - 코드를 보면 더욱 쉽게 이해된다!

 - 시간 복잡도

  [예시]를 참고하여 과정을 들여다보면 규칙을 하나 찾을 수 있다. i단계에서는 i번째 기준으로 n-i개 원소를 비교하게 된다.

  즉, 전체 비교횟수는 아래와 같다.

 

 

 - 선택 정렬에서는 어느 경우나 비교 횟수가 동일하여 O(n^2) 이다. 

 

 [코드]

package Sort;
import java.util.Arrays;

public class SelectionSort {

    //선택 정렬 연산
    public static void SelectionSort(int a[], int size) {
        int t, min, temp;
        //정렬 전 출력
        for(int i=0;i<size;i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println("");
        System.out.println("--------------Selection Sort--------------");
        for(int i=0;i<size-1;i++) {
            min = i;
            for(int j=i+1;j<size;j++) {
                if(a[j]<a[min]) {
                    min = j;
                }
            }
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
            System.out.println(i+"단계: "+Arrays.toString(a));        
        }
    }
    
    public static void main(String[] args) {
        int[] list = {69, 11, 30, 2, 16, 8, 31, 22};
        int size = list.length;
        SelectionSort(list, size);
    }

}

 

 [수행결과]

 

 

 

[참조] c로 배우는 쉬운 자료구조, 한빛미디어, 이지영 저 , 시그마 관련 - http://elwlsek.tistory.com/467