[알고리즘] 정렬 알고리즘들(버블 정렬, 선택 정렬, 삽입 정렬)의 작동 방식과 비교 횟수 분석

[1]버블 정렬

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 정렬하는 방식이다. 이 알고리즘의 기본 아이디어는 리스트의 처음부터 끝까지 반복하며, 인접한 요소들을 비교한 후에 잘못된 순서로 되어 있으면 이들을 교환하는 것이다. 이렇게 하면 가장 큰 요소가 리스트의 끝으로 `버블`처럼 떠오르게 되므로 버블 정렬이라고 명명되었다. 버블 정렬의 작동 방식은 다음과 같다. 리스트의 모든 요소를 반복적으로 검사하여 각 요소를 그 다음 요소와 비교한다. 만약 현재 요소가 다음 요소보다 크면 두 요소를 교환한다. 이 과정을 리스트의 끝까지 반복하면, 가장 큰 값이 리스트의 마지막으로 이동하게 된다. 그 다음에는 리스트의 마지막 요소를 제외하고 같은 과정을 반복한다. 이 과정은 리스트가 정렬될 때까지 계속된다. 최악의 경우 리스트가 완전히 역순으로 되어 있다면 모든 요소를 다 비교해야 하므로 O(n^의 시간 복잡도를 가진다. 버블 정렬은 최적화가 가능하다. 만약 어떤 반복에서 교환이 이루어지지 않았다면, 이는 리스트가 이미 정렬되어 있다는 것을 의미하므로 알고리즘을 조기에 종료할 수 있다. 그렇게 함으로써…