정렬 알고리즘 - Bubble
버블정렬(Bubble) 이란?
두 인접한 원소를 검사하여 정렬하는 방법이다.
시간복잡도는 O(n^2)으로 느리지만, 구현하기 매우 쉽다.
def bubble(array):
print("bubble")
for i in range(len(array)-1):
for j in range(len(array)-1-i):
if array[j] > array[j+1]:
array[j],array[j+1] = array[j+1],array[j]
맨 앞 숫자부터 다음 숫자로 가면서 바로 뒤에 있는 숫자들과 비교하여, 뒤에 있는 숫자가 더 작을때마다 서로 교환하는 방식이다.
위 코드가 돌아가는 단계를 세세히 뜯으면 아래와 같다.
Array = [3,4,5,2,1] 일때
1번째 큰 루프 시작
1번째 숫자 3 비교 (1번째 숫자 == 0번 인덱스 숫자 일때)
3 > 4 : 뒤에 있는 숫자가 더 크다. 변화 없음
2번째 숫자 4 비교
4 < 5 : 뒤에 있는 숫자가 더 크다. 변화 없음
3번째 숫자 5 비교
5 > 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,5,1]
4번째 숫자 5 비교
5 > 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,1,5]
첫번째 큰 루프 끝. (for i)
2번째 큰 루프 시작
Array = [3,4,2,1,5]
1번째 숫자 3 비교
3 < 4 : 뒤에 있는 숫자가 더 크다. 변화 없음
2번째 숫자 4 비교
4 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,4,1,5]
3번째 숫자 4 비교
4 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,1,4,5]
두번째 큰 루프 끝. 5까지 비교하지 않는 이유는 첫번째 큰 루프때 제일 큰 숫자 자리가 정해진다. 같은 원리로 두번째 루프가 끝나면 2번째로 큰 숫자 자리가 정해진다.
3번째 큰 루프 시작
Array = [3,2,1,4,5]
1번째 숫자 3 비교
3 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,3,1,4,5]
2번째 숫자 3 비교
3 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,1,3,4,5]
3번째 큰 루프 종료.
4번째 큰 루프 시작
Array = [2,1,3,4,5]
1번째 숫자 2 비교
2 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [1,2,3,4,5]
4번째 큰 루프 종료.
큰 루프 종료
Author And Source
이 문제에 관하여(정렬 알고리즘 - Bubble), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@areum0921/정렬-알고리즘-Bubble저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)