TIL - 2024/08/28

오늘도 코테 1문제를 풀고, 어제에 이어서 Java 기본 개념 영상을 이어서 봤다. 선택 정렬도 볼 예정

 

https://www.youtube.com/watch?v=DNCBaeCoMug

 

 

아스키 코드 , 내 머리 속에서 아예 잊고 살았는데 다시 상기 시켜주니 좋은거 같다.

 

 

defalult랑 protected는 거의 안쓴거 같다.

 

수준별 수업 한거 강의랑 , 다른 강의자료도 다시 다 볼 예정이다.

 

오늘의 알고리즘은 선택정렬 쪽 부분을 다시한번 봤다.

 

선택 정렬(Selection Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 직관적이지만 효율성이 떨어지는 알고리즘이다.

주어진 리스트에서 매번 가장 작은 (또는 큰) 원소를 찾아서 맨 앞부터 차례대로 정렬하는 방식,

선택 정렬의 전체적인 과정과 특징을 정리해봄

 

선택 정렬의 과정

1.기준 위치 선택: 정렬되지 않은 리스트에서 첫 번째 원소를 기준으로 선택합니다.
2.최소값 탐색: 기준 위치 이후의 모든 원소를 비교하여 가장 작은 값을 찾습니다.
3.교환: 찾은 최소값을 기준 위치에 있는 값과 교환합니다.
4.반복: 리스트의 끝까지 위의 과정을 반복하여 정렬을 완료합니다.

int[] arr = {7, 6, 2, 4, 3, 9, 1};

private static void sort(int[] arr) {
    for (int i = 0; i < arr.length; i++) { // 1. 기준 위치 선택
        int standard = i;
        for (int j = i + 1; j < arr.length; j++) { // 2. 최소값 탐색
            if (arr[j] < arr[standard]) standard = j; // 3. 기준 위치 갱신
        }
        // 4. 교환
        int temp = arr[standard];
        arr[standard] = arr[i];
        arr[i] = temp;

        print(arr);
    }
}

private static void print(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

 

실행 결과

1단계: 1 6 2 4 3 9 7
2단계: 1 2 6 4 3 9 7
3단계: 1 2 3 4 6 9 7
4단계: 1 2 3 4 6 9 7
5단계: 1 2 3 4 6 9 7
6단계: 1 2 3 4 6 7 9
7단계: 1 2 3 4 6 7 9

 

선택 정렬의 시간 복잡도

비교 횟수: n(n−1)/2n(n-1)/2n(n−1)/2 (n개의 원소가 있을 때)

시간 복잡도: O(N2N^2N2)

공간 복잡도: O(NNN)

장점

알고리즘이 단순하여 이해하기 쉽다/
교환 횟수가 적어서 비교적 적은 횟수의 교환으로 정렬을 수행할 수 있다.
추가적인 메모리 공간이 필요하지 않음.

단점

시간 복잡도가 O(N2N^2N2)로, 큰 데이터셋에 비효율적
불안정 정렬, 즉, 동일한 값의 원소가 있을 때, 정렬 전후에 그 상대적 순서가 변경될 수 있음.

 

선택 정렬은 이해하기 쉽고 구현이 간단하여 교육 목적으로 자주 사용되지만, 실제 대규모 데이터를 다룰 때는 효율성 면에서 한계가 있습니다. 따라서 더 효율적인 알고리즘(예: 퀵 정렬, 합병 정렬)이 실제 응용에서 주로 사용됩니다

 

선택 정렬은 구현이 간단하고 이해하기 쉽지만, 대규모 데이터를 다룰 때는 효율성 면에 한계가 있음,

더 효율적인 알고리즘은 퀵정렬, 병합정렬,  내일은 거품정렬에 대해 다시 보려고 한다.