선택 정렬은 매 차례마다 정렬되지 않은 원소들을 모두 확인하여 각 인덱스에 맞는 원소를 선택하여 해당 인덱스의 원소와 교환해주는 정렬입니다.
매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2)입니다.
그림을 통해 각 순서에 대해 설명하도록 하겠습니다.
- 먼저 가장 작은 값을 첫 번째 값인 15로 지정하고, minimum index를 0으로 놓습니다.
- 그 수의 뒤에 있는 모든 수와 비교하면서, minimum index에 있는 수보다 작은 수일 경우 minimum index를 해당 수의 인덱스로 바꿔줍니다.
- 연산이 끝나면 마지막 수인 1이 minimum index가 되고 해당 수와 처음 인덱스를 바꿔줍니다.
- 첫 번째 수는 제대로 정렬된 수이므로 다음 수인 4를 가장 작은 값으로 지정하고 minimum index를 1로 놓습니다.
- (2),(3)의 과정을 실행합니다. 그러면 가장 작은 수는 3이므로 해당 수와 1번 인덱스의 수를 바꿔줍니다.
이러한 과정은 각각의 인덱스에 맞는 수를 하나하나 찾아가는 연산이라는 것을 알 수 있습니다.
다음은 C++로 선택정렬을 나타낸 것입니다.
더보기
#include <iostream>
using namespace std;
#define MAX 5005
int arr[MAX];
int N;
void Swap(int &a, int &b) {
int temp =a;
a = b;
b = temp;
}
void selection_sort(int *arr, int size) {
for (int i = 0; i < size; i++) {
int minidx = i;
for (int j = i + 1; j < size; j++) {
if (arr[minidx] > arr[j]) {
minidx = j;
}
}
Swap(arr[minidx], arr[i]);
}
}
int main() {
cin>>N;
for(int i=0; i < N; i++) {
cin>>arr[i];
}
selection_sort(arr, N);
for (int i = 0; i < N; i++) {
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
다음은 Java 입니다.
더보기
import java.util.*;
public class Main {
static void selection_sort(int arr[], int size) {
for (int i = 0; i < size; i++) {
int minidx = i;
for (int j = i + 1; j < size; j++) {
if (arr[minidx] > arr[j]) {
minidx = j;
}
}
int temp = arr[minidx];
arr[minidx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[5005];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
selection_sort(arr, n);
for (int i = 0; i < n; i++) {
System.out.print(String.valueOf(arr[i]) + ' ');
}
System.out.println("");
}
}
다음 시간엔 삽입 정렬에 대해 알아보겠습니다.