[알고리즘] 버블 정렬이란 (Java, Python)

버블 정렬이란?

차례대로 인접한 두개의 숫자를 비교하여 앞의 숫자가 뒤의 숫자보다 크면 두 숫자의 자리를 바꿔주는 정렬

 

출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=justant&logNo=20204028286

버블 정렬 코드 (Python)

def bubblesort(data):
  for turn in range(len(data) - 1): #전체 데이터 길이의 -1 만큼의 턴을 돈다
    swap = False # swap이 발생하는지 확인한다. 발생하지 않으면 정렬리 됐다고 가정하고 break를 한다.
    for index2 in range(len(data) - turn -1): #1번째 턴 후 맨 마지막에 가장 큰 수가 위치하고 2번째 턴 후 마지막 두개의 숫자가 정렬되기 때문에 turn 수를 비교 횟수에서 빼서 최종 비교 횟수를 줄인다. 
      if data[index2] > data[index2 +1]: # 2개의 숫자를 비교
        data[index2], data[index2 + 1] = data[index2 + 1], data[index2] # 앞의 숫자가 작다면 SWAP 진행
        swap =True
    if swap == False:
      break
  return data

 

버블 정렬 시간 복잡도

버블 정렬은 반목문이 2개가 들어가므로 n^2 만큼의 시간 복잡도가 나온다.

 

버블 정렬 사용 팁

버블 정렬의 가장 큰 장점은 구현이 간단하다는 것이다. 하지만 큰 데이터를 정렬할 때 비효율적이기 때문에 작은 데이터를 정렬할 때 주로 사용해야만 한다.