선택 정렬
간단한 정렬 알고리즘으로, 배열을 정렬하는 과정에서 가장 작은(또는 가장 큰) 요소를 선택하여 정렬된 부분과 교환하는 방식으로 작동합니다.
배열에서 가장 작은 값을 찾고, 그것을 현재 정렬되지 않은 부분의 첫 번째 요소와 교환합니다.
이 과정을 배열의 모든 요소에 대해 반복합니다. 매 반복마다 정렬된 부분이 하나씩 늘어납니다.
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 현재 위치를 최소값의 인덱스로 설정
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 더 작은 값의 인덱스를 찾음
}
}
// 현재 위치와 최소값의 위치를 교환
swap(arr[i], arr[minIndex]);
}
}
// 배열 출력 함수
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "정렬된 배열: ";
printArray(arr, n);
return 0;
}
- 배열의 첫 번째 요소부터 시작합니다.
- 현재 인덱스 이후의 요소 중에서 가장 작은 값을 찾습니다.
- 해당 값을 현재 인덱스 위치의 요소와 교환합니다.
- 다음 인덱스로 이동하여 같은 과정을 반복합니다.
- 배열의 모든 요소에 대해 이 과정을 수행할 때까지 반복합니다.
시간 복잡도는 비효율적입니다.
O(n²) (n은 배열의 크기)입니다 .
최선의 경우에도
O(n²) 입니다.
그냥 보기에는 버블정렬과 크게 다를 바없지만 최선의 경우에도 시간복잡도가 안좋은 그대로입니다.
swap(arr[i], arr[minIndex]) 에서 minIndex가 i라면 즉 같은 위치라면 교환하지 않습니다.
이렇게하면 불필요한 교환을 줄일 수 있다고 합니다.
버블 정렬과 선택 정렬 모두 O(n²) 시간 복잡도를 가지며, 데이터가 많은 경우에는 적합하지 않습니다.
선택 정렬은 교환 횟수가 적고 메모리 오버헤드가 적은 반면, 버블 정렬은 안정성이 있습니다.
swap함수를 항상만들어서사용했었는데 기본함수로 있던걸 처음알았습니다..