Contents
버블 정렬(bubble sort)버블 정렬(bubble sort)
목표 : 오름차순을 기준으로 정렬
원본 데이터 (5, 8, 2, 4, 3) N
알고리즘 작성 해보기
1회전(4바퀴)
(1) 5, 8 비교 (변화 없음)
(2) 8, 2 비교 (5, 2, 8, 4, 3)
(3) 8, 4 비교 (5, 2, 4, 8, 3)
(4) 8, 3 비교 (5, 2, 4, 3, 8)
1회전을 수행하면 정렬이 완료되지는 않았지만 가장 끝 수가 맨 뒤로 이동
2회전(3바퀴)
(1) 5, 2 비교 (2, 5, 4, 3, 8)
(2) 5, 4 비교 (2, 4, 5, 3, 8)
(3) 5, 3 비교 (2, 4, 3, 5, 8)
2회전을 수행하면 그 다음으로 큰 수가 맨 뒤로 이동, 바퀴 수는 한 바퀴 줄어든다
3회전(2바퀴)
(1) 2, 4 비교 (2, 4, 3, 5, 8)
(2) 4, 3 비교 (2, 3, 4, 5, 8)
4회전(1바퀴)
(1) 2, 3 비교 변화 없음
회전수 : N-1
n회전 비교 횟수 : N-n
바퀴수가 줄어드는 코드 작성
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++) {
for (int j = 0; j < N-i-1; j++) {
System.out.println("몇바퀴 돌까?");
}
System.out.println();
}
// 두번째 4바퀴 도는데, 1회전때 4바퀴도는 내부 포문 만들기
}
}자리를 바꾸는 스왑코드 작성
package ex03.test;
public class BubbleTest03 {
public static void main(String[] args) {
int[] arr = {4,3};
// 스왑코드
int temp;
temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
System.out.println(arr[0]);
System.out.println(arr[1]);
}
}1회전 코드 작성해보기
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문으로 다시 작성 해보기
package ex03.test;
import java.util.Arrays;
public class BubbleTest04 {
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;
System.out.println(Arrays.toString(arr));
}
}
}
}바퀴수가 줄어드는 코드와 합쳐보기
최종
package ex03.test;
import java.util.Arrays;
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 j = 0; j < N-1; j++) {
for (int i = 0; i < N-j - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
버블 정렬이 되어 나옴
정렬의 목적
Binary Search를 하여 빠른 검색이 가능
중복된 데이터 들을 찾을 때 동일한 데이터가 나오지 않는 순간 멈출 수 있다.
Share article
