부경대 2021 1학기 이산수학 과제모음

1. BubbleSorting, SelectionSorting

버블 정렬과 선택 정렬은 기본적인 정렬 알고리즘으로, 데이터 구조와 알고리즘의 기초를 이해하는 데 중요한 역할을 한다. 두 알고리즘은 직관적이며 구현이 간단하지만, 큰 데이터 세트를 처리할 때는 비효율적일 수 있다. 버블 정렬은 리스트의 각 요소를 연속적으로 비교하며 정렬하는 방식이다. 가장 큰 요소를 리스트의 끝으로 보내는 과정을 반복하면서 리스트의 남은 부분을 정렬해 나간다. 이 과정에서 인접한 두 요소를 비교하여 정렬 순서에 맞지 않는 경우 위치를 교환한다. 한 번의 패스가 끝날 때마다 가장 큰 요소가 마지막으로 이동하므로 이 과정을 나머지 요소에 대해 계속 진행한다. 최악의 경우 시간 복잡도는 O(n²)로, 리스트의 크기가 커질수록 수행 시간이 급격히 증가한다. 이러한 이유로, 버블 정렬은 작은 데이터 세트를 정렬할 때는 괜찮지만, 대규모 데이터에는 적합하지 않다. 반면 선택 정렬은 리스트를 여러 개의 서브리스트로 나누면서 정렬을 수행한다. 이 알고리즘은 리스트에서 가장 작은 요소를 찾아 처음과 교환하고, 그 다음 요소에서 다시 가장 작은 요소를 찾아 교환하는 식으로 진행된다. …