[알고리즘] 버블 정렬

무작위 하게 배치되어 있는 숫자들을 정해진 순서대로 나열하는 것을 정렬이라고 한다.

다양한 정렬 알고리즘 중 버블 정렬에 대해 정리해보고자 한다.

버블 정렬은 인접한 앞뒤 원소를 비교하여 앞에 있는 원소의 크기가 뒤에 있는 원소의 크기보다 더 클 경우 두 원소의 위치를 교환한다.

1. 앞뒤 원소를 비교하여 앞에 있는 원소의 크기가 뒤에 있는 원소의 크기보다 더 클 경우 두 원소의 위치를 교환한다.
   [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   if data[i] > data[i+1]:
       data[i], data[i+1] = data[i+1], data[i]

2. 가장 큰 원소가 배열의 가장 오른쪽에 위치하도록 1번의 과정을 반복한다.
   [70, 31, 3, 72, 20] -> [31, 70, 3, 72, 20]

   [31, 70, 3, 72, 20] -> [31, 3, 70, 72, 20]

   [31, 3, 70, 72, 20] -> [31, 3, 70, 20, 72]

   for i in range(len(data) - 1):
       # 1번 코드 
       if data[i] > data[i+1]:
           data[i], data[i+1] = data[i+1], data[i]

3. 위의 1번 2번 과정을 모든 원소들이 정렬 될 때까지 반복한다.

   for j in range(len(data) - 1):
       # 2번 코드
       for i in range(len(data) - 1):
         # 1번 코드 
         if data[i] > data[i+1]:
             data[i], data[i+1] = data[i+1], data[i]

4. 최적화 단계, 2번 과정이 끝나면 가장 큰 원소가 가장 오른쪽에 위치하기 때문에 마지막 원소는 비교할 필요가 없다. 또한, 이미 정렬이 완료 되었을 경우 반복문을 종료한다.

   def bubblesort(data):
       # 3번 코드
       for j in range(len(data) - 1):
           # 최적화
           swap = False
           # 2번 코드, 최적화 len(data) - j - 1
           for i in range(len(data) - j - 1):
               # 1번 코드 
               if data[i] > data[i+1]:
                   data[i], data[i+1] = data[i+1], data[i]
                   swap = True
           if not swap:
               break
       return data