[정렬 알고리즘] 선택 정렬

2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬

 

 

 

📎 선택 정렬

선택 정렬은 작은 요소의 순서대로 선택해 앞쪽으로 위치를 옮겨 순서대로 정렬하는 알고리즘이다.

 

선택정렬의 과정

1. 정렬되지 않은 배열의 요소 중 가장 작은 요소(최솟값) 선택
2. 정렬되지 않은 배열의 요소 중 첫 요소(제일 왼쪽에 위치한 요소)와 자리 바꿈
3. n개의 요소일 경우 n-1번만큼 <1~2> 반복

 

 

package com.doit.java.sort;
 
import java.util.Scanner;
 
public class SelectionSort {
    /*
     * 선택 정렬 : 선택 정렬은 작은 요소부터 순서대로 선택해 앞쪽으로 위치를 옮겨 순서대로 정렬하는 알고리즘
     * 일반적인 선택 정렬의 시간 복잡도는 O(n²)
     * n개의 배열 n-1번 비교함 : 총 n(n-1)/2 번 수행
     * 
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정렬할 요소의 수: ");
    
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        
        //요소 입력받음
        for(int i=0; i<n; i++) {
            arr[i]=sc.nextInt();
        }
        sc.close();
        
        selectionSort(arr, n);
                        
        System.out.println("선택 정렬 완료");
        
        //정렬 후 출력
        for(int i=0; i<n; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    
    static void selectionSort(int[] arr, int n) {
        //n개의 요소 -> n-1번 비교
        for(int i=0; i<n-1; i++) {
            //정렬되지 않은 요소 중 최솟값 찾기
            int min = i;
            
            for(int j=i+1; j<n; j++) {
                if(arr[j]<arr[min]) {
                    min = j;    //최솟값 찾아
                }
            }
            swap(arr, i, min);    //정렬되지 않은 요소 중 첫요소와 자리 바꿈
        }
    }
    
    //배열의 요소 두개의 위치를 바꿈 
    static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1]=arr[idx2];    //idx1 : idx1 -> idx2
        arr[idx2]=tmp;            //idx2 : idx2 -> idx1
    }
 
}
 

 

 

 

자바 코드로 보면 이렇다.

 

 

선택 정렬의 성능 분석

선택정렬의 시간 복잡도는 O(n²) 이다.

 

n개의 요소를 받아 정렬하기 위해서는 총 n(n-1)/2 번의 수행이 필요하다.

 

결국 몇개의 자료를 배열하든 자료수의 제곱한 값에 비례해 시간이 걸린다.

그래서 최선의 최악의 경우는 없다. 항상 저만큼의 수행이 필요하고, 자료수의 제곱만큼의 시간이 걸린다.

 

 

+ 참고

T아카데미 | 스마트 ICT 전문가 양성 (skplanet.com)

컴퓨터 알고리즘 초급 | T아카데미 온라인강의

 

+

책정보, Do it! 자료구조와 함께 배우는 알고리즘 입문 : 네이버 책 (naver.com)

Do it! 자료구조와 함께 배우는 알고리즘 입문