선택 정렬
선택 정렬은 배열을 처음부터 훑어서 가작 작은 수를 제일 앞에 가져다 놓습니다.
그 다음, 다시 배열을 훑어서 두 번째로 작은 수를 두 번째 칸에 가져다 놓습니다. 계속 반복해서 끝까지 정렬합니다.
[5,1,4,7,2,6,8,3] 배열을 처음부터 훑어 가장 작은 1을 앞으로 보냅니다.
[1,5,4,7,2,6,8,3] 다시 훑어 2를 앞으로 보냅니다.
[1,2,4,7,5,6,8,3] 3을 앞으로
[1,2,3,7,5,6,8,4]
[1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,7,8] 정렬 끝
const unorganizedArray = [5, 1, 4, 7, 2, 6, 8, 3];var minIndex, temp, i, j;for (i = 0; i < unorganizedArray.length - 1; i++) {minIndex = i;for (j = i + 1; j < unorganizedArray.length; j++) { // 최솟값의 위치를 찾음if (unorganizedArray[j] < unorganizedArray[minIndex]) {minIndex = j;}}temp = unorganizedArray[minIndex];unorganizedArray[minIndex] = unorganizedArray[i];unorganizedArray[i] = temp;}
선택 정렬의 시간 복잡도
O(N²)
선택 정렬의 공간 복잡도
O(N) → O(1) 상수 이므로 공간 복잡도 무시
선택 정렬(selection sort)의 공간 복잡도는 O(1)입니다.
이는 선택 정렬 알고리즘이 정렬을 수행하는 동안 원본 배열 외에 추가적인 저장 공간을 거의 또는 전혀 필요로 하지 않기 때문입니다.
선택 정렬은 주어진 배열 내에서 가장 작은(또는 큰) 요소를 찾아서 정렬되지 않은 부분의 첫 번째 요소와 위치를 교환하는 방식으로 작동합니다.
이 과정이 배열이 완전히 정렬될 때까지 반복됩니다.
이러한 작업은 추가 배열이나 리스트를 사용하지 않고 원본 배열 내에서 이루어지므로, 선택 정렬은 추가적인 메모리를 거의 요구하지 않으며, 따라서 그 공간 복잡도는 O(1)
출처