13. 버블 정렬(Bubble Sort)(오름차순,내림차순 정렬)

 

버블 정렬(Bubble Sort)은 정렬 대상 리스트(배열)의 항목을 수평방향으로 나열했다고 가정했을 때,

왼쪽 끝에서부터 시작해서 인접하는 두 항목의 값을 비교하여 올바른 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬방법이다.

 

이렇게 인접하는 항목의 값을 비교해서 위치를 교환하는 과정을 리스트(배열)의 마지막 항목까지 반복해서 제일 큰(또는 작은) 값이 끝에 오도록 한다.

각 회전(Pass)과정이 끝날때마다 정렬은 뒤에서부터 하나씩 완료된다.

---

int[] numArr= {9,7,3,5,1} 라는 배열이 존재한다고 가정했을 때,

 

정렬하기 전은 아래와 같다.

데이터값=> | 9 | 7 | 3 | 5 | 1 |

index=> 0 1 2 3 4

 

이 배열을 각각 오름차순, 내림차순으로 정렬해보면 아래와 같다.

 

1. 오름차순 정렬

 

1)

데이터 값은 총 5개이고 첫번째 숫자와 남은 4개의 숫자를 비교하는 것이므로

반복문의 총 반복 횟수는 배열의 길이-1

for(int i=0;i<numArr.length-1;i++)

 

2)

내부 반복문은

i=0; ==> 조건식이 j<4; 되어야만 4번 비교함.

i=1; ==> 조건식이 j<3; 되어야만 3번 비교함.

i=2; ==> 조건식이 j<2; 되어야만 2번 비교함.

i=3; ==> 조건식이 j<1; 되어야만 1번 비교함.

 

와 같이 비교가 이루어져야 하므로 반복 횟수는 numArr.length-1-i

for(int j=0;j<numArr.length-1-i;j++)

 

3)

오름차순 정렬이므로 인덱스0에 해당하는 수가 가장 작아야 한다.

따라서 인덱스가 작은 수가 큰 수보다 크면 변경해야 하므로 조건문은 아래와 같다.

if(numArr[j]>numArr[j+1])

 

 

4)

j=0 일 때

int temp=numArr[0]; // 인덱스 0에 해당하는 숫자는 9

numArr[0]=numArr[1]; // numArr[0](9)이 numArr[1](7)보다 크므로 numArr[0]에 numArr[1] 대입

numArr[1]=temp;

 

int temp=numArr[1]; // 인덱스 1에 해당하는 숫자는 9

numArr[1]=numArr[2]; // numArr[1](9)이 numArr[2](3)보다 크므로 numArr[1]에 numArr[2] 대입

numArr[2]=temp;

 

int temp=numArr[2]; // 인덱스 2에 해당하는 숫자는 9

numArr[2]=numArr[3]; // numArr[2](9)이 numArr[3](5)보다 크므로 numArr[2]에 numArr[3] 대입

numArr[3]=temp;

 

=>numArr[4]==9, 같은 방법으로 numArr[3]==7, numArr[2]==5, numArr[1]==3, numArr[0]==1

 

int temp=numArr[j];

numArr[j]=numArr[j+1];

numArr[j+1]=temp;

 

for(int i=0;i<numArr.length-1;i++) {

			for(int j=0;j<numArr.length-1-i;j++) { 
				if(numArr[j]>numArr[j+1]) {
					int temp=numArr[j];    
					numArr[j]=numArr[j+1]; 
					numArr[j+1]=temp;	
				}
			}// end of for---------------------------------------
		}// end of for---------------------------------------
System.out.println("=== 오름차순 정렬한 후 ===");

		for(int i=0;i<numArr.length;i++) {
			String str = (i<numArr.length-1)?",":"\n";
			System.out.print(numArr[i]+str);
        }// end of for---------------------------------------

/*
=== 오름차순 정렬한 후 ===
1,3,5,7,9
*/

 

2. 내림차순 정렬

 

int[] numArr2= {9,7,3,5,1};

 

1)

데이터 값은 총 5개이고 첫번째 숫자와 남은 4개의 숫자를 비교하는 것이므로

반복문의 총 반복 횟수는 배열의 길이-1

for(int i=0;i<numArr2.length-1;i++)

 

2)

내부 반복문은

i=0; ==> 조건식이 j<4; 되어야만 4번 비교함.

i=1; ==> 조건식이 j<3; 되어야만 3번 비교함.

i=2; ==> 조건식이 j<2; 되어야만 2번 비교함.

i=3; ==> 조건식이 j<1; 되어야만 1번 비교함.

 

와 같이 비교가 이루어져야 하므로 반복 횟수는 numArr.length-1-i

for(int j=0;j<numArr2.length-1-i;j++)

 

3)

내림차순 정렬이므로 인덱스0에 해당하는 수가 가장 커야 한다.

따라서 인덱스가 작은 수가 큰 수보다 작으면 변경해야 하므로조건문은 아래와 같다.

if(numArr2[j]<numArr2[j+1])

 

 

4)

j=0일 때 numArr2[0]>numArr2[1]이므로 numArr2[0]==9

 

j=1일 때 numArr2[1]>numArr2[2]이므로 numArr2[1]==7

 

j=2일 때

int temp=numArr2[2]; // 인덱스 3에 해당하는 숫자는 3

numArr2[2]=numArr2[3]; // numArr2[2](3)이 numArr2[3](5)보다 작으므로 numArr2[2]에 numArr2[3] 대입

numArr2[3]=temp; // numArr2[3] ==3

numArr2[3]>numArr2[4]이므로 numArr2[2]==5, numArr2[3]==3

 

j=3일 때 numArr2[3]>numArr2[4]이므로 numArr2[4]==1

 

int temp=numArr[j];

numArr[j]=numArr[j+1];

numArr[j+1]=temp;

 

int[] numArr2= {9,7,3,5,1};
		
		for(int i=0;i<numArr2.length-1;i++) {
			
			for(int j=0;j<numArr2.length-1-i;j++) {
				
				if(numArr2[j]<numArr2[j+1]) {
					int temp=numArr2[j];    
					numArr2[j]=numArr2[j+1]; 
					numArr2[j+1]=temp;	
				}
			}
			System.out.println("=== 내림차순 정렬한 후 ===");

			for(i=0;i<numArr2.length;i++) {
				String str = (i<numArr2.length-1)?",":"\n";
				System.out.print(numArr2[i]+str);
			}
		}

/*
=== 내림차순 정렬한 후 ===
9,7,5,3,1
*/