반응형
void bubbleSort(vector<int>& v, int n) {
int i, j,temp;
for (i = n-1; i > 0;i--) {// n-1 완료되면 가장큰수 배열의 맨 끝에 위치 다음 n-2,n-3...,1
for (j = 0;j < i;j++) {
if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
}
}
}
for 문 한번 돌때마다 가장 큰 수가 맨 뒤에 위치하게 된다.
따라서, 매 회 n-i 순회 하며
안정성 : 안정된 정렬 (인접한 레코드끼리만 자리바꿈)
제자리성 : 제자리 정렬
평균시간복잡도 = O(n2)
최악시간복잡도 = O(n2) (역순으로 정렬)
알고리즘
1. 첫번째 for 에서 i 의 크기를 n-1 부터 순회
2. 두번째 for 에서 j 를 i 까지 순회하면서 v[j] > v[j+1] 이면 swap
반응형
'Lecture > Algorithm' 카테고리의 다른 글
[정렬] 셸 정렬 ( Shell Sort ) (0) | 2021.05.09 |
---|---|
[정렬] 삽입정렬 ( Insertion Sort ) (0) | 2021.05.09 |
[정렬] 선택정렬( Selection sort ) (0) | 2021.05.08 |
[백준 1708번] 컨벡스헐 (0) | 2021.05.03 |
[기하] 단순 폐쇄 경로 찾기 (0) | 2021.04.30 |