무민이의 반반무많이

Bubble Sort (버블 정렬) 본문

Algorithm/Theory

Bubble Sort (버블 정렬)

M00min 2016.08.16 23:18

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)


Bubble Sort(버블 정렬)는 왼쪽 끝에서부터 시작해서, 인접하는 두 항목의 값을 비교하여 올바른 순서로 되어있지 않으면, 두 값을 서로 교환하는 정렬 방식을 말한다. 아래 예제를 통해 자세히 알아보자.


1. 먼저 배열에 아래와 같이 5개의 값이 있다고 하자. 우리는 이 값을 오름차순으로 정렬하고자 한다.


2. 배열의 첫 번째 값과 두 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 4보다 크므로 자리가 바뀐다.


3. 배열의 두 번째 값과 세 번째 값을 비교하여, 두번째 값이 더 큰 경우 자리를 바꿔준다. 여기서는 5가 1보다 크므로 자리가 바뀐다.


4. 배열의 세 번째 값과 네 번째 값을 비교하여, 세 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 3보다 크므로 자리가 바뀐다.


5. 배열의 네 번째 값과 다섯 번째 값을 비교하여, 네 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 5가 2보다 크므로 자리가 바뀐다.


6. 배열의 다섯 번째 값의 정렬이 완료되었다. 정렬 결과 가장 큰 값이 다섯 번째 위치에 왔다.


7. 마찬가지로 배열의 첫 번째 값과 두 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 1보다 크므로 자리가 바뀐다.


8. 배열의 두 번째 값과 세 번째 값을 비교하여, 두 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 3보다 크므로 자리가 바뀐다.


9. 배열의 세 번째 값과 네 번째 값을 비교하여, 세 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 4가 2보다 크므로 자리가 바뀐다.


10. 배열의 네 번째 값의 정렬이 완료되었다. 정렬 결과 두 번째로 큰 값이 네 번째 위치에 왔다.


11. 배열의 첫 번째 값과 두 번째 값을 비교하여, 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 1이 3보다 작으므로 자리가 바뀌지 않는다.


12. 배열의 두 번째 값과 세 번째 값을 비교하여 두 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 3이 2보다 크므로 자리가 바뀐다.


13. 배열의 세 번째 값의 정렬이 완료되었다. 정렬 결과 세 번째로 큰 값이 세 번째 위치에 왔다.


14. 배열의 첫 번째 값과 두 번째 값을 비교하여 첫 번째 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 1이 2보다 작으므로 자리가 바뀌지 않는다.


15. 배열의 두 번째 값의 정렬이 완료되었다. 정렬 결과 네 번째로 큰 값이 두 번째 위치에 왔다.


16. 배열의 첫 번째 값의 정렬의 완료되었다. 정렬 결과 다섯 번째로큰 값이 첫 번째 위치에 왔다.


지금까지 Bubble Sort(버블 정렬)의 오름차순 정렬에 대해 알아보았다. 정렬의 과정이 마치 거품과 같다고 하여, Bubble Sort(버블 정렬)라고 불린다. 내림차순 정렬시에는 앞의 값과 뒤의 값을 비교하여, 앞의 값이 더 작은 경우 자리를 바꿔서 작은 수가 더 뒤에 위치하도록 정렬을 해나가면 된다.


<오름차순 정렬>


<내림차순 정렬>

'Algorithm > Theory' 카테고리의 다른 글

Insertion Sort(삽입 정렬)  (0) 2016.08.16
Selection Sort(선택 정렬)  (0) 2016.08.16
Bubble Sort (버블 정렬)  (0) 2016.08.16
0 Comments
댓글쓰기 폼