62 — 버블 정렬 — 첫 알고리즘

39 가이드는 Python이 정렬을 해 주었습니다. 여기서는 정렬을 직접 만들어 봅니다. 버블 정렬은 알고리즘입니다 — 언제나 목록을 순서대로 끝내는 고정된 단계의 요리법입니다. 이웃한 쌍을 비교해 순서가 잘못이면 맞바꾸고, 어떤 패스에서도 맞바꿈이 없을 때까지 반복합니다.

#단계

1. 처음 두 숫자를 비교합니다. 왼쪽이 더 크면 맞바꿉니다. 맞바꿈에는 세 번째 변수가 필요합니다. 임시가 첫 값을 잡아 두는 동안 숫자들[0]이 두 번째 값의 자리를 차지합니다:

   숫자들 = [5, 2, 9, 1, 7, 3]
   if 숫자들[0] > 숫자들[1]:
       임시 = 숫자들[0]
       숫자들[0] = 숫자들[1]
       숫자들[1] = 임시
   말해 숫자들
   

   복사실행해 보기 →

   [2, 5, 9, 1, 7, 3]이 출력됩니다 — 5와 2가 자리를 바꿨습니다.

2. 반복 하나로 목록 전체를 훑으며 이웃한 쌍을 비교하고 필요하면 맞바꿉니다. 이것이 한 패스이고, 가장 큰 값을 끝으로 보냅니다:

   숫자들 = [5, 2, 9, 1, 7, 3]
   n = len(숫자들)
   for j in range(0, n - 1):
       if 숫자들[j] > 숫자들[j + 1]:
           임시 = 숫자들[j]
           숫자들[j] = 숫자들[j + 1]
           숫자들[j + 1] = 임시
   말해 숫자들
   

   복사실행해 보기 →

   [2, 5, 1, 7, 3, 9]이 출력됩니다. 9가 끝까지 거품처럼 떠올랐습니다 — 이름의 유래입니다.

3. 한 패스로는 부족합니다. 2와 1이 아직 순서가 아닙니다. 바깥 반복이 패스를 되풀이합니다. 패스마다 남은 값 중 가장 큰 값이 이미 자리를 잡았으므로 안쪽 반복은 한 칸 더 일찍 멈춥니다 — n - i - 1:

   숫자들 = [5, 2, 9, 1, 7, 3]
   n = len(숫자들)
   for i in range(n):
       for j in range(0, n - i - 1):
           if 숫자들[j] > 숫자들[j + 1]:
               임시 = 숫자들[j]
               숫자들[j] = 숫자들[j + 1]
               숫자들[j + 1] = 임시
   말해 숫자들
   

   복사실행해 보기 →

   [1, 2, 3, 5, 7, 9]이 출력됩니다 — 정렬 완료입니다.

4. 이미 정렬된 목록은 빨리 끝내야 합니다. 플래그가 한 패스에서 맞바꿈을 했는지 기록합니다. 맞바꿈이 없으면 목록이 끝난 것이므로 반복을 break로 나갑니다:

   숫자들 = [5, 2, 9, 1, 7, 3]
   n = len(숫자들)
   for i in range(n):
       바뀜 = False
       for j in range(0, n - 1):
           if 숫자들[j] > 숫자들[j + 1]:
               임시 = 숫자들[j]
               숫자들[j] = 숫자들[j + 1]
               숫자들[j + 1] = 임시
               바뀜 = True
       if not 바뀜:
           break
   말해 숫자들
   

   복사실행해 보기 →

   [1, 2, 3, 5, 7, 9]이 출력됩니다. 플래그가 일찍 끝내는 비결입니다.

5. 이제 전체를 한 프로그램에 담습니다. 목록을 손으로 정렬하고 패스를 하나씩 출력하며 결과를 Python의 sorted()와 비교합니다. bubble.ko.nme로 저장합니다:

   # bubble.ko.nme — 버블 정렬, 내장 정렬과 비교하기
   # 실행: nme 실행 bubble.ko
   #
   # 매 패스에서 이웃한 쌍을 비교하고 순서가 잘못이면 맞바꿉니다.
   # 그래서 가장 큰 남은 값이 끝으로 떠오릅니다. 교환이 없으면
   # 플래그로 일찍 멈춥니다.
   
   숫자들 = [5, 2, 9, 1, 7, 3]
   내장 = sorted(숫자들)
   
   말해 f"시작: {숫자들}"
   말해 ""
   
   n = len(숫자들)
   비교 = 0
   교환 = 0
   
   for i in range(n):
       바뀜 = False
       for j in range(0, n - i - 1):
           비교 = 비교 + 1
           if 숫자들[j] > 숫자들[j + 1]:
               임시 = 숫자들[j]
               숫자들[j] = 숫자들[j + 1]
               숫자들[j + 1] = 임시
               바뀜 = True
               교환 = 교환 + 1
       말해 f"패스 {i + 1}: {숫자들}"
       if not 바뀜:
           말해 "  교환 없음 — 이미 정렬됨, 일찍 멈춤"
           break
   
   말해 ""
   말해 f"내 반복 후:  {숫자들}"
   말해 f"sorted() 후: {내장}"
   
   if 숫자들 == 내장:
       말해 "두 결과가 일치합니다."
   말해 f"{n}개 값에 비교 {비교}번, 교환 {교환}번"
   

   복사실행해 보기 →

6. 실행합니다:

   nme 실행 bubble.ko
   

   복사

   시작: [5, 2, 9, 1, 7, 3]
   
   패스 1: [2, 5, 1, 7, 3, 9]
   패스 2: [2, 1, 5, 3, 7, 9]
   패스 3: [1, 2, 3, 5, 7, 9]
   패스 4: [1, 2, 3, 5, 7, 9]
     교환 없음 — 이미 정렬됨, 일찍 멈춤
   
   내 반복 후:  [1, 2, 3, 5, 7, 9]
   sorted() 후: [1, 2, 3, 5, 7, 9]
   두 결과가 일치합니다.
   6개 값에 비교 14번, 교환 8번
   

   복사

   패스 4에서 교환이 없으므로 플래그가 정렬을 일찍 끝냅니다 — 반복이 다섯 번째나 여섯 번째 패스까지 돌지 않았습니다. sorted()는 Python의 내장 정렬입니다. 순서가 같다는 것은 손으로 쓴 알고리즘에 좋은 확인 신호입니다.

7. 영어는 같은 단계를 show, 영어 변수 이름, 영어 목록으로 씁니다. 전체 영어 프로그램은 영어 가이드에 있습니다.

#직접 해보기

목록을 [9, 8, 7, 6, 5] — 거꾸로 된 순서 — 로 바꾸고 다시 실행해 보세요. 거의 모든 패스가 맞바꾸므로 플래그가 일찍 멈추지 못하고 다섯 패스가 모두 돕니다. 그런 다음 [1, 2, 3, 4, 5], 즉 이미 정렬된 목록을 써 보세요. 첫 패스에서 아무것도 맞바꾸지 않고 프로그램이 한 패스 뒤에 멈춥니다.

#배운 것

• 버블 정렬은 이웃한 쌍을 비교해 순서가 잘못이면 맞바꿉니다.
• 맞바꿈에는 임시 변수가 필요해 값이 사라지지 않습니다.
• 바깥 반복이 패스를 되풀이하고, 패스마다 비교가 하나씩 줄어듭니다 (n - i - 1).
• 바뀜 플래그가 목록이 정렬되면 반복을 일찍 끝내게 합니다.
• 결과를 sorted()와 비교하면 알고리즘을 검증할 수 있습니다.