[알고리즘/정렬 알고리즘] 선택 정렬 (Selection sort) Java, Python

선택 정렬(Selection sort) 알고리즘의 개념

• (오름 차순일 경우)가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.
• 제자리 정렬(in-place sorting) 알고리즘의 하나
• 정렬을 마친 부분과 아직 정렬하지 않은 부분이 나뉘어 있으며, 아직 정렬되지 않는 부분에서 최솟값을 찾아 정렬의 마친 부분의 끝 부분에 값을 넣어준다.

선택 정렬(Selection sort) 예제

•  배열에 3, 2, 6, 4, 1 순으로 값이 들어가 있고 오름차순으로 정렬할 대의 선택 정렬 예를 확인해보자

• 위의 과정과 같이 배열 중 최솟값을 찾아 회색 부분(정렬하지 않은 부분의 첫 번째 요소)과 살구색 부분(정렬하지 않은 부분의 최솟값)을 교환해주고 만약 둘이 같은 값을 가진다면 다음 단계로 넘어간다.

[Java 코드]

public class SelectionSort {
 
    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 4, 1};
        int temp = 0;
        int minIdx = 0;
        int N = arr.length;
        
        for(int i = 0; i < N-1; i++) {            //마지막 요소는 자동 정렬되므로 N-1까지 반복
            minIdx = i;
            
            for(int j = i+1; j < N; j++) {    //최솟값 찾기
                if(arr[j] < arr[minIdx]) { 
                    minIdx = j;
                }
            }
            
            if(i != minIdx) {                    //최솟값을 찾았다면 최솟값과 자리 바꿔주기
                temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }
        
        for(int a : arr) {
            System.out.print(a +" ");
        }
    }
}
 

 

[Python 코드]

def selection_sort(arr):
    N = len(arr)
 
    for i in range(N-1):
        minidx = i
 
        for j in range(i+1, N):                         #최솟값 찾기
            if arr[j] < arr[minidx]:
                minidx = j       
 
        if i != minidx:
            arr[minidx], arr[i] = arr[i], arr[minidx]    #swap
 
    print(arr)
 
 
arr = [3, 2, 6, 4, 1]
selection_sort(arr)