자료의 정렬 - 버블 정렬(Bubble sorting)

버블 정렬(Bubble sorting)

나란히 있는 두 개의 데이터를 계속하여 바꾸어 나가면서 차례대로 정렬하는 방법이다.

정렬이 진행되는 모양이 비누 거품(bubble)과 같다고 하여 붙여진 이름.

버블정렬(Bubble sorting)의 방법

 ① 두 개의 데이터를 계속하여 바꾸어 나가면서 차례대로 정렬하는 방법

 ② 두수를 비교하여 가장 큰 수를 맨 오른쪽에 배치한다.

 ③ 큰 수를 오른쪽으로 이동

버블정렬(Bubble sorting)의 예시

1. 20, 7, 12, 8을 버블정렬을 이용하여 배열해보자.

  위 숫자를 배열해보자.

처음 두 개를 비교해 교체한다.

다시 두 번째 세 번째를 비교해서 교체한다.

다시 세 번째 네 번째를 비교해서 교체한다.

이렇게 끝까지 가면 가장 큰 수가 맨 뒤로 가게 된다.

 

다시 앞에서부터 두 개의 데이터를 계속 비교하여 자리를 바꾸면서 정렬을 하면 정렬이 완료된다.

 

2. 3, 31, 48, 73, 8, 11, 20, 29, 65, 15을 버블정렬을 이용하여 배열해보자.

왼쪽부터 시작해 이웃한 쌍들을 비교해간다.

순서대로 되어 있지 않으면 자리를 바꾼다.

정렬이 완료된 맨 오른쪽 수 73을 대상에서 제외하고 다시 왼쪽부터 시작해 이웃한 쌍을 비교해간다.

정렬이 완료된 맨 오른쪽 수 65를 대상에서 제외하고 위와 같은 작업을 반복한다.

정렬완료.

 

버블정렬(Quick sorting) 알고리즘

버블정렬(Quick sorting) 특징

  -비교횟수 및 자리교환횟수: n(n-1) / 2

  -시간복잡도: O(n²)

 

타 정렬에 비해 이해하기 쉽고 코드도 더 간단하지만, 비교해야할 데이터의 갯수가 많을수록 정렬에

필요한 시간이 많이 필요하다.

 

 

도움되는 사이트

  - https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

정렬되는 모습을 실시간으로 보여주는 사이트이다.

사진으로 보는것보다 직접 정렬되는 모습을 보면 이해하기 더욱 쉽다.