선택정렬이란 배열에서 먼저 원소를 넣을 위치를 정해놓고, 그 위치에 어떤 원소를 넣을지 하나하나 탐색하면서 정렬하는 알고리즘이다. 예를 들어 아래와 같은 배열이 있으면
8 4 6 5 3 2 1 9 7 먼저 첫번째 인덱스부터 위치를 선택하여 가장 작은 값인 1을 찾는다. 이후 그 인덱스의 숫자와 우리가 넣어줄 숫자의 위치를 바꾼다. 이를 차례대로 진행하면 먼저 1과 8을 바꿔준다. 1 4 6 5 3 2 8 9 7 이후 다시 4와 2를 바꿔준다. 1 2 6 5 3 4 8 9 7 같은 방법으로 순차적으로 진행하면 1 2 3 5 6 4 8 9 7 ........ 1 2 3 4 5 6 7 8 9 이를 c코드로 하면 아래와 같다.#include <iostream>
using namespace std;
int main()
{
int a[100], n, idx, i, j, tmp;
// a는 배열, n은 입력받을 index의 개수
scanf("%d",&n);
for(i =0; i<n; i++){
scanf("%d",&a[i]);
}
for(i=0; i<n-1; i++){
idx = i; //먼저 바꿔줄 위치를 지정
for(j= i+1; j<n; j++){
if(a[idx]>a[j]) idx = j; //이후 가장 작은 값의 idx를 찾기
}
// min값의 index를 발견하면 이를 swap
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
}
for(i=0; i<n; i++){
printf("%d ",a[i]);
}
return 0;
}
데이터의 갯수가 n이라고 하면, 총 루프의 횟수는 n(n-1)/2 이므로 시간복잡도는 O(n^2) 이다.
장점
단점