버블 정렬

샤핑

 

 

이번 시간에는 버블 정렬의 동작 원리를 살펴보겠습니다.

 

버블 정렬 (Bubble Sort) - "두 값을 비교해서 오른쪽으로 밀어내자!"

- 두 인접한 원소를 검사하여 정렬하는 방법입니다. 왼쪽 값이 오른쪽 값보다 더 큰지 작은지에 따라 맞바꿀지를 결정합니다. 이렇게 계속 맞바꿔서 최대값 또는 최소값을 오른쪽으로 계속 밀어내는 것입니다.

 

 

 

위의 배열로 알고리즘의 원리를 살펴보겠습니다. 여기서, 오름차순으로 정렬할 것인데, 오름차순은 왼쪽 값이 오른쪽 값보다 더 작으므로, 왼쪽 값이 더 크다면 서로 맞바꿔야 합니다.

 

 

 

왼쪽 값: 4

오른쪽 값: 3

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

따라서, 서로 맞바꾸면 위와 같은 형태가 됩니다.

 

 

 

왼쪽 값: 1

오른쪽 값: 4

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

왼쪽 값: 4

오른쪽 값: 5

왼쪽 값이 더 크지 않으므로 그대로 둡니다.

 

 

 

왼쪽 값: 5

오른쪽 값: 2

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

여기까지 하면, 가장 큰 숫자가 맨 오른쪽으로 간 것을 볼 수 있습니다. 이 값은 이미 정렬되었으므로 정렬 대상에서 제외합니다.

 

 

 

왼쪽 값: 3

오른쪽 값: 1

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

왼쪽 값: 3

오른쪽 값: 4

왼쪽 값이 더 크지 않으므로 그대로 둡니다.

 

 

 

왼쪽 값: 4

오른쪽 값: 2

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

여기까지 하면, 두 번째로 큰 숫자가 오른쪽으로 간 것을 볼 수 있습니다. 이 값 역시 이미 정렬되었으므로 정렬 대상에서 제외합니다.

 

 

 

왼쪽 값: 1

오른쪽 값: 3

왼쪽 값이 더 크지 않으므로 그대로 둡니다.

 

 

 

왼쪽 값: 3

오른쪽 값: 2

왼쪽 값이 더 크므로 서로 맞바꿉니다.

 

 

 

왼쪽 값: 1

오른쪽 값: 2

왼쪽 값이 더 크지 않으므로 그대로 둡니다.

 

 

 

이렇게 하면, 오름차순으로 깔끔하게 정렬된 것을 볼 수 있습니다. ^^

이 알고리즘을 소스 코드로 표현하면 아래와 같습니다.

 

소스 코드

 

 

출력 결과) 1 2 3 4 5

 

 

<출처>

위키백과 - 거품 정렬

소스 코드: https://github.com/jhs951101/BubbleSort

 

 

728x90