앞서 선택 정렬을 설명했다. 만약 내가 쓴 순서대로 읽어보고도 이해가 되지 않는다면 뒤로 돌아 선택정렬을 다시 복습하거나 이해하고 오기 바란다.
우리에겐 복습, 이해 만이 살길이기 때문이다.
오늘은 버블 정렬이다. 그렇다면 선택 정렬과 무엇이 다른가??????????
그 차이점은 바로 시작점이다.
선택 정렬
선택 정렬은 첫번째 값부터 마지막 값까지 진행하며 가장 작은 최소값을 찾는다.
최소값을 찾아 제일 앞으로 교체했다면 그 최소값은 건들지 않고 뒤에서 부터 마지막까지 진행한다.
버블정렬
버블 정렬은 선택 정렬과는 다르게 서로 인접한 두 값만을 비교한다. 인덱스 1과 2의 값을 비교 시
1보다 2가 작다면 2는 1의 자리로 교체된다. 그 후 2와 3을 비교하는 방식이 반복된다.
이해를 돕기 위한 버블정렬 순서도이다.
위 설명과 마찬가지로 그림을 보면 인접한 두 수를 비교하여 작은 수를 앞으로 교체하는 작업이 반복되어지고 몇 번의 회전을 거쳐 오름차순이 완성되는 것을 볼 수 있다.
우리는 위 그림과 같이 알고리즘을 구현하면 된다.... 어려워 보이지만 그렇지 않다
내가 강조했던 for문과 함께라면 물론 선택정렬도 마찬가지 ㅎㅎ
int[] arr = new int[10];
1. for(int i = 0; i < arr.length;i++){
arr[i] = (int)(Math.random() * 100) + 1;
}
for(int i = 0; i < arr.length - 1; i++){
2. boolean flag = false;
for(int j = 0; j < arr.length - 1 - i; j++){
3. if(arr[j] > arr[j +1]){
4. int temp = arr[j];
5. arr[j] = arr[j+1];
6. arr[j+1] = temp;
7. flag = true;
}
}
8. if(!flag){
9. break;
}
}
System.out.println(Arrays.toString(arr));위에서 부터 아래 순서로 코드에 대한 설명을 시작하면,
- 크기 10인 int타입 arr 배열을 선언하고 1 ~ 100의 난수로 초기화한다.
- 만약 배열의 길이만큼 돌린 for문 보다 정렬이 일찍 끝난다면 반복을 그만할 flag를 선언
- 만약 j 보다 (j+1) 다음 번지의 값이 작다면
- j의 값을 temp에 담아준다.
- 그 자리에 j 번지에 j보다 작았었던 (j+1)의 값을 삽입한다.
- 그 후 (j+1)번지에는 j의 값을 담아준다.
- 만약 정렬이 완료되지 않아 이 조건문을 만족하여 아래의 식을 수행한다면 flag는 true로 아래 break를 실행하지 않게 한다.
- 만약 조건문을 거치지 않아 flag 가 여전히 false라면 break를 만나 반복이 멈춘다.
arr.length - 1 - i 의 의미
- for문이 한 번 돌때마다 맨 뒤의 값은 이미 정렬이 끝난 상태이다. 때문에 맨 뒤의 인덱스를 제외하기 위해 -i 를 해주는 것이고 -1 은 배열의 범위를 벗어나지 않기 위해서이다.
만약 -1이 없다면 첫 번째 for문이 돌때 이차for문의 인덱스가 10이되어 범위를 벗어난다.그리고 일차for에 -1 이 없다면 맨뒤 인덱스를 제거하는 도중 맨 마지막 인덱스에 도달하면 -11 이 되기 때문에 인덱스에 또한 벗어난다.
즉, 반복회수를 줄여주기 위함이다.
