![[자바 (JAVA)] 20. 버블 정렬](https://image.inblog.dev?url=https%3A%2F%2Fsource.inblog.dev%2Ffeatured_image%2F2025-02-11T15%3A38%3A53.184Z-475086b0-f2ed-4026-ae23-282cdac83bd9&w=3840&q=75)
{5,4,3,2,1} 배열 크기 N
한 회전마다 마지막 index의 값을 찾는다.
전체 회전수는 allRound = N-1이다.
회전마다 반복되는 count는 N-1, N-2, N-3, N-4
STEP 1.
마지막 index 값을 찾는 한 번의 회전만 테스트
package algo;
// {1,2,3,5,4}
public class Bubble02 {
public static void main(String[] args) {
// 인접한 두 수를 비교하고 교환
int[] arr = {5, 3, 1, 2, 4};
// 회전수는 N-1
// 1회전 (목표 : 4번지의 값을 정하는 것)
// 1-1 ---------------------------------------
if (arr[0] > arr[1]) { // 교환 조건
int temp = arr[1]; // temp = 3;
arr[1] = arr[0];
arr[0] = temp;
}
// {3,5,1,2,4}
// 1-2 ----------------------------------------
if (arr[1] > arr[2]) { // 교환 조건
int temp = arr[2];
arr[2] = arr[1];
arr[1] = temp;
}
// {3,1,5,2,4}
// 1-3
if (arr[2] > arr[3]) { // 교환 조건
int temp = arr[3];
arr[3] = arr[2];
arr[2] = temp;
} // {3,1,2,5,4}
// 1-4
if (arr[3] > arr[4]) { // 교환 조건
int temp = arr[4];
arr[4] = arr[3];
arr[3] = temp;
} // {3,1,2,4,5}
// 2회전 (목표 : 3번지의 값을 정하는 것)
// 3회전 (목표 : 2번지의 값을 정하는 것)
// 4회전 (목표 : 1번지의 값을 정하는 것)
}
}STEP 2. 1회전 공통 모듈 찾기
package algo;
// {1,2,3,5,4}
public class Bubble03 {
public static void main(String[] args) {
// 인접한 두 수를 비교하고 스왑(교환)
int[] arr = {5, 3, 1, 2, 4};
// 회전수는 N-1
// 1회전 (목표 : 4번지의 값을 정하는 것)
int a = 0;
for (int i = 0; i < 4; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ",");
}
System.out.println();
// 2회전 (목표 : 3번지의 값을 정하는 것)
// 3회전 (목표 : 2번지의 값을 정하는 것)
// 4회전 (목표 : 1번지의 값을 정하는 것)
}
}
3. 전체 회전 공통 모듈 찾기
매 회전마다 의 최대값 4, 3, 2, 1을 변수화 시키지 못했다.
package algo;
// {1,2,3,5,4}
// 공통 모듈 찾아내기
public class Bubble04 {
public static void main(String[] args) {
// 인접한 두 수를 비교하고 스왑(교환)
int[] arr = {5, 4, 3, 2, 1}; // 샘플 최악으로 변경하기
int a = 0; // 탐색 시작 index
int n = arr.length; // 배열의 크기
int r = 0; // 라운드
int c = 0; // 라운드마다 반복 횟수
// 회전수는 N-1
// 1(r)회전 (목표 : 4번지의 값을 정하는 것)-------------------------------
r++;
a = 0;
c = n - r; // 4
for (int i = 0; i < c; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
// 2회전 (목표 : 3번지의 값을 정하는 것)-------------------------------
r++;
a = 0;
c = n - r; // 3
for (int i = 0; i < c; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
// 3회전 (목표 : 2번지의 값을 정하는 것)-------------------------------
r++;
a = 0;
c = n - r; // 2
for (int i = 0; i < c; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
// 4회전 (목표 : 1번지의 값을 정하는 것)-------------------------------
r++;
a = 0;
c = n - r; // 1
for (int i = 0; i < c; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
}
}
4. 반복
package algo;
// {1,2,3,5,4}
// 공통 모듈 찾아내기
public class Bubble05 {
public static void main(String[] args) {
// 인접한 두 수를 비교하고 스왑(교환)
int[] arr = {5, 4, 3, 2, 1}; // 샘플 최악으로 변경하기
int a = 0; // 탐색 시작 index
final int N = arr.length; // 배열의 크기
int r = 0; // 라운드
int c = 0; // 라운드마다 반복 횟수
// 회전수는 N-1
// 1(r)회전 (목표 : 4번지의 값을 정하는 것)-------------------------------
for (int round = 0; round < N - 1; round++) {
r++;
a = 0;
c = N - r; // 4,3,2,1
for (int i = 0; i < c; i++) {
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
}
}
}
5. 시간 복잡도 계산
package algo;
public class Bubble {
public static void main(String[] args) {
// 1. 초기 세팅
int[] arr = {15, 13, 12, 11, 7, 10, 9, 8};
int a; // 시작 index
final int N = arr.length; // 배열의 크기
int r = 0;
// 시간복잡도
// 첫항 : 1, 마지막항 N-1
// 가우스연산 (끝)
int myCount = Util.gauss(1, N - 1);
System.out.println("myCount : " + myCount);
int count = 0;
for (int k = 0; k < N - 1; k++) {
a = 0;
r++;
for (int i = 0; i < N - r; i++) {
count++;
System.out.print(".");
if (arr[a] > arr[a + 1]) { // 교환 조건
int temp = arr[a + 1]; // temp = 3;
arr[a + 1] = arr[a];
arr[a] = temp;
}
a++;
}
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
}
System.out.println("시간복잡도 : 배열크기(" + N + ") : " + count);
}
}6. 버블 정렬 시간 복잡도 증명
버블정렬 시간복잡도 O((n^2-n) / 2) = O(n^2)
증명
n = 2일때 1번
n = 3일때 3번 (1+2)
n = 4일때 6번 (1+2+3)
n = 5일때 10번 (1+2+3+4)
n = 6일때 15번 (1+2+3+4+5)
.....
n일 때 (1+2+3+...+n-1) 번
총 더하는 횟수 : n-1번 (항의 수)
첫 항 : 1
마지막 항 : n-1
가우스 연산 적용 : 합 S = (첫 항 a + 마지막 항 l) * 항의 수 n / 2
(n-1 + 1) * (n-1) / 2 = n(n-1) / 2- n이 계속 무한대로 커진다는 것을 가정했을 때,
- n의 제곱에서 /2나 -n은 n의 제곱에 영향을 줄 수 없기 때문에 시간복잡도 = O(n^2)로 표기 가능
Share article