버블 정렬

정렬의 종류

버블 정렬(Bubble Sort)
선택 정렬(Selection Sort)
카운팅 정렬(Counting Sort)
삽입 정렬(Insertion Sort)
힙정렬
병합 정렬
퀵정렬

버블 정렬이란

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
⭐인접한 원소끼리 비교
⭐계속 자리를 교환

정렬 과정

1. 총 몇 번 비교? arr.length-1만큼 비교
2. 인접한 두 수끼리 비교한다
   i=0 일 땐 arr[0]부터 arr[3]까지
   i=1 일 땐 arr[0]부터 arr[2]까지
   i=2 일 땐 arr[0]부터 arr[1]까지
3. 이전 인덱스 원소가 크다면
4. 두 수를 교환한다.

구현

		int[] arr = {55, 7, 78, 12, 42};
		int tmp=0;
		int len = arr.length;
		
		// 총 몇 번 비교? arr.length-1만큼 비교
		for(int i=0; i < len-1; i++) {
			// 인접한 두 수끼리 비교한다
			for(int j=0; j < len-1-i; j++) {
				if(arr[j] > arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			} //for
		} //for

아래와 같이도 구현할 수 있다.

		int[] arr = {55, 7, 78, 12, 42};
		int tmp=0;
		int len = arr.length;

		for(int i = len-1; i > 0; i--) {
			for(int j= 0; j < i; j++) {
				if(arr[j] > arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			} //for
		} //for