Search

Algorithms | 버블, 선택, 삽입 정렬 정리

Date
2024/07/30
category
Algorithms
Tags
algorithms
c++

1. 버블 정렬

1.1. 동작

1.2. 특징

•
큰 값 부터 정렬된다
•
원소 하나를 정렬하기 위해서 swap이 여러 번 일어날 수 있다
•
stable 정렬이다

1.3. 성능

•
최상의 경우 시간 복잡도
◦
이미 정렬된 상태일 때 최상의 경우
◦
정렬되지 않은 영역을 순차적으로 탐색 후 swap이 한번도 일어나지 않으면 정렬 종료
◦
원소 개수 nn이 증가할 때 수행 시간이 증가한다
◦
시간 복잡도: O(n)O(n)
•
최악의 경우 시간 복잡도
◦
내림차순으로 정렬된 경우
◦
인덱스 kk의 자리를 정렬된 상태로 만들기 위해선 kk번의 비교가 필요하다
◦
마지막 인덱스 자리부터 인덱스 1번 자리까지 정렬된 상태로 만들면 모든 원소가 정렬된다
◦
원소 개수를 nn이라고 할 때 비교 횟수는
∑k=1n−1k=n(n−1)2\sum_{k=1}^{n - 1}k = \frac{n(n-1)}{2}
◦
시간 복잡도: O(n2)O(n^2)
•
공간 복잡도
◦
원소 개수가 늘어나도 필요한 메모리 크기는 같다
◦
공간 복잡도: O(1)O(1)

2. 선택 정렬

2.1. 동작

2.2. 특징

•
작은 값부터 정렬된다
•
한 원소를 정렬할 때 swap은 한 번만 일어난다
•
unstable 정렬이다
◦
ex) (2,a),(2,b),(1,c)(2, a), (2, b), (1, c)일 때 숫자 기준으로 선택 정렬하면 (1,c),(2,b),(2,a)(1, c), (2, b), (2, a)가 된다

2.3. 성능

•
시간 복잡도
◦
최솟값을 찾을 때 정렬되지 않은 원소들 모두 탐색해야 한다
◦
원소가 이미 정렬된 상태여도 그 원소가 정렬된 상태인지 확인하기 위해 최솟값 탐색을 한다 → 최악의 경우와 최상의 경우 시간 복잡도가 같다
◦
원소 개수가 nn개 일 때 비교 횟수는 (n−1)+(n−2)+...+1(n- 1) + (n -2) + ... + 1 이므로
∑k=1n−1k=n(n−1)2\sum_{k=1}^{n - 1}k = \frac{n(n-1)}{2}
◦
시간 복잡도: O(n2)O(n^2)
•
공간 복잡도
◦
원소 개수가 늘어나도 필요한 메모리 크기는 같다
◦
공간 복잡도: O(1)O(1)

3. 삽입 정렬

3.1. 동작

3.2. 특징

•
작은 값부터 정렬된다
•
stable 정렬이다

3.3 성능

•
최상의 경우
◦
이미 원소들이 정렬된 경우
◦
각 원소를 정렬된 자리에 있는지 한번 씩만 확인 후 수행 종료
◦
원소 개수 nn이 증가하면 수행 시간이 증가
◦
시간 복잡도: O(n)O(n)
•
최악의 경우
◦
내림차순으로 정렬된 경우
◦
원소 개수가 nn개이고 인덱스 1번부터 n−1n - 1번 원소의 삽입 위치를 찾기 위한 총 비교 횟수는 1+2+3+...+(n−1)1 + 2 + 3 + ... + (n - 1)이므로
∑k=1n−1k=n(n−1)2\sum_{k=1}^{n - 1}k = \frac{n(n-1)}{2}
◦
시간 복잡도: O(n2)O(n^2)
•
공간 복잡도
◦
원소 개수가 늘어나도 필요한 메모리 크기는 같다
◦
공간 복잡도: O(1)O(1)