버블 정렬 이란?
- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
예시 노트
코드
i 는 0 부터 시작하니 0부터 리스트 길이 - 1 만큼 "턴" 을 돌아주고
인덱스 0과 1 , 1과2 , 2와3... 이런식으로 각각의 인덱스끼리 비교해주는 연산은 리스트 길이 - 1 만큼 해준다. ( j도 0 부터 시작하므로 ) 하지만 이렇게 되면 이미 정렬된 숫자를 반복해서 체크해주는 상황이 발생하니 앞선 턴에서 마지막 숫자가 최대값으로 설정이 될터이니 굳이 비교를 해주지 않아도 되기에 " 데이터 길이 - 턴( i값 ) - 1 " 로 설정해준다.
추가적으로 swap = False 로 설정하고 숫자 끼리의 스왑이 이루어지지 않았다는건 이미 정렬된 리스트라는 반증이므로 False 값을 유지했다면 Break 로 for문을 나와 있는 그대로의 리스트를 반환한다.
시간복잡도
데이터 길이 만큼의 n번의 "턴"을 돌아야 하며 해당 리스트 안에서 인덱스 값들끼리의 비교연산 n번이 이루어져야 하므로 O(n^2) 시간 복잡도를 갖는다.
다만, 완전 정렬이 되어있는 경우 리스트 길이 만큼만 반복문을 돌면 되므로 O(n)의 시간복잡도를 갖는다.
비교횟수의 평균값과 최악값
평균값: n^2/2
최악값은 n^2
WILL is ALL