(CS50)-알고리즘 기초(버블정렬)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 버블 정렬
• 배열

버블 정렬

• 두개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법.
• 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중
• 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할수 있음.

실행

[버블정렬예시]

• 제일 먼저 배열 안에서 5와 1을 비교 -> 1이 5보다 작기 때문에 두 수는 교환.
• 다음에 5와 6을 비교하는데 올바른 순서로 되어있기 때문에 그 다음 요소로 넘어감.
• 다음은 6과 2를 비교하고 계속 같은 방식으로 비교하여 교환.
• n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게 됨
• 그렇기에 다음 정렬에서는 n-1개의 원소를 정렬해주면 됨.
  • 이 예시에서는 다음 정렬은 1, 5, 2, 4, 3 다섯 개의 숫자만 가지고 수행됨.

정리

• n개의 요소를 정렬해주기 위해서 버블정렬은 n-1번 실행해주어야 함.
• 최악의 상황인 경우 최대한의 횟수를 실행해줘야 하므로 경제적이지 않음.