티스토리 뷰
반응형
소개
- 배열의 인접한 두 요소 값들을 비교하여 정렬한다.
과정
코드
- \(j\) 인덱스 값이 \(j + 1\) 인덱스 값보다 크다면 두 숫자의 위치를 바꿔준다.
- 첫 번째 for문이 한 번 종료될 때마다 가장 마지막 인덱스에 숫자가 하나씩 정렬된다.
public static void main(String[] args) {
int[] nums = { 6, 7, 2, 8, 1, 4 };
int len = nums.length;
for (int i = 0; i < len - 1; ++i) {
for (int j = 0; j < len - i - 1; ++j) {
if (nums[j] > nums[j + 1])
Swap(nums, j, j + 1);
}
}
}
결과
계산 복잡도
Time Complexity : for문 두 개가 지배하며, \((N-1) + (N -2 ) + ... + 1 = \frac{(N-1)*(N)}{2}\)
- Best : \(O(N^2)\)
- Average : \(O(N^2)\)
- Worst : \(O(N^2)\)
Space Complexity : \(O(1)\)
반응형
'Algorithm > Sort' 카테고리의 다른 글
힙 정렬 (Heap Sort) (2) | 2020.12.24 |
---|---|
병합 정렬 (Merge Sort) (0) | 2020.12.24 |
셸 정렬 (Shell Sort) (0) | 2020.12.24 |
삽입 정렬 (Insertion Sort) (0) | 2020.12.24 |
선택 정렬 (Selection Sort) (0) | 2020.12.24 |
댓글