[JAVA] 자바 정렬 : 버블 정렬 (bubble sort)

버블 정렬 : 인접한 두 원소를 비교하며 정렬하는 방법

 

기본 로직 : 

첫 번째 숫자와 두 번째 숫자를 비교하여 오름차순으로 정렬. 두 번째 숫자와 세 번째 숫자를 비교하여 오름차순 정렬 이렇게 모든 숫자들을 한 번씩 비교하였다면 그게 1회전을 하는 것이고, 1회전 후에는 항상 제일 큰 숫자가 마지막에 와야 한다. 

 

swap : (어떤 것을 주고 그 대신 다른 것으로) 바꾸다 

int a =10, b=20 가 있을 때, a 와 b 의 값을 바꾸고 싶다면 어떻게 해야 할까? 

변수 int tmp; 를 생성해주고 1. tmp=a; tmp 에 a의 값을 담는다. 2. a=b ; a에 b의 값을 할당한다. 3. b=tmp; b에 tmp 값 할당

 

 

코드로 확인

        int [] a = { 8, 3, 10, 9, 6, 4, 2, 88 }; //해당 배열이 있다. 버블 정렬 해보아라 
		int i, j, tmp; //값을 담을 변수 선언 
        
		for (i = 0; i < a.length - 1; i++) { 
        // 정렬 전의 숫자 -1 번 반큼 반복. 5개 숫자면 4번 반복 (n-1)
			for (j = 0; j < a.length - 1 - i; j++) {
		// a.length-1-i에 -i 는 결국 1회전시 가장 큰 숫자는 정렬 완료 되어 있기에 할 필요 없다.
				if (a[j] > a[j + 1]) { // 앞방 뒷방을 비교하는 중.
		// 앞에 있는 숫자가 더 크면 오름차순이 제대로 안된거라 바꿔 줘야 함

		// swap
			tmp = a[j];// J 번째 있는 값을 tmp 로 옮기고
			a[j] = a[j + 1]; // j에 j+1 을 넣어줘
			a[j + 1] = tmp; // 비어 있는 j+1에는 tmp 를 넣어주자
				}
			}

		}

		System.out.println("정렬 후");
		for (i = 0; i < a.length; i++) {
			System.out.println(a[i] + "\t");
		}
		System.out.println();
	}

int [ ] a 배열에 있는 숫자들을 버블 정렬할 것이다. 값들을 담을 int 변수들도 선언한다.

첫 번째 for 문은 전체적인 배열을 반복한다고 생각하면 쉽다.  i 가 배열 a 의 길이-1 만큼 반복할껀데 왜냐하면, 버블 정렬은 길이가 3개면 2번 비교하는것이고 길이가 100이면 99번을 비교하는 것이니까. 즉 값들을 두개씩 묶어서 한번 비교하는 거니까 배열의 크기 만큼 돌면 하나가 아무것도 없는게 되어 버린다. 따라 배열길이 -1 만큼 반복을 수행한다.  

 

두 번째 for 문은 내부에서 비교를 반복하는 개수인데 왜 배열길이-1-i 로 되었냐하면, 결국 전체적인 1회전이 끝나면 버블 정렬은 가장 큰 숫자가 맨 뒤로 가게 되어 있다. 그러면 굳이 또 마지막까지 비교를 하지 않아도 되니까 커지는 i 만큼 비교 할 대상들이 줄어든다. 또한, if 문을 통해서는 값들을 비교 해 주었는데 j 보다 j 다음의 숫자가 작다면 swap 을 통해 값 변환을 시켜 준다.

프린트를 위한 for 문을 돌려 깔끔하게 출력하면 끝!