버블 정렬(Bubble Sort)
버블 정렬(Bubble Sort) '인접'한 두개의 원소를 비교하여 자리를 교환하는 방식으로 정렬. 처음부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막으로 정렬된다. 평균 비교 횟수와 평균 자리 교환 횟수는 n(n-1)/2 이다. 따라서 시간 복잡도는 O(n^2)가 된다. 예시) {57, 16, 41, 2, 50, 6} 1. 인접한 두 원소를 비교하여 자리를 교환하는 작업을 마지막 원소까지 반복하여 가장 큰 원소를 마지막 자리로 옮긴다. {57, 16, 41, 2, 50, 6} ===> {16, 57, 41, 2, 50, 6} ===> {16, 41, 57, 2, 50, 6} ===> {16, 41, 2, 57, 50, 6} ===> {16, 41, 2, 50, 57, 6} ===> {..
2021. 4. 2.
선택 정렬(Selection Sort)
선택 정렬(Selection Sort) 기준 위치에 맞는 원소를 '선택'하여 자리를 교환하는 방식으로 정렬. 전체 비교 횟수는 n개의 원소에 대해 n(n-1)/2 이고, 어떤 경우에서나 비교 횟수가 같기 때문에 시간 복잡도는 O(n^2)이다. 예시) {57, 16, 41, 2, 50, 6} 1. 첫 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다. {57, 16, 41, 2, 50, 6} 기준 위치 가장 작은 원소 2 ====> {2, 16, 41, 57, 50, 6} 2. 두 번째 자리를 기준 위치로 정한 후 가장 작은 원소를 선택하여 자리를 바꾼다. {2, 16, 41, 57, 50, 6} 기준 위치 가장 작은 원소 6 ====> {2, 6, 41, 57, 5..
2021. 4. 2.
