1. 정렬
자료구조에서 정렬을 얘기하는 이유는 탐색을 설명하기 위한것이다.
탐색은 어떤 기준을 근거로해서 정렬된 데이터들을 어떻게 효율적으로 탐색할것인가?그것을 논의하는게 탐색이다.
탐색에 앞서 선행된 주제가 정렬이다.
2. 버블정렬 이해
- 버블정렬은 구현하기는 쉬우나 성능은 떨어진다.
- 인접한 두개의 데이터를 비교해가면서 바뀌어야 한다면 두 데이터를 바꾸면서 정렬을 진행한다.
1) 첫번째 : 제일 큰 값을 맨 뒤로 보낸다.
2) 두번째: 두번째로 큰 값을 맨뒤에서 한 칸 앞으로 보낸다.
3) 세번째: 나머지를 동일하게 정렬한다.
이와 같이 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 한다.
3. 버블정렬 구현
- for문 중첩으로 구현하였다.
- 안쪽 for문의 반복조건과 바깥쪽 for문의 반복조건에 대한 이해가 정확히 필요하다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | package Sort; public class BubbleSort { public static void main(String[] args) { int[] arr = {3, 2, 4, 1}; BubbleSort(arr, arr.length); for(int i=0; i<arr.length; i++) { System.out.print(arr[i]); } } static void BubbleSort(int[] arr, int n) { int i, j; int temp;//임시 for(i=0; i<n-1; i++) { for(j=0; j<(n-i)-1; j++) { if(arr[j] > arr[j+1]) {//앞이 뒤보다 크다면, 앞뒤를 바꿔줌 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } } | cs |
4. 성능평가
정렬 알고리즘의 성능은 다음 정렬과정의 핵심 2가지 근거로 판단하는것이 일반적이다.
1) 비교의 횟수 - 두 데이터간의 비교연산의 횟수
2) 이동의 횟수 - 위치의 변경을 위한 데이터의 이동 횟수
실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 비교의 횟수이다.
비교횟수는 다음 반복문 안에 위치한 if문의 실행 횟수를 기준으로 계산할 수 있다.
if(arr[j] > arr[j+1]) {...} //비교 연산이 발생하는 장소
앞서 본 버블정렬의 과정 [10-1]~[10-3]의 그림을 보면
4개의 데이터를 3단계에 걸쳐서 정렬하였다. 비교의 횟수를 더한 결과는 3+2+1 이었다.
이렇듯 버블 정렬의 데이터의 수가 n개일때 진행되는 비교의 횟수는 다음과 같다.
(n-1) + (n-2) + . . . + 2+ 1
그리고 이는 등차수열의 합에 해당하므로 다음과 같이 정리된다.
따라서 버블 정렬의 비교연산에 대한 빅-오는 최선의 경우와 최악의 경우 구분없이 O(n^2) 이다.
빅오를 구할때 이동의 횟수는 무시했다.