버블 정렬 ( Bubble Sort )

( 본 게시글은 작성자가 메모용으로 사용하는 용도임을 밝힙니다. 정보가 불확실할 수 있으니 참고 부탁드립니다 )

 

버블 정렬은 데이터를 정렬할때 사용하는 정렬 알고리즘으로, 첫번째 원소 ( 혹은 맨 뒷쪽의 원소부터 )를 선정하여, 데이터값을 오름차순으로 정렬한다는 가정하에 옆에 있는 원소와 값을 비교하여 만약 첫번째 원소가 옆의 원소보다 값이 크다면 서로 스왑을 진행한다.

 

만약 8, 3, 9, 7, 6의 값 배열이 있다고 한다면, 위의 사진처럼 정렬을 진행하며, 총 10번의 비교를 하여 4번 순회를 한다.

해당 버블 정렬의 시간복잡도는 O(n * n)이며 구현은 간단하지만 데이터가 많아지면 연산 속도가 느려지고 매우 비효율적이다.

main 함수 내에서 2중 for문을 통하여 구현하였고, 먼저 i = 0, j = 0일때 첫번째 원소부터 끝까지 비교를 하여 큰 값을 뒤쪽으로 스왑하여 보낸다. 그 다음 i = 1일때 다시 스왑을 진행, 반복한다. 위에서 설명한거처럼 값의 범위가 커지면 커질수록 더 오래걸리고, 효율적이지 못하다.