[Algorithm] 정렬 - 선택 정렬(Selection Sort)

# 요약

• 인간이 정렬하는 과정과 매우 비슷
• 데이터를 한번에 읽고 정렬 진

# 구체적 설명

1. 주어진 데이터 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

# 알고리즘

# 코드 작성 -  JAVA

import java.util.Arrays;

public class SortAlgorithm {
    static int[] arr = new int[]{7, 1, 3, 2, 4, 5, 6};
    static int cnt =0;

    public static void main(String[] args) {
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length -1; i++) {
            int min_idx = i; //
            for (int j = i +1; j < arr.length; j++) {
                if (arr[j] < arr[min_idx]){
                    min_idx =j;
                }
            }
            swap(min_idx , i); //최솟값과 맨 앞 위치한 값을 교체한다
        }
    }

    private static void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        cnt++;
    }
}

# 결과

[1, 2, 3, 4, 5, 6, 7]

#시간복잡도

최선	O(n2)
평균	O(n2)
최악	O(n2)

#장단점

장점	단점
- 제자리 정렬: 추가적인 메모리가 거의 필요하지 않는다. - 동일한 값을 가진 요소들의 상대적인 순서가 변경되지 않는다. - 이해하기 쉽다	- O(n2)이라는 비효율적인 시간복잡도를 가진다.

 

---

※ 제자리 정렬

• 정렬을 수행할 때 추가적인 메모리를 최소한으로 사용하는 정렬 방법