[C++] [정렬 알고리즘] 선택 정렬 (Selection Sort)
선택 정렬 (Selection Sort) 선택 정렬은 정렬 알고리즘 중 하나이다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 선택 정렬은 정렬 되어있지 않은 데이터 중 최소값을 찾아 맨 앞 값과 자리를 바꾼다. 정렬이 완료된 나머지 데이터를 똑같은 방식으로 정렬하는 것이다. 최악 시간복잡도: O(n^2) 최선 시간복잡도: O(n^2) 평균 시간복잡도: O(n^2) 공간복잡도: O(1) 예시 다음의 배열을 오름차순으로 정렬한다. [ 11, 8, 1, 5, 20, 0 ] 배열에서 최솟값을 찾는다. 최솟값: 0 그리고 정렬되지 않은 배열의 첫 번째 값인 11과 위치를 바꾼다. [ 0, 8, 1, 5, 20, 11 ] 정렬되지 않은 나머지 데이터 중..
2024. 2. 20.
[C++] [정렬 알고리즘] 버블 정렬 (Bubble Sort)
버블 정렬 (Bubble Sort) 버블 정렬은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n^2)로 아주 느리지만 코드가 단순해 자주 사용된다. 버블 정렬을 기본적으로 배열의 두 수(a, b)를 선택한 뒤, 두 수가 정렬되어 있다면 놔두고 그렇지 않다면 두 수를 바꾸는 방식이다. 오름차순으로 정렬할 때는 a b여야 정렬된 것으로 판단한다. 이를 처음부터 끝까지 반복한다. 최악 시간복잡도: O(n^2) 최선 시간복잡도: O(n) 평균 시간복잡도: O(n^2) 공간복잡도: O(1) 예시 다음의 배열을 오름차순으로 정렬한다. [ 11, 8, 1, 5, 20, 0 ] 맨 처음 11과 8을 비교한다. 11 > 8 이므로 두 수를 바꾼다. [ 8, 11, 1, 5, 20, 0 ]..
2024. 2. 2.
