[알고리즘] 내림차순 구하기 (버블정렬)

오늘은 자바로 내림차순 정렬을 구하는 sort 함수를 만드는 도중에 배열의 값을 변경할 때 이해가 안 가는 부분이 있어 정리 하기위해 글을 작성해 봅니다!

int arr[] = {95, 100, 105, 110};
		int temp = 0;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=i; j<arr.length; j++) {
				if(arr[i] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}

이 부분에서 처음 i = 0 번째 for 문이 시행이 되면 arr[i]의 0 번째 값은 95가 되어 두 번째 for 문인 j를 돌게 되는데 j의 1번째 for 문이 실행이 되면 arr[j]의 값이 100이 되어 arr[i]가 arr[j]보다 값이 작기 때문에 if 문이 실행이 된다.

if 문이 실행이 되면 arr[i]의 0번째는 100, arr[j]의 첫 번째 값은 95가 되면서 변경이 된다고 생각을 했다 그렇게 쭉 i = 0 번째 for 문을 전부 돌게 되면

 

i 번의 0 번째 j번의 0 번째 실행 중
i : 0 j : 0 , arr[i] : 95, arr[j] :95 
i 번의 0 번째 j번의 1 번째 실행 중
i : 0 j : 1 , arr[i] : 100, arr[j] :95 
i 번의 0 번째 j번의 2 번째 실행 중
i : 0 j : 2 , arr[i] : 105, arr[j] :100 
i 번의 0 번째 j번의 3 번째 실행 중
i : 0 j : 3 , arr[i] : 110, arr[j] :105 

 

(윗부분이 이해가 안 되면 밑의 사진을 봐주세요! )

for i = 0 , j = i ~ 3

for i = 1 , j = i ~3

위의 사진들처럼 값이 변경이 되고 i의 1번째 for 문이 끝이 나면 i의 2번째 for 문은 실행이 될 수가 없지 않은가? 라는 생각을 하면서 이해가 가지 않았다.

 

그래서 콘솔을 찍어 확인을 해보니 이중 for 문의 i의 0 번째의 j 번째가 끝이 나면 arr의 값들도 전부 변경이 된다는 걸 알게 되었고 (당시에는 for문이 실행이 되면 arr[i]와 arr[j]가 따로 생성이 되고, 두 번째 for 문인 j가 i부터 arr.length(3)까지 실행이 완료가 되면 변경된 arr[j] 값만 arr 배열에 적용되는 줄 알고 있었는데 아니였다.. 실제로는 for문의 i가 한번 실행이 되고 끝이나면 변경된 arr[i] 와 arr[j]의 값이 arr의 배열에 적용이 되서 최종적으로 arr 배열의 값이 변경이 된다는걸 알게 되었다.. )

그래서 두 번째 사진의 메모장에 적은 부분은 잘못된 부분이고 아래의 사진처럼 변경되어야 하는 게 맞는다는 걸 알게 되었다!

for i = 1 , j = i ~3

i 번의 0 번째 j번의 0 번째 실행 중
i : 0 j : 0 , arr[i] : 95, arr[j] :95 

i 번의 0 번째 j번의 1 번째 실행 중
i : 0 j : 1 , arr[i] : 100, arr[j] :95 

i 번의 0 번째 j번의 2 번째 실행 중
i : 0 j : 2 , arr[i] : 105, arr[j] :100 

i 번의 0 번째 j번의 3 번째 실행 중
i : 0 j : 3 , arr[i] : 110, arr[j] :105 
arr : [110, 95, 100, 105]


i 번의 1 번째 j번의 1 번째 실행 중
i : 1 j : 1 , arr[i] : 95, arr[j] :95 

i 번의 1 번째 j번의 2 번째 실행 중
i : 1 j : 2 , arr[i] : 100, arr[j] :95 

i 번의 1 번째 j번의 3 번째 실행 중
i : 1 j : 3 , arr[i] : 105, arr[j] :100 
arr : [110, 105, 95, 100]


i 번의 2 번째 j번의 2 번째 실행 중
i : 2 j : 2 , arr[i] : 95, arr[j] :95 

i 번의 2 번째 j번의 3 번째 실행 중
i : 2 j : 3 , arr[i] : 100, arr[j] :95 
arr : [110, 105, 100, 95]


i 번의 3 번째 j번의 3 번째 실행 중
i : 3 j : 3 , arr[i] : 95, arr[j] :95 
arr : [110, 105, 100, 95]

------- 변경된 값 -------
arr : [110, 105, 100, 95]

		// 내림차순 정렬
        int arr[] = {95, 100, 105, 110}; 
		int temp = 0;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=i; j<arr.length; j++) {
				if(arr[i] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
				System.out.println();
				System.out.println("i 번의 "+ i + " 번째 j번의 " + j + " 번째 실행 중");
				System.out.print("i : " + i + " j : " + j + " , arr[i] : " + arr[i] + ", arr[j] :" + arr[j] + " ");
				System.out.println();
			}
			System.out.print("arr : " + Arrays.toString(arr));
			System.out.println();
			System.out.println();
		}
		
		System.out.println("------- 변경된 값 -------");
		System.out.print("arr : " + Arrays.toString(arr));
	}

}

 

그리고 이러한 정렬 방식을 버블정렬이라고 하는걸 알게 되었고 버블정렬이 무엇인지 다른 자료들을 찾아 보았다! 

 

[버블정렬]

1. 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
2. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

개념

1. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다고 한다.

 

2. 1회전을 수행하고 나면 가장 큰 자료가 맨 앞으로 이동하므로 2회전에서는 맨 앞에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 앞에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

장점
구현이 매우 간단하고 쉽다.

단점
순서에 맞지 않은 요소를 인접한 요소와 교환하며,
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다고 한다!