두 번째 해결책 각 인덱스의 값을 선택해 적절한 위치에 놓습니다.
해결책 1-8-2 원소 바꾸기
void Sort1toN2(int arr[], int size)
{
int temp;
for (int i = 0; i < size; i++) {
while (arr[i] != i + 1 && arr[i] > 1) {
temp = arr[i];
arr[i] = arr[temp - 1];
arr[temp - 1] = temp;
}
}
}
분석
• 이차 시간 복잡도처럼 보이지만, 내부 반복문은 외부 반복문이 몇 번 실행되든지 간에 원소를 한 번만 바꿉니다.
• 내부 반복문이 한 번 처리되면 해당 위치의 원소는 해당 인덱스 값이나 -1을 가집니다.
• 시간 복잡도는 O(n)입니다.