BubbleSort(버블정렬) - JAVA
BubblSort의 개념을 간단하게 알아보고, java
로 구현해보자.
거품 정렬이란?
-
두 인접한 원소를 검사하며 정렬하는 알고리즘
-
가장 단순한 정렬 알고리즘이지만, 시간복잡도가
O(N^2)
으로 상당히느리다.
거품 정렬 과정
인접한 두 원소를 비교하면서 큰 값이 작은값보다 뒤에 위치하도록 정렬한다.
시뮬레이션
[3,4,1,6,7,5]
리스트를 BubbleSort로 정렬해보자.
- 뒤에서부터 정렬을 완성시킨다.
-
매번 첫원소부터 비교하면서, 인접한 원소보다 크다면 뒤에 위치하도록
SWAP
해준다. 3<4
이므로 건너뛴다.
4>1
이므로SWAP
한다.
4>6
이므로 건너뛴다.
6>7
이므로 건너뛴다.
5<7
이므로SWAP
한다.
이제, 한 STEP
이 끝났다. 위의 과정을 list
의 길이만큼 반복하면 오름차순 정렬이 완료된다.
- 이어서 정렬 해보자.
1>3
이므로SWAP
해준다.
3<4
이므로 건너뛴다.
4<6
이므로 건너뛴다.
6>5
이므로SWAP
한다.
- 정렬이 완료되었다.
시간복잡도(Time Complexity)
O(N^2)
구현
public class bubbleSort {
static void bubbleSort(int[] list){
for(int i=0;i<list.length-1;i++){
for(int j=1;j<list.length-i;j++){
if(list[j]<list[j-1]){
int tmp=list[j];
list[j]=list[j-1];
list[j-1]=tmp;
}
}
}
}
public static void main(String[] args){
int[] list={3,4,1,6,7,5};
bubbleSort(list);
}
}
Leave a comment