버블 정렬(Bubble Sort)

버블 정렬은 연속된 두 개의 값을 비교해 기준에 해당하는 값을 뒤로 넘겨 정렬하는 방식이다.

그렇기에 맨 뒤에서부터 값이 완성되어 나가며 순서는 아래와 같다.

 

-오름차순 기준

1. 1번 인덱스와 2번 인덱스를 비교한다.

2. 1번 인덱스가 더 클 경우 서로 위치를 바꾼다.

3. 2번 인덱스와 3번인덱스를 비교한다.

4. 2,3 과정을 마지막 인덱스까지 반복한다.

5. 다시 1번부터 4번을 반복하되 마지막 인덱스 - 정렬 완료된 수만큼까지만 한다.

   ㄴex) 2번째 사이클인 경우 첫번째 싸이클로 마지막값이 정렬 되 있으므로 그 앞에까지만 돌린다.

 

 시간복잡도는 (배열의 크기) * (n^2)이다.

 

코드로 구현 시 이렇게 되며, 여기에

다음과 같은 배열을 입력 시

다음과 같은 결과가 나온다.

간단하게 두 번째 사이클 첫번째 과정까지만 진행 순서를 보자.

 

1. 0번 인덱스(9)와 1번 인덱스(7)를 비교한다.

2. 0번 인덱스(9)가 더 크므로 두 인덱스간 값을 바꾼다.

   ㄴ이 과정으로 0번인덱스는 7, 1번 인덱스는 9가 된다.

3. 1번 인덱스(9)와 2번 인덱스(5)를 비교한다.

4. 1번 인덱스(9)가 더 크므로 두 인덱스간 값을 바꾼다.

5. 이 과정을 마지막 인덱스까지 반복해 9번 인덱스의 값이 9가 되었다.

    ㄴ여기서 한 싸이클이 끝난다.

6. 0번 인덱스(7)와 1번 인덱스(5)를 비교한다.

7. 0번 인덱스가 값이 더 크므로 두 인덱스간 값을 바꾼다.

8. 이 과정을 반복하되, 이미 값 하나가(1~5과정) 맨 끝에서 정렬이 되어 있으므로 그 앞에까지만 진행한다.

   ㄴ즉, 현재 싸이클 - 1만큼 진행한다 생각하면 된다.