bubble sort 버블정렬

Jungsangjin0/sort-practice

 

package sort.bubble;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		/*배열의 크기 10으로 초기화*/
		int[]numArr = new int[10];
		//numArr.length = 10  0 ~9
		for(int i = 0; i < numArr.length; i++) {
			/*1 ~ 9까지random수로  배열 초기화*/
			numArr[i] = (int)((Math.random() * 9) + 1);
		}
		/*
		 * 정렬 전
		 * [3, 5, 5, 6, 4, 2, 8, 4, 9, 9]
		 */
		System.out.println(Arrays.toString(numArr));
		
		/*
		 * 배열의 길이는 numArr.length 
		 * 비교하는 숫자는 numArr.length - 1
		 * 이해하기 위한 예시)  3, 1, 4 배열이 있다면
		 * 처음 비교 시 [3, 1] 그리고 [1, 4]를 비교하게 된다(i = 0; j = 2번)
		 * 다음 for문에서 변경된 앞 두 숫자 [3, 1]을 비교하게 된다.(i = 1; j = 1번)
		 * 따라서 밖에 for문은 numArr.length -1 이된다.
		 */
		for(int i = 0; i < numArr.length-1; i++) {
			/*자리바꿈 체크*/
			boolean check = false;
			
			/*
			 * numArr.length -1 -i 번째 하는 이유
			 * 이해하기 위한 예시) 3, 1, 2, 4 배열이 있다면
			 * 처음 비교시(i = 0, numArr.length = 4) [3, 1](두 자리 변경), [3,2](두 자리 변경), [3, 4](고정) :: 비교는 총 3번 마지막 인덱스에 4 고정
			 * 다음 비교시 (i = 1, numArr.length = 4) [1, 2](고정), [2, 3](고정) :: 비교는 총 2번 ::2번 하는 이유 : 마지막 인덱스에 4가 고정되었기 때문에
			 * 비교 하지 않아도 되기 때문에 3번 비교가 아닌 2번 비교 
			 * 마지막 비교시 (i = 2, numArr.length = 4) [1, 2](고정) :: 비교는 총 1번 : 4 이 후에 큰 숫자 3이 고정되었기 때문에 1번 비교
			 * 따라서 j를 반복할 떄 numArr.length - 1 에 숫자 i 만큼 줄여주게 된다.
			 * -1을 해주는 이유는 if문에서 비교 시 j번째 인덱스와 j + 1인덱스를 비교하게 되는데 length 만큼 하게 되면 exception이 발생한다.
			 * ex) numArr.length = 5, idx = 0 ~ 4, (j가 4일 때) numArr[4](j), numArr[5](j + 1) 
			 */
			for(int j = 0; j < numArr.length-1-i; j++) {
				/*j 번째 인덱스의 값이(8) j+1 번째 인덱스 값보다 클 경우(5) 두 개의 자리를 바꾼다.*/
				if(numArr[j] > numArr[j + 1]) {
					int temp = numArr[j];
					numArr[j] = numArr[j + 1];
					numArr[j + 1] = temp;
					check = true; /*자리바꿈 체크*/
				}/*if 문 끝*/
				
			}/*j for문 끝*/
			if(!check) break; /*자리바꿈이 일어나지 않았다면 i for문을 나간다. : 다 정렬되어있는 상태에서 for문을 더이상 돌지않게 함.*/
		}/*i for문 끝*/
		
		
		/*정렬 후
		 *[2, 3, 4, 4, 5, 5, 6, 8, 9, 9]
		 */
		System.out.println(Arrays.toString(numArr));
	}
}

 

 

참고서적 : Java의 정석3rd Edition, 남궁 성