1.5.8 1에서 n까지 정렬하기
문제 1-8 크기 n인 배열이 주어집니다. 이 배열은 1부터 n까지의 고유한 원소를 가집니다. 배열의 원소를 정렬하세요.
첫 번째 해결책 각 인덱스 값을 선택해 적절한 위치로 옮깁니다. 이때 옮기려는 위치에 원래 있던 값을 선택해 이 과정을 반복합니다.
해결책 1-8-1 적절한 위치로 원소 이동하기
void Sort1toN(int arr[], int size) { int curr, value, next; for (int i = 0; i < size; i++) { curr = i; value = -1; /* 원소를 적절한 위치로 옮기기 */ while (curr >= 0 && curr < size && arr[curr] != curr + 1) { next = arr[curr]; arr[curr] = value; value = next; curr = next - 1; } } }
분석
• 이차 시간 복잡도처럼 보이지만, 내부 반복문은 단 하나의 원소만 순회합니다.
• 내부 반복문에서 하나의 원소를 처리하면 이 원소는 해당 인덱스 값 또는 -1을 가집니다.
• 시간 복잡도는 O(n)입니다.