버블 정렬은 알고리즘에 속한다!
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정 따라서
함수를 절차적으로 만들면 ‘알고리즘’이다.
버블정렬
- 서로 인접한 두 원소(인덱스)를 검사하여 정렬하는 알고리즘 - 인접한 2개의 레코드(값)를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
- 버블 정렬은 인덱스 0과 인덱스 1을, 인덱스 1과 인덱스 2를, 인덱스 2와 인덱스 3을, …, 이런 식으로 (마지막 - 1) 번째 인덱스와 마지막 인덱스를 비교하여 교환하면서 인덱스를 정렬한다.
- 1 회전 (마지막 인덱스 - 1) 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2 회전 때는 정렬이 된 마지막 인덱스는 비교에서 제외 된다. 이렇게 정렬을 1 회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
버블 정렬의 흐름 보기
5, 8, 2, 4, 3 수를 버블 정렬 하면?
버블 정렬의 회전 수는 N-1회 돈다! 이때 N은 배열의 크기이다.
그리고 회전마다 비교하는 횟수가 다른데
1 회전 비교 횟수 : N - 1
2 회전 비교 횟수 : N - 2
3 회전 비교 횟수 : N - 3
4 회전 비교 횟수 : N - 4 로 회전한다.
이를 함수로 풀어보면 각 회전 마다의 루프 수 : N - i 로 된다. (이때 i는 회전 수)
ㅤ | 1 회전 | 2 회전 | 3 회전 | 4 회전 |
1 | 5, 8 비교 (변화 없음) | 5, 2 비교 (2, 5, 4, 3, 8) | 2, 4 비교 (변화 없음) | 2, 3 비교 (변화 없음) |
2 | 8, 2 비교 (5, 2, 8, 4, 3) | 5, 4 비교 (2, 4, 5, 3, 8) | 4, 3 비교 (2, 3, 4, 5, 8) | ㅤ |
3 | 8, 4 비교 (5, 2, 4, 8, 3) | 5, 3 비교 (2, 4, 3, 5, 8) | ㅤ | ㅤ |
4 | 8, 3 비교 (5, 2, 4, 3, 8) | ㅤ | ㅤ | ㅤ |
3 회전에서 정렬이 완료 되지만 컴퓨터이기 때문에 중간에 끝낼 수 없어서 4 회전까지 끝까지 가게 된다.
특징 : 가장 큰 수가 가장 먼저 제일 뒤로 간다. (만약 의심 되면 다음 것도 해본다!)
결론 : 가장 큰 수를 마지막으로 보내면서 정렬 된다.
정렬의 목적
- 자료구조의 검색에 초점이 맞춰져 있다.
- 효율적으로 원하는 데이터를 찾기가 쉬워진다.
- 중복이 데이터가 있어도 멈추는 타이밍을 알 수 있게 된다. - 클러스터링(Clustering) : 중심점을 기준으로 가까운 데이터들을 할당하고, 그룹화를 반복적으로 수행한다.
- 3 번 같은 형태를 두고 ‘이진 탐색(Binary Search)’ 이라 한다.
그림 설명
버블 정렬 예시
버블 정렬 예제
package ex03; public class BubbleEx01 { // 함수-메서드 : 메서드 맛보기 // static 을 찾을때 class 부터 찾는다. 하지만 같은 class 내에 있으면 class 명 생략가능 static void bubble(int[] arr) { final int N = arr.length; int temp; for (int loop = 1; loop < N; loop++) { for (int i = 0; i < N - loop; i++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } for (int i = 0; i < N; i++) { System.out.print(arr[i] + " "); } } public static void main(String[] args) { int[] arr = {5, 8, 2, 4, 3}; BubbleEx01.bubble(arr); // static 을 찾을때 class 부터 찾는다. 하지만 같은 class 내에 있으면 class 명 생략가능 System.out.println(); int[] arr2 = {5, 8, 2, 4, 3, 10, 500, 7, 6}; BubbleEx01.bubble(arr2); } }
출력 결과
위의 bubble이 main의 밖에 있는데 이를 메소드(함수) 라고 한다!
메서드(함수) 선언 시 같은 class 내에서는 class.a();가 아닌 a(); 로 선언이 가능하다!
이를 바탕으로 BubbleEx01.bubble(arr);이 아닌 bubble(arr);으로만 선언이 가능하다!
메소드는 다음에 다룹니다!
Share article
