버블 정렬(bubble sort)

📔 버블 정렬(bubble sort) 이란

• 서로 인접한 두 원소의 대소를 비교하여 정렬하는 알고리즘
• 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2)
• 오름차순의 경우 1세트(바깥쪽 반복문)이 끝나면 가장 큰 수가 맨 뒤에 오게 된다.
  내림차순의 경우 반대

 

📔 버블 정렬(bubble sort) 예제

• 위의 예제는 오름차순일 경우의 예제이다.
• 앞뒤의 숫자를 비교해서 앞의 숫자가 크면 뒤의 숫자랑 바꾼다.
• 1세트가 끝나면 가장 큰 수가 맨 뒤로 온다. 
• 다음 세트부터는 맨 뒤의 숫자를 빼고 비교를 해준다. (이미 가장 큰 수이기 때문)

 

📔 버블 정렬(bubble sort) 구현

numbers = [5, 3, 8, 1, 2]
print(f'정렬 전: {numbers}')
print()
for i in range(len(numbers)):
    print(f'{i + 1}세트')
    for j in range(len(numbers) - 1 - i):
        if numbers[j] > numbers[j + 1]:
            numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
            print(f'정렬 중: {numbers}')
print()
print(f'정렬 후: {numbers}')

 

📔 버블 정렬(bubble sort) 특징

• 장점
  • 단순한 구현
• 단점
  • 정렬이 불필요한 요소에도 접근해야 한다.
  • 시간복잡도 O(n^2)
• 구현이 간단하지만 매우 비휼적이므로 거의 쓰이지 않음.

 

📔 버블 정렬(bubble sort) 참교자료

처음 프로그래밍을 배울 때 강사님께서 보여준 자료가 생각났다.

아예 처음이신 분은 보는 것을 추천

버블정렬