공부 일지/개인 공부 기록용
자바공부 16일차
Joshbla
2022. 5. 9. 15:41
2022/05/08
- 백준 단계별 10-5 ~ 11-3
- 정렬
1. 선택 정렬 (Selection Sort)
가장 원시적인 방법으로 for문으로 최소값을 찾아서 첫번째 위치에 넣고
그 다음 최소값을 그 다음 위치에 넣는 것을 반복.
시간복잡도는 O(N²)로 안좋은 편
2. 버블 정렬 (Bubble Sort)
배열 내에서 서로 붙어있는 숫자끼리 비교하고 큰값을 뒤로 보내준다.
시간복잡도는 O(N²)
3. 삽입 정렬 (Insertion Sort)
선택정렬에 비해서 시간측면에서 효율적, 필요할 때만 위치를 바꾸므로
데이터가 거의 정렬되어 있을 때 효과적이다.
항상 오름차순으로 정렬된다.
시간복잡도는 O(N²)이다. 최상의 경우 O(N)의 복잡도를 지닌다
4. 퀵 정렬
가장 많이 사용한다. 피벗-파티션의 과정을 거친다.
평균 시간복잡도는 O(NlogN)이고 최악의 경우 O(N²)이다.
5. 계수 정렬 (Count Sort)
특정 조건 아래서 매우빠른 알고리즘
모든데이터가 양의 정수, 데이터 개수가N, 데이터 중 최댓값이 K일 때
수행시간 O(N+K)가 보장된다.
일반적으로 데이터의 최소,최대의 차가 1,000,000을 넘지 않을 때 효과적
- Arrays.sort는 퀵정렬에 해당하고 평균nlogn, 최악n2
Collections.sort는 타임정렬에 해당한다. 평균, 최악nlogn
| 정렬 종류 | 시간 복잡도 | 공간 복잡도 | ||
| 평균(Average) | 최선(Best) | 최악(Worst) | ||
| 선택 정렬 | O(n2) | O(n2) | O(n2) | O(n2) |
| 버블 정렬 | O(n2) | O(n2) | O(n2) | O(n) |
| 삽입 정렬 | O(n2) | O(n) | O(n2) | O(n2) |
| 합병 정렬 | O(n×log n) | O(n×log n) | O(n×log n) | O(n×log n) |
| 퀵 정렬 | O(n×log n) | O(n×log n) | O(n2) | O(n×log n) |
| 힙 정렬 | O(n×log n) | O(n×log n) | O(n×log n) | O(n×log n) |
| 쉘 정렬 | O(N^1.25) | O(N^1.25) | O(N^1.25) | O(n) |
| 기수 정렬 | O(dn) | O(dn) | O(dn) | |