개발자로 홀로 서기

안녕하세요. Mommoo 입니다.

오늘은 정렬 중에, 학습하기 쉬운 버블정렬에 대해 포스팅 합니다.

버블 정렬이 어떻게 진행되는지 gif파일로 만들어 봤습니다.

버블정렬?

물속에 있는 거품이 수면위로 보글보글 하게 올라오는 것처럼,

제일 무거운 원소가 배열의 최상단까지 올라가는 과정을 마치 거품이 올라가는 것과 같다 하여 

이름을 버블정렬이라 지었습니다.

버블정렬의 원리

만약 아래와 같은 배열이 있다고 가정해봅시다.

위의 배열을 내림차순으로 정렬 해보려고 합니다. (1 2 3 4 5 6)

버블정렬은 정렬이 안된 배열의 범위내에서, 서로 붙어 있는 배열 요소 2개씩 비교해 나갑니다.

붙어있는 배열요소 2개를 비교했을시, 큰쪽을 뒤쪽으로 배치 한후, 

처음 비교 요소중 2번째 요소와 다음 요소(3번째요소) 를 또 비교합니다. 마찬가지로 2개의 요소중 큰 요소를 배치하구요.

이런식으로 배열의 끝까지 비교를 했을시, 첫 배열범위에서 제일 큰 수가 맨 뒤로 배치 됩니다.

아래의 예시를 보시면 더욱 이해가 잘 될겁니다.

1세트를 마치게 되면 첫번째 배열 범위(1~6번째)에서 제일 큰 숫자인 6이 맨 뒤에 배치 됩니다.

또한, 1세트를 마치면 맨뒤에 요소 6은 정렬이 완료 된 상태 입니다. 따라서, 배열범위를 변경해야 합니다. (1~5번째로 변경)

아래는 2세트 에서의 예시 입니다.

2세트를 마치게 되면 바뀐 배열 범위(1~5번째)에서 제일 큰 숫자인 5가 배열 범위 맨 뒤에 배치됩니다.

또한, 맨뒤의 요소 5,6은 정렬이 완료 된 상태 이므로, 배열 범위를 변경합니다.(1~4번째로 변경)

이런식으로, 한세트가 끝나면, 배열 범위를 바꾼 후 2개씩 비교를 해 나가면, 배열 뒤쪽에서는 내림차순으로 정렬이 됩니다.

결과적으로, 버블정렬의 가장 큰 특징은 범위 내의 제일 큰 숫자를 뒤로 배치 하는 것과, 배열범위를 하나씩 줄여가는것 입니다.

지금까지의 설명을 읽고, 맨 위의 gif를 다시 본다면 재밌게 보실 수 있습니다!.

버블정렬의 성능

소트의 성능을 생각해볼때, 공간복잡도와 시간복잡도를 생각해보게 됩니다.

공간 복잡도는 말그데로, 배열만을 썻느냐, 아님 추가 배열을 썼느냐 등을 가리는 것이고

시간 복잡도는 정렬을 하는데 시간이 얼마나 소요 됬는지를 알아봅니다.

정렬은 공간 복잡도 보다, 시간 복잡도가 직결되므로 시간 복잡도만 알아볼것입니다.

시간복잡도는 보통 빅O 표기법으로 표시를 하는데,

빅O 표기법은 걸린시간의 최악의 경우만을 표기합니다. 

또한, 걸린 시간에서 부수적인 계산요소들은 생략하여 표기합니다.

버블정렬의 빅O 표기법을 구해보자면 아래와 같습니다.

만약 배열이 정렬 된 상태에서 정렬이 걸린시간을 생각하면, 한번만 비교해본후, 

정렬된걸 감지한후, 더이상 비교와 교환을 하지 않습니다. 

만약 배열의 크기가 n이라 하면, 교환은 한번도 이루어지지 않고, 비교만 (n번)합니다. (최선의 상황)

위의 배열 예시는 정렬이 하나도 되지 않은 최악의 상황입니다. 오히려 역으로 정렬된 상태입니다.

위의 배열은 비교를 n번 + n-1번 + n-2번 + n-3번 + n-4번 +.....+ 1번 하므로, 결국 n*(n+1)/2 의 비교횟수와

n*(n+1)/2의 교환 횟수를 가집니다. (최악의 상황) 

따라서 빅O 표기법의 조건중 하나인 최악의 상황 n*(n+1)/2으로 따지는데, 

이것을 아래와 같이 부수적인 계산요소들은 생략합니다.

따라서 빅O 표기법은 O(n^2) 입니다.

이는 앞으로 볼 정렬에 비교한다면, 느린편에 속합니다.

다음 포스팅은 버블정렬 - 자바코드 편을 포스팅 하겠습니다.

읽어주셔서 감사합니다.

안녕하세요. Mommoo 입니다.

앞으로 버블 정렬,선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬을 만들어 볼텐데요,

이러한 정렬 들을 만들기 쉽게, 디버깅을 편하게 하기 위해 조상 클래스 Sort를 만들어 보고자 합니다.

기본목표는 아래와 같습니다.

• 정렬들간의 비교분석을 위해 같은 배열 데이터를 참조하게 한다.
• 데이터의 갯수만 변경하면 데이터가 갯수에 맞게, 랜덤값이 자동적으로 생성되게 한다.
• 정렬들간의 비교를 위하여 공통된 행위 설계. ( sort할때 걸리는 시간, sort가 성공했는지 여부, 규격화된 디버깅 설계 등등...)
• Comparable 인터페이스를 구현 해, Sort클래스를 상속받는 수 많은 정렬 클래스들이 시간 순으로 랭크화 하게 한다.

먼저 완성된 소스입니다.

특이점등을 설명해드리자면...

▶  6번의 DATA_LENGTH 변수는 추후에, 데이터 갯수를 표시하기 위해 public으로 공개했습니다.

▶  16번의 static 초기화 부분에서는 자동적으로 랜덤 값을 넣어주며, sort가 성공했는지 여부를 알기 위해

미리 sort된 배열도 하나 만들었습니다.

▶  각각의 자식 클래스마다 공통된 배열의 값을 참조를 해야하지만, 자식만의 배열을 가져야 하므로,

28번의 배열을 protected로 추가했습니다.

▶  36, 39번의 메서드는 각 자식 클래스마다 독립적인 내용이므로 자식에게 구현을 맡겼습니다.

▶  42번의 start 메서드는 자식 클래스가 start 메서드를 사용했을시, sort가 진행되고 sort 진행시간이 기록됩니다.

또한, 프린팅을 줄 맞춰서 예쁘게 하기위해, 프린팅 정보중 너비가 제일 긴 텍스트의 길이를 저장했습니다.

▶  58번의 swap 함수는 sort에서 빠지지 않는 swap기능을 미리 구현해놓았습니다.

▶  117번의 toString메서드는 자식 클래스의 소트가 진행됬을경우, 정보를 프린팅 하기위해 구현했습니다.

▶  129번의 compareTo 메서드는 Comparable을 구현하기위해 오버라이딩 했습니다. 추후에

자식클래스들을 시간순으로 정렬하기 위해 작성했습니다.

준비한 내용은 여기까지 입니다.

다음 포스팅은, 이러한 Sort 클래스를 상속받아 Bubble 소트를 만들어보겠습니다!