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)/2 (n개의 원소가 있을 때)
시간 복잡도: O(N2N^2)
공간 복잡도: O(NN)
장점
알고리즘이 단순하여 이해하기 쉽다/
교환 횟수가 적어서 비교적 적은 횟수의 교환으로 정렬을 수행할 수 있다.
추가적인 메모리 공간이 필요하지 않음.
단점
시간 복잡도가 O(N2N^2)로, 큰 데이터셋에 비효율적
불안정 정렬, 즉, 동일한 값의 원소가 있을 때, 정렬 전후에 그 상대적 순서가 변경될 수 있음.
선택 정렬은 이해하기 쉽고 구현이 간단하여 교육 목적으로 자주 사용되지만, 실제 대규모 데이터를 다룰 때는 효율성 면에서 한계가 있습니다. 따라서 더 효율적인 알고리즘(예: 퀵 정렬, 합병 정렬)이 실제 응용에서 주로 사용됩니다
선택 정렬은 구현이 간단하고 이해하기 쉽지만, 대규모 데이터를 다룰 때는 효율성 면에 한계가 있음,
더 효율적인 알고리즘은 퀵정렬, 병합정렬, 내일은 거품정렬에 대해 다시 보려고 한다.