15. 버블(Bubble) 정렬 알고리즘

1. 개요

 버블 정렬은 모든 정렬중에서 가장 쉬운 알고리즘이며 가장 비효율적인 알고리즘이다. 매 반복마다(가장 겉의 루프) 최대값이

제일 끝에 위치하기 때문에 이 모습이 마치 물 속의 버블(공기방울)이 수면위로 올라올수록 점점 커지는 모습을 형상화한다

하여 버블 정렬이라는 이름이 붙었다. 버블 정렬은 정말 데이터 수가 작아 속도에 영향을 안미치는 경우 사용하며 혹은 이미

데이터가 정렬되었는지 탐지할 수 있다는 것 뿐이다.

 일반 버블 정렬의 복잡도는 O(n^2) 

 개선된 버블 정렬일 경우 정렬 상태를 탐지하는 복잡도는 O(n) (정렬 속도가 아님)

2. 코드

2-1) 메인

2-2) 데이터 생성 ( O(n)으로 중복되지 않는 랜덤 숫자 배열 생성 )

2-3) 버블 정렬 알고리즘

2-4) 개선된 버블 정렬 알고리즘

2-5) 출력

3. 해설

 면접 때 코딩 문제로 한번 나왔다. 하지만 그 당시 나에겐 버블 정렬은 딱히 알고리즘이 아니었기 때문에 그런 정렬은 

모른다고 저는 퀵 정렬만 씁니다. 라고 말했다가 퀵 정렬을 코딩했다. 지금 생각하면 패기가 넘쳤던 면접이다. 번외로

대학 때 춤동아리에서 춤췄다고 말했다가 무반주로 춤도 췄다. 중요한 건 이 면접에 내 인생의 첫 면접이었다. 결과는 합격!

 기억해야 할 것.   

 1) 2개의 루프, 외곽 루프의 시작 인덱스는 맨 마지막에서 감소하며 안쪽 루프는 0부터 시작하여 증가한다.

 2) 스왑 과정이 안쪽 루프에 존재 

    (버블 정렬과 비교되는 선택 정렬의 경우 외곽 루프에 스왑 존재. 그래서 O() 같지만 선택 정렬이 조금 더 빠르다.)