1. 버블 정렬
(1) 정의
인접한 원소끼리 비교 후에, 정렬되어 있지 않다면, 두 원소의 위치를 swap한다.
이런 식으로 정렬하게 되면 배열 혹은 리스트의 오른쪽부터 값들이 정렬되어 쌓이게 된다.
예시
사진 출처: 블로그
(2) 시간 복잡도
$$
O(n^2)
$$
2. 선택 정렬
(1) 정의
정렬이 되어있지 않은 범위 내에서의 최소값 혹은 최대값을 맨 오른쪽 혹은 맨 왼쪽으로 몰아넣는다.
이후 정렬되지 않은 부분 내의 최소값 혹은 최대값을 다시 찾아 아까 몰아넣은 곳으로 또 몰아넣는다.
밑의 사진은 오름차순 정렬을 선택 정렬로 행한 것이고, 최소값을 오른쪽으로 몰아넣었다.
사진 출처: 블로그
(2) 시간 복잡도
$$
O(n^2)
$$
3. 삽입 정렬
(1) 정의
- 정렬된 범위 내에 현재 값을 삽입할 적절한 위치를 찾는다. (오름 차순, 내림차순일 경우, 범위 내 원소와 현재 값 크기 비교)
- 삽입할 위치에 현재 값을 삽입한다. (정렬된 영역이 +1 증가한다.)
- 정렬되지 않은 영역의 값을 가지고 위의 과정을 반복한다.
사진 출처: 블로그
(2) 시간 복잡도
$$
O(n^2)
$$
'알고리즘 > 알고리즘-이론' 카테고리의 다른 글
코딩 테스트 구현 스킬 모음 (Java) (0) | 2024.07.04 |
---|---|
자료 구조 완벽 정리! (0) | 2024.06.23 |
JAVA 2차원 배열 (matrix) 회전 공식 완벽 정리! (0) | 2024.06.14 |
시간 복잡도의 개념과 코딩 테스트에서의 활용법 (0) | 2024.06.13 |
🖤 알고리즘 이론 - 순열과 조합 [JAVA] (0) | 2024.04.07 |