1. 알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다. 추상적인 명령은 XXX. 함수를 절차적으로 만들면 알고리즘이 된다.
2. 버블 정렬이란?
- 오름차순을 기준으로 정렬
- 서로 인접한 두 원소(=인접한 번지)를 비교하고, 검사하여 정렬하는 알고리즘
- 만약 인접한 2개의 값을 비교해서 (크기가) 순서대로 되어있지 않으면 두 원소를 교환하는 방식으로 정렬을 수행한다. 정렬이 필요한 모든 원소에 대해 이러한 과정을 반복하면서 전체적으로 정렬될 때까지 진행한다.
- 0번째 인덱스랑 1번째 인덱스를, 1번째 인덱스랑 2번째 인덱스를, 2번째 인덱스랑 3번째 인덱스를 ….. 이런 식으로 n번째만큼 비교해서 마지막 -1번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬.
- 선택 정렬과 기본 개념이 유사하다.
- 버블 정렬은 간단하지만 효율성이 낮아 대규모 데이터에는 적합하지 않다.
숫자를 연속적으로 저장할 때는 벡터에 저장한다.
’인접하다’는 뜻은 번지수가 바로 옆에 있다는 말.
3. 버블 정렬 예시
1회전
N = [ 5, 8, 2, 4, 3 ] (1round) 5, 8 비교 - 변화없음 (2round) 8, 2 비교 - 변화 있음. (5, 2, 8, 4, 3) (3round) 변화된 값을 봄 - 8, 4 비교 - 변화 있음. (5, 2, 4, 8, 3) (4round) 변화된 값을 봄 - 8, 3 비교 - 변화 있음. (5, 2, 4, 3, 8)
총 5개의 숫자 중, 4번 돌았다. (1회전 = 전체길이 -1) 1회전 했으나, 2, 3, 4, 5, 8 이 안됐으니 완성된 건 아님. 아직 끝나지 않았다... 2, 3, 4, 5, 8 순으로 만드는게 바로 '버블 정렬'
2회전
1회전 (4바퀴)가 끝나면
[ 5, 2, 4, 3, 8 ]로 2회전 시작!
(1r) 5, 2 비교 - (2, 5, 4, 3, 8) (2r) 5, 4 비교 - (2, 4, 5, 3, 8) (3r) 5, 3 비교 - (2, 4, 3, 5, 8) 2회전 때는 총 3번 돈다. (2회전 = 전체길이 -2)
3회전
2회전 (3바퀴)가 끝나면
[ 2, 4, 3, 5, 8 ]로 3회전 시작!
(1r) 2, 4 비교 - 변화 없음 (2r) 4, 3 비교 - (2, 3, 4, 5, 8) 3회전때는 총 2번 돈다. (3회전 = 전체길이 -3)
인간의 눈으로 봤을 때는 종료된게 맞지만, 컴퓨터는 2, 3을 비교해보지 않았으니 끝나지 않는다.
4회전
3회전 (2바퀴)가 끝나면
[ 2, 3, 4, 5, 8 ]로 4회전 시작!
(1r) 2, 3 비교 - 변화 없음 4회전때는 총 1번 돈다. 2, 3, 4, 5, 8이 된 걸 확인. - 종료!
버블 정렬은
한 번 돌 때 가장 큰 수가 뒤로 가는 걸 알 수 있다. = 가장 끝에 큰 수를 두는 게 반복된다.
회전수 : N - 1
1회전 비교 횟수 : N - 1
2회전 비교 횟수 : N - 2
3회전 비교 횟수 : N - 3
4회전 비교 횟수 : N - 4
*비교할 데이터가 5개 있으면 4번만 비교
4. 간단한 코드로 TEST
TEST
package ex03.test; public class BubbleTest01 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; //final이 붙은 변수는 대문자로 입력. (자바 문법임) //첫번째 도전. 4바퀴 돌기 for (int i = 0; i < N - 1; i++) { // System.out.println("몇 번 돌지?"); } //두번째 도전. 4바퀴 도는데, 1회전때 4바퀴 도는 내부 for문 만들기 //두번째 도전. 4바퀴 돌고, 내부적으로 4바퀴 돌기. for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1; j++) { System.out.println("몇 바퀴 돌까?"); } System.out.println(); } } }
package ex03.test; public class BubbleTest02 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; //세번째 도전. 4바퀴 돌고, 내부적으로 (4,3,2,1) 바퀴 돌기. for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N-i-1; j++) { System.out.println("몇 바퀴 돌까?"); } System.out.println(); } } }
final이 붙은 변수는 대문자로 입력. (자바 문법임)
5. 버블 정렬 코드
1회전을 코드로
package ex03.test; public class BubbleTest04 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; int temp; if(arr[0] > arr[1]){ temp = arr[0]; arr[0] = arr[1]; arr[1] = temp; } if(arr[1] > arr[2]){ temp = arr[1]; arr[1] = arr[2]; arr[2] = temp; } if(arr[2] > arr[3]){ temp = arr[2]; arr[2] = arr[3]; arr[3] = temp; } if(arr[3] > arr[4]){ temp = arr[3]; arr[3] = arr[4]; arr[4] = temp; } for (int i = 0; i < 5; i++) { System.out.print(arr[i] + " "); } } }
2회전을 코드로
package ex03.test; public class BubbleTest05 { 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 < N-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 < N; i++) { System.out.print(arr[i] + " "); } } }
간략화 된 코드 (자동 회전)
package ex03.test; public class BubbleTest06 { public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; final int N = arr.length; int temp; for (int loop = 1; loop < N; loop++) { for (int i = 0; i < N-loop; 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] + " "); } } }
package ex04; (내가 한거) public class Bubble01 { public static void main(String[] args) { int[] arr1 = {5, 8, 2, 10, 3, 0, 30, 55, 22, 19, 6, 80, 77, 32, 11}; final int N = arr1.length; int temp; //5, 2, 8, ,10, 3 //5, 2, 8, 3, 10 for (int j = 0; j < N - 1; j++) { for (int i = 0; i < N - 1 - j; i++) { if (arr1[i] > arr1[i + 1]) { temp = arr1[i]; arr1[i] = arr1[i + 1]; arr1[i + 1] = temp; } } } for (int i = 0; i < N; i++) { System.out.print(arr1[i] + " "); } } }
* 외부의 첫 번째 루프(
loop)는 한 번의 전체 패스(한 회전)를 나타내며,
* 내부의 두 번째 루프는 인접한 두 원소를 비교하고 필요에 따라 교환하는 역할을 한다.
(=0번 인덱스랑 1번 인덱스를, 1번 인덱스랑 2번 인덱스를, 2번 인덱스랑 3번 인덱스를 비교하는 역할)외부 루프 = 전체 회전수 (전체 범위)니까, N - 1 내부 루프 = 실제로 정렬을 하는 부분. 처음 비교할 땐 4번, 2번째 비교할 때는 3번, 3번째 비교할 때는 2번... N-i-1 최종 위치가 한 번 돌 때마다 확정되니까 회전수가 점점 줄어드는 것. 여기서 i는 위치가 확정된 애들의 개수, -1은 최초 회전수가 N-1(4회 회전)하니까
클래스랑 메소드가 같이 있는 형식 (아래 예시 참조)은 클래스명 생략 가능.
* bubble(arr); 이렇게 해도 호출이 가능하다.
package ex03; public class BubbleEx01 { static void bubble(int[] arr) { final int N = arr.length; int temp; for (int loop = 1; loop < N; loop++) { for (int i = 0; i < N-loop; 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] + " "); } } public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; bubble(arr); System.out.println(); int[] arr2 = {5, 8, 2, 4, 3, 10, 500, 7, 6}; BubbleEx01.bubble(arr2); } }
Share article