선택정렬

1. 선택정렬이란?

정렬 순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그자리에 있던 데이터는 빈자리로 이동하는것.

2. 선택정렬 구현

- 버블정렬과 유사하다

- for문 중첩으로 구현하였다. 

- 안쪽 for문의 반복조건과 바깥쪽 for문의 반복조건에 대한 이해가 정확히 필요하다.

public class SelectionSort {
 
    public static void main(String[] args) {
 
        int[] arr = {3, 2, 4, 1};
 
        SelSort(arr, arr.length);
 
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
    static void SelSort(int[] arr, int n)
    {
        int i, j;
        int temp;//임시
        int min;
        
        for(i=0; i<n-1; i++) {
             min = i;
            for(j=i+1; j<n; j++) {// 최소값 탐색
                if(arr[min] > arr[j]) {//선택정렬의 비교연산
                    min = j;
                }
            }
            /* 교환 */
            temp = arr[i];
            arr[i]= arr[min];
            arr[min] = temp;
        }
    }
}
 

3. 성능평가

앞서본 버블정렬과 성능상 큰 차이가 없다.

비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.

if(arr[min] > arr[j]) {//선택정렬의 비교연산

                    min = j;

         }

4개의 데이터를 3단계에 걸쳐서 정렬하였다. 비교의 횟수를 더한 결과는 3+2+1 이었다.

이렇듯 버블 정렬의 데이터의 수가 n개일때 진행되는 비교의 횟수는 다음과 같다.

(n-1) + (n-2) + . . . + 2+ 1

그리고 이는 등차수열의 합에 해당하므로 다음과 같이 정리된다.

따라서 선택정렬의 비교연산에 대한 빅-오는 최선의 경우와 최악의 경우 구분없이 O(n^2) 이다.

빅오를 구할때 이동의 횟수는 무시했다.