-
버블 소트란?
인접한 원소 간의 비교를 통해 정렬하는 알고리즘으로써, 시간복잡도는 O(n2)이다.
시간복잡도가 왜 O(n2) 인가요?
버블소트는 인접한 값과의 숫자 비교를 반복해나가며 정렬을 진행합니다.
궁극적으로 우리가 원하는 오름차순의 배열을 얻기 위해서는 N개의 값들을 비교하는 과정을 N번 반복 했을 때, 정렬이 완료 되기 때문에 O(n2)라고 칭할 수 있다.
인접한 수끼리의 비교가 이루어 지는 경우, 자연스럽게 가장 큰 수가 배열의 맨 뒤로 향하는 현상을 확인 할 수 있을 것인데, 그러한 이유로 위와 같은 작업을 배열의 길이인 N번 반복이 완료 됬을 때 비로소 정렬이 완료 되었음을 알 수 있는 것이다.
버블 소트 예제
# 최초 문자열 arr = [ 7, 6, 5, 4, 3 ] # task 1 [ 7 > 6 ] arr = [ 6, 7, 5, 4, 3 ] # task 2 [ 7 > 5 ] arr = [ 6, 5, 7, 4, 3 ] # task 3 [ 7 > 4 ] arr = [ 6, 5, 4, 7, 3 ] # task 4 [ 7 > 3 ] arr = [ 6, 5, 4, 3, 7 ]
버블소트 _ 파이썬 코드
import random def bubbleSort(arr): for i in range(len(arr)-1, 0, -1) : # 각 회차마다 가장 큰 수가 맨 뒤로 오기 때문에 # 배열의 총 길이에서 -1 줄여가며 진행해준다. for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # 인접 값들끼리의 비교를 통해 정렬 return arr arr = random.sample(range(100), 10) print(arr) print(bubbleSort(arr))
'CS > Algorithm Theory' 카테고리의 다른 글
[ Algo Theory ] 버블 / 삽입 / 선택 정렬 (0) 2021.05.22 [Algorithm Theory] 그래프란? (0) 2021.03.14 [알고_이론] 퀵정렬 (Quick sort _ by python ) (0) 2021.01.27 [알고_이론] 선택정렬 (Selection sort _ by python ) (0) 2021.01.27 [알고_이론] 삽입정렬 (insertion sort _ by python ) (0) 2021.01.27 댓글