다음글을 참고하여 작성하였습니다.
[알고리즘] 거품 정렬 - Bubble Sort (Python, Java)
거품 정렬
상황별, 알고리즘별 정렬 과정과 속도를 애니메이션으로 볼 수 있는 사이트
Sorting Algorithms Animations
Sorting(정렬) Algorithm : 일정한 순서에 따라 열거하는 알고리즘
오늘은 그 중 거품정렬에 대해 알아보겠다.
원투쓰리포 버블버블
거품정렬이란?
버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬이다. 한 번 정렬을 할 때마다 맨 마지막 인덱스에 가장 큰 수가 위치하므로 정렬을 거듭할수록 정렬할 범위가 줄어든다는 특징이 있다.
거품정렬 진행 예시
*값(인덱스)
[6, 4, 9, 3, 1] (입력)
6과 4 비교 후, Swap -> [4, 6, 9, 3, 1]
6과 9 비교, 9가 더 큰 값이므로 그대로 -> [4, 6, 9, 3, 1]
9와 3 비교 후, Swap -> [4, 6, 3, 9, 1]
9와 1 비교 후, Swap -> [4, 6, 3, 1, 9]
[4, 6, 3, 1, 9]
python 코드로 거품정렬 구현하기
def bubble_sort(arr):
#arr의 맨 마지막 인덱스부터 0까지, 1씩 감소
for i in range(len(arr)-1, 0, -1)
#0부터 i-1까지 반복
for j in range(i):
#직전 인덱스의 값이 다음 인덱스의 값보다 클 경우
if arr[j] > arr[j+1]:
#교환
arr[j], arr[j+1] = arr[j+1], arr[j]java 코드로 거품정렬 구현하기
public class Bubble {
public static void bubbleSort(int[] arr) {
for(int i = arr.length -1; i > 0 ; i--) {
for(int j = 0; j < i; j++) {
if(arr[j]>arr[j+1]) {
int temp = arr[j]; #*
arr[j] = arr[j+1]; #*
arr[j+1] = arr[j]; #*
}
}
}
}
//만일 swap을 모듈화 한다면... 별표한 위 세줄의 코드를
//swap(arr, j, j+1)로 대체할 수 있다.
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}거품정렬은 swap의 실행 여부로 정렬되지 않은 값과 정렬된 값을구분할 수 있기 때문에 최적화 할수 있는 가능성이 있습니다.
예를들면
1. 이전 패스에서 swap이 한 번도 일어나지 않은 경우
- 마지막으로 swap이 있던 인덱스를 기억해둘 경우
이전 패스에서 swap이 한 번도 일어나지 않은 경우에 대한 python 코드
def bubble_sort(arr):
for i in range(len(arr)-1, 0, -1):
swapped = False
for j in range(i):
if arr[j] > arr[j+1]:
arr[j]m arr[j+1] = arr[j+1], arr[j]
#한 패스에 한 번이라도 swap이 일어날 경우에 표시
swapped = True
if not swapped:
break이전 패스에서 swap이 한 번도 일어나지 않은 경우에 대한 java 코드
public class Bubble {
public static void sort(int[] arr) {
for (int i = arr.length-1; i > 0; i--) {
boolean swapped = false;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j, j+1);
swapped = true
}
}
if (!swapped) breal;
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}마지막으로 swap이 있던 인덱스를 기억해둘 경우에 대한 python 코드
def bubble_sort(arr):
end = len(arr) - 1
while end > 0:
last_swap = 0
for i in range(end):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
last_swap = i
end = last_swap마지막으로 swap이 일어난 인덱스를 기억해두는 경우, 이미 정렬된 데이터는 신경쓰지 않을 수 있다. 0부터 마지막으로 스왑이 일어난 인덱스 이전까지만 정렬 알고리즘을 실행하면 되겠다.
public class Bubble {
public static void bubbleSort(int[] arr) {
int end = arr.length - 1;
while (end > 0) {
int last_swap = 0;
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i+1]) {
swap(arr, i, i+1);
last_swap = i;
}
}
end = last_swap;
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
- 위 블로그의 구현코드도 참고하였는데, 혼자 생각했을때는 인덱스를 거꾸로 줄여나갈 생각을 못 했는데, 정렬이 진행되면서 전체 인덱스의 마지막부터 하나씩 줄여나가는 과정을 보니 코드도 훨씬 깔끔하고, 변수도 추가로 할당하지 않아도 돼서 신박하다고 생각했다.
