선택정렬(Selection Sort)

 

선택정렬 개념

• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• 최솟값 또는 최댓값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다. 
  • 첫번째 순서에는 첫번째 위치에 가장 최솟값을 넣는다.
  • 두번째 순서에는 두번째 위치에 남은 값 중에서의 최솟값을 넣는다.

선택정렬 특징

• 장점
  • 자료의 이동횟수가 미리 결정된다.
• 단점
  • 시간 복잡도가 n제곱이라 효율적이지 않아코딩 테스트에서는 많이 사용하지 않는다.
  • 안정성을 만족하지 않는다.
  •  
  • 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

선택정렬 예제

 

선택정렬 구현 코드

package org.kyhslam.algo;

public class selectSort {

    public static void main(String[] args) {

        int array[] = {8,75,10,60,15,49,12,25}; //8개

        selectSort(array);

        System.out.println("-----------");
        viewArray(array);
    }

    public static void selectSort(int a[]){

        int minIndex = 0;

        for(int i=0; i < a.length-1; i++){
            minIndex = i; // 최소값 인덱스 ( 초기화 : 해당 위치 값)
            for(int j=i+1; j < a.length; j++){
                if(a[minIndex] > a[j]){
                    minIndex = j;
                }
            }

            if(minIndex != i){
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }

            System.out.printf("step = " + i + "  ");
            viewArray(a);
        }
    }


    public static void viewArray(int[] arr){
        for(int k=0; k < arr.length; k++){
            System.out.printf(arr[k] + " ");
        }
        System.out.println("");
    }
}

 

선택정렬 시간복잡도