저번 글에서 언급했듯이 이제부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다.
이번 시간에는 기본적인 정렬 알고리즘 세 개 중 하나인 버블 정렬입니다.
(삽입과 선택은 다음 시간에 다루겠습니다!)
버블 정렬(Bubble Sort) - 안정 정렬
버블 정렬이란 인접한 두 원소를 계속 비교해 나가며 최종 정렬 값을 하나씩 완성해 나가는 방법입니다.
글로써는 이해하기가 어려울 수 있으니 그림으로 자세하게 설명드리도록 하겠습니다.
위 그림은 주어진 데이터를 오름 차순으로 버블 정렬하는 과정입니다.(데이터의 사이즈 n = 5)
정렬 과정은 데이터의 수 - 1 만큼 회전(반복)하며 큰 값을 결정해 나가는 것입니다.
다시 말해 1회전 - 첫 번째로 큰 값(7), 2회전 - 두 번째로 큰 값(5) ... 마지막으로 n-1 번째로 큰 값(2)을 결정하고 끝입니다.
(n번째 큰 값 1은 n-1번째로 큰 값이 정해지면 알아서 정해지므로 n-1번째 까지만 진행합니다.)
최종적으로 7 - 3 - 2 - 1 -5 의 데이터가 1 -2 - 3 - 5 - 7 로 정렬됨을 확인할 수 있습니다.
소스 코드
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 | #include <iostream> using namespace std; void swap(int *a, int * b){ int temp; temp = *a; *a = *b; *b = temp; } int main() { int a[5] = {7,3,2,1,5}; bool endFlag; //정렬 for(int i = 0 ; i < 4;i++){ endFlag = true; for(int j=0; j <4-i;j++){ if(a[j]>a[j+1]){ swap(&a[j],&a[j+1]); endFlag = false; } } if(endFlag) break; } //출력 for(int i = 0; i <=4; i++) cout << a[i] <<" "; return 0; } | cs |
코드 설명
배열 a : 정렬하고자 하는 데이터 입니다.
endFlag : 정렬 과정 중에서 데이터의 교환(swap)이 일어나지 않으면, 정렬된 상태이므로 이 때 탈출하기 위한 신호(Flag) 변수입니다.
Line 5 - 10 : 데이터의 위치를 바꾸는 함수 정의입니다.
Line 19 : 매 회전마다 교환 여부를 파악하기 위해 true로 초기화
Line 21 -24 : 인접한 데이터의 순서가 맞지 않으면 교환하고 endFlag를 false로 변경하여 탈출하지 않습니다.
Line 26 : endFlag 값을 보고 정렬 완성 상태를 파악한 후 반복문을 끝낼지 결정하는 부분입니다.
시간 복잡도
버블 정렬을 사용했을 때 최악의 경우는 정렬하고자 하는 방향의 반대로 구성된 데이터들을 정렬할 때 입니다.
다시 말해서 오름차순으로 정렬하고자 할 경우 내림차순으로 정렬된 데이터들을 오름차순으로 정렬하는 경우입니다.
이 경우에는 endFlag 인해서 중간에 break가 되지 않고, 끝까지 돌아갑니다.
입력 데이터의 크기가 n 일때 시간복잡도를 계산해보면,
1회전 : n-1번비교, 2회전 : n-2번 비교 n-1회전 : 1번 비교
이를 계산하면 n-1 부터 1까지 등차 수열의 합이므로 최고 차항은 n에 대한 2차식이 됩니다.
따라서 시간복잡도는 이 됩니다.
'공부 > 알고리즘' 카테고리의 다른 글
[알고리즘] - 퀵 정렬(Quick sort) #6 (0) | 2019.01.31 |
---|---|
[알고리즘] - 선택 정렬(Selection sort) #5 (0) | 2019.01.16 |
[알고리즘] - 삽입 정렬(Insertion sort) #4 (3) | 2019.01.15 |
[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2 (5) | 2019.01.09 |
[알고리즘] - 알고리즘과 성능 척도 #1 (1) | 2019.01.07 |