1.버블 정렬
- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
[장점]
1. 추가적인 메모리 소비가 작다.
2. 구현이 매우 쉽다.
3. 안정정렬이 가능하다.
[단점]
1. 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.
자세히 보기 https://visualgo.net/en/sorting
Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo
VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitte
visualgo.net
위 알고리즘에서도 볼 수 있듯, 초기 배열에서 원래 해당자리에 맞는 위치지만, 교환과정에서 중간에 한 번씩 맞지 않은 자리임에도 이동하게 된다. 또한 다른 정렬 알고리즘보다 값 교환 과정이 많기 때문에 그만큼 효율성도 떨어져 가장 배우기 쉽고, 구현하기 쉬움에도 사실상 쓰이지 않는 정렬 방법이다.
O(N^2)의 시간 복잡도를 갖는다.
2. 자바로 알고리즘 구현
- 특이점
- n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용한다.
- 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
- 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.
1. for(int index = 0; idex < dataList.size()-1; index++)를 반복
2. swap = false (교환이 되었는지를 확인하는 변수를 두자)
3. 반복문안의 반복문으로 n - 1번 반복하며,
4. 반복문안의 반복문 안에서, if (dataList.get(index2) > dataList.get(index2 + 1)) 이면
5. 데이터를 스왑 하고, Collections.swap(dataList, index2, index2 + 1);
6. 스왑 했음을 체크하기 위해, swap을 true로 놓고,
7. 반복문안의 반복문을 수행 후에도 swap 이 false 이면, 전체 반복을 멈춤 (break)
import java.util.ArrayList;
import java.util.Collections;
public class BubbleSort {
public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
for (int index = 0; index < dataList.size() - 1; index++) {
boolean swap = false;
for (int index2 = 0; index2 < dataList.size() - 1 - index; index2++) {
if (dataList.get(index2) > dataList.get(index2 + 1)) {
Collections.swap(dataList, index2, index2 + 1);
swap = true;
}
}
if (swap == false) {
break;
}
}
return dataList;
}
}
3. 정리
버블 정렬의 경우 사실상 거의 쓰이지 않는 정렬 알고리즘이지만, 반대로 가장 기초적인 정렬 알고리즘이기도 하다. 보통 정렬 알고리즘에 대해 배우면 버블 정렬 알고리즘부터 배울 것이다.
하지만 삽입정렬이나 선택정렬과 같은 O(N2^)의 시간복잡도를 갖는다 하더라도 거품정렬의 교환 횟수가 평균적으로 더 많기 때문에 실질적으로는 삽입, 선택 정렬보다 더 많은 시간이 걸린다.
'Algorithm' 카테고리의 다른 글
[알고리즘] 삽입 정렬 (Insertion Sort) (0) | 2023.01.16 |
---|---|
[알고리즘] 선택 정렬 (Selection Sort) (0) | 2023.01.16 |
[알고리즘] 자료구조: 트리(Tree) (0) | 2023.01.08 |
[알고리즘] 자료구조: 해쉬 (0) | 2022.12.07 |
[알고리즘] 자료구조: 시간복잡도, 공간복잡도 (0) | 2022.12.06 |