[JAVA] 정렬 알고리즘(선택정렬)

정렬(Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것

* 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨.

---

1. 선택 정렬

정렬이 완료되지 않은 데이터 중 가장 작은 (혹은 가장 큰) 데이터를 선택해 맨 앞에 (혹은 맨 뒤에) 있는 데이터와 바꾸는 것을 반복하는 알고리즘.

최소 값 기준 정렬

최대 값 기준 정렬

* 마지막에 남은 숫자의 경우 정렬을 수행하지 않아도 된다.

수행 과정을 보면, 정렬이 되지 않은 숫자들을 하나씩 비교해가며 최소 값(최대 값)을 찾고 이를 정렬하는 과정을 반복한다. 따라서 이중 반복문을 사용하여 구현할 수 있다.
▶시간복잡도 : O(n^2)

<코드>

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        int n = 5;
        int[] arr = {29, 10, 14, 37, 13};
 
        for(int i = 0; i < n; i++){
            int min_idx = i;
            for(int j = i + 1; j < n; j++){
                if(arr[min_idx] > arr[j]){
                    min_idx = j;
                }
            }    
 
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
        for(int i = 0; i < n; i++){
            System.out.print(arr[i] + " ");
        }
    }
}

---

추가 예정