서로 인접한(바로 옆) 두 원소(인덱스)를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드(값)를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
입력을 막하면 CPU의 효율은 좋지만 메모리 효율은 떨어짐.
정렬은 목적은 자료를 찾는 효율이 좋아짐.
- 5,6,9,10,15,3,10 …..
값이 정렬이 되어있지 않을 때, 10을 찾는다면 처음부터 하나하나 찾는다. 10을 찾아도 뒤에 값이 있을 수 있기 때문전체 자료를 탐색해야 한다.
- 5,6,9,10,15,3, ….. primary key
값이 정렬되어 있지 않아도 값이 중복되지 않다면 비교적 탐색이 쉬워진다. 다만 처음부터 찾아야 한다.
- 3,5,6,9,10,1…….
만약 값이 정렬이 되어있다면 2진 탐색(탐색 범위를 절반씩 좁혀가며 찾는 방식) 이 가능하다.
중복되어 있어도 정렬되어 있다면 중간에 탐색을 멈출 수 있다.
int[] arr = {5, 8, 2, 4, 3};
배열에 무작위의 5개 숫자가 있다. 이 숫자를 정렬하기 위해서는 우선 arr[0] 과 arr[1] 자리 부터
교환할 수 있어야 한다.
int[] arr = {5, 8}; int temp; / temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
자료 위치를 교환하는 스왑 코드
새로운 변수 temp가 있어야 교환이 가능하다.
이제 5개로 배열을 정렬해보자
public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; int temp; for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "\t"); } }
버블정렬의 특징
- 버블정렬을 하게 되면 가장 큰 수가 제일 뒤로 온다.
- 1번 정렬이 끝날 때 n-1 번의 숫자 비교가 일어난다.
- 회전의 횟수는 n-1번 일어난다.
이제 위의 코드를 복사해서 반복해보자
public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; int temp; for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < arr.length - 2; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < arr.length - 3; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < arr.length - 4; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "\t"); } }
순서대로 정렬이 완료가 되었다.
이제 공통된 부분을 반복문으로 변환하자.
달라지는 부분은 반복문이 1회, 2회 실행되면서 4번, 3번 숫자가 줄어든다.
이를 변수 k로 표현했다.
public class BubleTest08 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; int temp; for (int k = 1; k < N; k++) for (int i = 0; i < N - k; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } for (int i = 0; i < N; i++) { System.out.print(arr[i] + "\t"); } } }
버블정렬이 완료가 되었다. 이제 배열의 값과 크기를 다르게 설정해도 정렬이 완료된다.
int[] arr = {5, 8, 2, 4, 3, 10, 50, 15};
Share article