CS(Computer Science)/Algorithm
기본 정렬 알고리즘(선택,삽입)-알고리즘07
용준한
2023. 8. 15. 15:08
Selection Sort(선택정렬)
- Inplace 정렬 알고리즘 중 하나(추가 메모리 필요X)
- n번째 index에 n번째로 작은 원소를 삽입한다.
알고리즘: 각 루프 마다:
- 최대 원소를 찾는다.
- 최대 원소를 가장 오른쪽의 원소와 교환한다.
- 1~2 를 반복하는데 1 에서 찾고 옮긴 원소를 제외하고 반복한다.
시간복잡도 및 의사코드:
//n은 배열 A의 크기 cost times
for j=1 ~ j=n-1 n
smallest=j n-1
for i=j+1 ~ i=n Σ(n-j+1)
if A[i] <= A[smallest] Σ(n-j)
smallest=i Σ(n-j)
swap(A[j],A[smallest]) n-1
T(n) = 모든 연산 시간이 O(n^2) 이므로 O(n^2) 이다. (혹은 for문이 이중으로 겹쳐있으므로)
Insertion Sort(삽입정렬)
- (key)가 두번째 원소부터 시작하는데, 앞의 원소들과 비교하여 삽입할 위치를 찾고 그 위치에 삽입하여 정렬을 완성한다.
알고리즘:
- for i =0~ n : 각 key에 대하여
- key의 앞에 있는 부분들과 비교(if arr[i] 가 앞의 어떤 위치 a 보다 작다면 a에 삽입)
- 삽입할 위치 a를 찾으면, a뒤의 원소들을 한칸씩 뒤로 이동해서 삽입할 자리를 만들고 삽입
시간복잡도 및 의사코드:
의사코드:
는 =2,3,⋯,인 경우에 대해 while루프의 검사가 실행되는 횟수
따라서,
BestCase: 이미 정렬 된 경우
while문의 실행되지 않으므로 위의 식에서 n에 대해 1차식으로 남는다.
따라서 O(n)
WorstCase: 역순으로 정렬 된 경우
각 key에 대해 앞의 모든 원소들가 비교를 해야되므로 while 문은 항상 j-1만큼 연산을 한다.
따라서 O(n^2)
코드 구현(C):
void insertion_sort ( int data[], int n )
{
int i, j, remember;
for ( i = 1; i < n; i++ ) //각 key에 대하여
{
remember = data[(j=i)];
while ( --j >= 0 && remember < data[j] ){ //삽입할 위치를 찾는다
data[j+1] = data[j];
}
data[j+1] = remember;
}
}
장점:
- stable(안정) : 중복된 값을 입력 순서에 맞게 정렬 (mergesort 포스팅 참고)
- 이미 정렬되어 있을 시 효율성이 매우 좋음
단점:
- 원소들의 이동이 많음.
- 정렬이 안되어 있을때 시간이 오래걸림