정렬 알고리즘1 - 버블정렬(Bubble Sort)

버블정렬 (Bubble Sort)

출처- 위키백과

작동방식

• 인접한 두 데이터의 값을 비교해 위치를 맞바꾸는 방식
• 맞바꾸는 과정이 더이상 필요없을 때까지 반복한다

참고로 버블이라는 명칭은 정렬되는 모습이 버블, 즉 물 속에서 거품처럼 올라오는 모습과 비슷하여 여기서 유래했다고 한다. 마치 맥주 탄산이 올라오는 것 같다.

 

 

특징

 

• 정렬 방식이 간단하다
• 위치를 바꾸는 작업이 많아 효율이 좋지않다
• 데이터의 총 개수 n 이라고 했을때, 비교횟수는 (n-1), (n-2), (n-3), ... , 1 로서 루프를 돌면서 줄어든다
• 총비교횟수 : n * (n-1) / 2 이다. n제곱만큼 계산량을 가진다

 

 

예시

[ 1, 14, 9, 6, 2, 19, 4, 7 ] 와 같은 숫자집합이 있을때 아래와 같은 순서로 정렬된다.

 

1 9 14 6 2 19 4 7 
1 9 6 14 2 19 4 7 
1 9 6 2 14 19 4 7 
1 9 6 2 14 4 19 7 
1 9 6 2 14 4 7 19 
1 6 9 2 14 4 7 19 
1 6 2 9 14 4 7 19 
1 6 2 9 4 14 7 19 
1 6 2 9 4 7 14 19 
1 2 6 9 4 7 14 19 
1 2 6 4 9 7 14 19 
1 2 6 4 7 9 14 19 
1 2 4 6 7 9 14 19 

 

 

구현코드 - Java

public void test(){
	int[] intArr = {1, 14, 9, 6, 2, 19, 4, 7};
	int i, j, temp;
	//a. 반복문1
	for(i=intArr.length-1; i>0; i--){
		//b. 반복문2
		for(j=0; j<i; j++){
			//c. 조건식
			if(intArr[j] > intArr[j+1]){
				temp = intArr[j];
				intArr[j] = intArr[j+1];
				intArr[j+1] = temp;
			}
		}
	}
}

 

 

---

변형된 버블정렬

버블정렬의 코드를 다르게 구성해 정렬할 수 있다. 내부 반복문의 인자값만 바꾼다

 

구현코드 - Java

int[] intArr = {1, 14, 9, 6, 2, 19, 4, 7};
//a. 반복문1 - 첫번째부터 n-1까지
for(int i=0; i<intArr.length-1; i++){
	//b. 반복문2 - i+1부터 n까지
	for(int j=i+1; j<intArr.length; j++){
		//c. 조건식
		if(intArr[i] > intArr[j]){
			int temp = intArr[i];
			intArr[i] = intArr[j];
			intArr[j] = temp;
		}
	}
}

• a- 바깥쪽 반복문이 실행된다. 정렬할 요소개수에서 한 개 줄인 값(n-1)까지 반복한다
• b- 안쪽 반복문이 실행된다. 바깥쪽 반복변수 i+1, 즉 다음 인덱스 값부터 마지막 값까지 반복한다
• c- 오름차순, 내림차순 등 정렬조건식

 

 

정렬 순서

 

1 9 14 6 2 19 4 7  -> 첫번째 루프. 두번째 숫자 14와 세번째 숫자 9를 바꾼다
1 6 14 9 2 19 4 7  -> 두번째 숫자 9와 네번째 숫자 6을 바꾼다
1 2 14 9 6 19 4 7  -> 두번째 숫자 6과 다섯번째 숫자 2를 바꾼다. 첫번째 루프 종료.
1 2 9 14 6 19 4 7  -> 두번째 루프
1 2 6 14 9 19 4 7
1 2 4 14 9 19 6 7
1 2 4 9 14 19 6 7  -> 세번째 루프
1 2 4 6 14 19 9 7
1 2 4 6 9 19 14 7  -> 네번째 루프
1 2 4 6 7 19 14 9
1 2 4 6 7 14 19 9  -> 다섯번째 루프
1 2 4 6 7 9 19 14  -> 여섯번째 루프
1 2 4 6 7 9 14 19  -> 일곱번째 루프