[Algoritm]초보자도 쉽게 선택정렬 이해하기! - java언어, 백준문제풀이

 

선택정렬(Selection Sorting)

데이터를 선택정렬로 정렬하는 방식

 

선택정렬 개념, 선택정렬이란?

제자리 정렬(in-place sorting) 알고리즘 중 하나로, 입력된 원소들 외에 다른 메모리를 추가로 요구하지 않는다. 

 

매 순서마다 원소를 넣을 위치는 정해져있고, 그 위치에 어떤 원소를 넣을것인지 찾아서 선택하는 알고리즘이다.

 

즉 오름차순일 경우, 이미  정해진 위치인 '배열의 0번째 방'에 가장 작은 원소를 넣기로한다. 정렬되지 않은 원소들을 탐색하여 0번째 방에 들어갈 가장 작은 수를 선택한 다음, 가장 앞쪽에 있는 원소와 0번째 방에 있는 원소를 교환한다.

 

 

그림으로 이해하기

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

시간 복잡도

• O(n^2)
  • 최악, 최선, 평균 모두 동일함. 

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• 동일한 시간복잡도를 가진 버블정렬보다 교환횟수가 적다. (선택정렬은 버블정렬보다 항상 우수하다)
• 사용할 수 있는 메모리가 제한적인 경우에 사용하면 성능상 이점이 있다.
• 알고리즘이 단순하고 직관적이다. 구현이 쉽다. 

단점

• 원소들이 이미 정렬되어 있더라도 관계없이 동일한 횟수의 연산을 진행하기 때문에 효율성이 떨어진다. 
  • 이미 제자리에 있어도 비교를 수행한다.
• 불안정 정렬(unstable sorting)으로 정렬후에 같은 값을 가지는 원소들의 순서가 유지되지 않을 수 있음

 

 

소스코드 예시와 설명 (백준문제_ java)

백준 1427 문제 정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/1427

  조건 -  주어진 원소목록을 내림차순으로 정렬하기

import java.util.*;

public class 선택정렬_내림차순1427 {
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] a = new int[str.length()];
        for(int i=0; i<str.length();i++){
            a[i] = Integer.parseInt(str.substring(i,i+1));
        }
        //배열중 가장 큰 수를 찾아서 앞에 배치하기.
        //그다음번에는 배치된 다음번부터의 배열에서만 정렬하기.
        //이중 for문
        for(int i=0;i<a.length;i++){ //0번방부터 시작
            //여기서 메인 
            //i와 i+1 비교, i보다 크면 max에 저장
            int max = i;
            for(int j=i+1;j<a.length;j++) {
                if(a[max]<a[j]){
                    max = j;
                }
            }//for1
            
            //마지막에 남은 temp를 i에 할당, i는 젤 큰수의 인덱스로 할당 - 교환작업
            int temp = a[i];
            a[i] = a[max];
            a[max]=temp;
        }//for2
        for (int i : a) {
            System.out.print(i);
        }
    }
}