버블 정렬

-버블 정렬이란

그림이 허접하여 죄송합니다.ㅋㅋ

 

정렬하려는 배열의 값들이 5, 4, 9, 1, 7이고 오름차순으로 정렬하려고 가정했을 때,

1. 처음 인덱스에 있는 값부터 시작하여 끝 인덱스 -1까지 바로 다음에 있는 값과 비교하여 오른쪽에 있는 값이 더 크다면 두 값을 교환한다.

2. 이를 배열에 들어있는 값의 개수만큼 반복한다.

그리고 그림과 같이 값을 교환할 때 나오는 화살표들이 거품이 보글보글 일어나는 것과 비슷하게 생겼다고 하여 버블 정렬이라고 한다.

 

-버블 정렬의 시간 복잡도

버블 정렬은 처음 인덱스부터 끝 인덱스까지 순환(n)하며 값을 교환하고, 이를 다시 배열에 들어있는 값의 길이만큼 돌리는(n) 정렬 알고리즘이기 때문에 n * n =  n^2이라는 시간 복잡도가 나온다.

 

-코드(C++)