계발자 블로그
[알고리즘] 버블정렬 본문
버블정렬(Bubble Sort)이란 ?
버블정렬은 서로 인접한 두 수를 검사하여 정렬하는 알고리즘입니다.
9 8 7 3 2 5 4 1 6 이런 배열이 있다면
8 9 7 3 2 5 4 1 6
8 7 9 3 2 5 4 1 6
8 7 3 9 2 5 4 1 6
...
8 7 3 2 5 4 1 9 6
8 7 3 2 5 4 1 6 9 이렇게 가장 큰 수가 맨 뒤로 가게 됩니다.
그럼 그 다음부터는 8번째 원소 까지만 정렬을 해줍니다.
public int[] solution(int n, int[] arr) {
for(int i=0; i<n; i++) {
for(int j=0; j<n-i-1; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
return arr;
}
길이가 n인 배열 arr을 입력 받았을 때 버블정렬 하는 코드입니다.
버블정렬의 시간복잡도는 선택정렬과 같은 O(N^2)입니다.
하지만 버블정렬은 자리바꿈이 계속해서 일어나기 때문에
대표적인 정렬 알고리즘 중 가장 느립니다.
'Algorithm' 카테고리의 다른 글
유클리드 호제법 최대공약수 최소공배수 구하기 (0) | 2022.06.23 |
---|---|
[알고리즘] 삽입정렬 (0) | 2022.05.18 |
[알고리즘] 선택정렬 (0) | 2022.05.17 |
[알고리즘] 에라토스테네스의 체 (0) | 2022.05.16 |
[알고리즘] BFS(Breadth-First Search) 너비 우선 탐색 (0) | 2022.04.20 |