알고리즘14 단순 선택 정렬 1. 단순 선택 정렬 단순 선택 정렬은 컬렉션의 가장 작은 요소부터 정렬을 시작해 알맞은 위치로 옮기며 정렬하는 알고리즘입니다. 단순 선택 정렬의 시간복잡도는 O(n^2)입니다. 다음과 같은 배열을 단순 선택 정렬로 정렬해보겠습니다. 우선 배열에서 가장 작은 요소를 선택합니다. 그리고 배열의 맨 앞의 요소와 자리를 바꿔줍니다. 이때 앞 부분(초록칸)은 정렬된 부분이라고 하고, 그 뒤쪽 부분들은 정렬되지 않은 부분이라고 합니다. 마찬가지로 정렬되지 않은 부분에서 가장 작은 요소를 선택해서 정렬되지 않은 부분의 첫 번째 요소와 자리를 바꿔줍니다. 하지만 가장 작은 요소인 3이 맨앞에 있으므로 그대로 남겨둡니다. 이제 남은 부분에 대해서도 가장 작은 요소를 선택하고 맨 앞 요소와 바꾸는 작업을 모든 부분이 완.. 2021. 10. 12. 버블 정렬 Bubble Sort 처음으로 소개드릴 알고리즘은 정렬 중에서도 버블 정렬입니다. 버블이라는 어원은 컵에 액체를 따르면 액체 보다 가벼운 공기 방울(버블)이 컵위로 떠오른다는 점에서 착안하여 버블 정렬이라는 이름이 붙게 되었습니다. 1. 버블 정렬 버블 정렬은 인접한 두 요소의 대소 관계를 비교해서 정렬합니다. 버블 정렬은 가장 간단한 형태의 정렬이며 시간복잡도는 O(n^2)로 요소가 많아질수록 느립니다. 다음과 같은 배열을 오름차순 버블 정렬해보겠습니다. 이렇게 양옆의 요소들끼리 비교하여 요소의 크기가 작으면 앞으로 보내고, 크기가 크면 뒤로 보냅니다. 이 경우에는 배열을 1회 순회하는 동안 버블정렬이 완료되었지만 1회 순회 했음에도 정렬되지 않는 경우가 있습니다. 다음 배열을 보면 1회 수행했음에도 완벽하게 정렬되지 않습.. 2021. 10. 11. 이전 1 2 3 다음 300x250
