거의 정렬 된 배열 정렬 (k 이하로 잘못 배치 된 요소)

거의 정렬 된 배열 정렬 (k 이하로 잘못 배치 된 요소)

---

최근에이 인터뷰 질문을 받았습니다.

각 N요소가 k올바른 정렬 순서의 위치 만큼만 ​​잘못 배치 될 수 있다는 점에서 거의 정렬 된 배열이 제공 됩니다. 배열을 정렬하는 공간 및 시간 효율적인 알고리즘을 찾으십시오.

나는이 O(N log k)다음과 같은 솔루션을.

arr[0..n)인덱스 0(포함)에서 N(배타적) 까지 배열의 요소를 의미 함을 나타냅니다 .

• 종류 arr[0..2k)
  • 이제 우리는 그것이 arr[0..k)최종 정렬 위치에 있음을 압니다 ...
  • ...하지만 arr[k..2k)여전히 k!
• 종류 arr[k..3k)
  • 이제 우리는 그것이 arr[k..2k)최종 정렬 위치에 있음을 압니다 ...
  • ...하지만 arr[2k..3k)여전히 잘못 배치 될 수 있습니다.k
• 종류 arr[2k..4k)
• ....
• 정렬 할 때까지 arr[ik..N)완료됩니다!
  • 이 마지막 단계는 2k남은 요소 가 적은 경우 다른 단계보다 저렴할 수 있습니다.

각 단계에서에서 2k요소 를 최대로 정렬하고 각 단계가 끝날 때 최종 정렬 된 위치에 O(k log k)최소한 k요소를 배치합니다. 있습니다 O(N/k)전체 복잡하므로 단계는, O(N log k).

내 질문은 다음과 같습니다.

• 가 O(N log k)최적은? 이를 개선 할 수 있습니까?
• 동일한 요소를 (부분적으로) 다시 정렬하지 않고도이를 수행 할 수 있습니까?

---

Bob Sedgewick 이 그의 논문 작업 (및 후속 작업)에서 보여준 것처럼 삽입 정렬 은 "거의 정렬 된 배열"을 절대적으로 분쇄 합니다. 이 경우 무증상이 좋아 보이지만 k <12이면 매번 삽입 정렬이 승리 할 것입니다. 삽입 정렬이 그토록 잘 수행 되는 이유에 대한 좋은 설명이 있는지는 모르겠지만 Algorithms 라는 제목의 Sedgewick의 교과서 중 하나를 살펴볼 수 있습니다 (그는 여러 언어에 대한 여러 버전을 작성했습니다).

• O (N log k)가 최적인지 여부는 알 수 없지만, 요점은 신경 쓰지 않습니다. k가 작 으면 상수 요소이고 k가 크면 배열을 정렬합니다.

• 삽입 정렬은 동일한 요소를 다시 정렬하지 않고이 문제를 해결합니다.

Big-O 표기법은 알고리즘 클래스에 모두 적합하지만 현실에서는 상수가 중요합니다. 이것을 놓치기는 너무 쉽습니다. (그리고 저는 Big-O 표기법을 가르친 교수로서 이렇게 말합니다!)

---

비교 모델 만 사용하는 경우 O (n log k)가 최적입니다. k = n 인 경우를 고려하십시오.

다른 질문에 대답하려면 힙을 사용하여 정렬하지 않고이를 수행 할 수 있습니다.

최소 2k 요소 힙을 사용하십시오. 먼저 2k 요소를 삽입 한 다음 최소값을 제거하고 다음 요소를 삽입하십시오.

이것은 O (n log k) 시간과 O (k) 공간을 보장하며 힙은 일반적으로 충분히 작은 숨겨진 상수를 갖습니다.

---

점근 적으로 최적의 솔루션 중 하나가 최소 힙을 사용한다는 점이 이미 지적되었으며 Java로 코드를 제공하고 싶었습니다.

public void sortNearlySorted(int[] nums, int k) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int i = 0; i < k; i++) {
    minHeap.add(nums[i]);
  }

  for (int i = 0; i < nums.length; i++) {
    if (i + k < nums.length) {
      minHeap.add(nums[i + k]);
    }
    nums[i] = minHeap.remove();
  }
}

---

k은 (는) 매우 작을 것으로 예상 되기 때문에 삽입 정렬이 아마도 가장 분명하고 일반적으로 허용되는 알고리즘 일 것입니다.

임의의 요소에 대한 삽입 정렬에서는 N 개의 요소를 스캔해야하며 각 요소를 평균 N / 2 위치로 이동하여 총 작업 수를 ~ N * N / 2 개로 지정해야합니다. "/ 2"상수는 big-O (또는 유사한) 특성화에서 무시되어 O (N ² ) 복잡성을 제공합니다.

제안하는 경우 예상되는 작업 수는 ~ N * K / 2이지만 k은 상수이므로 k/2big-O 특성화에서 전체 용어가 무시되므로 전체 복잡성은 O (N)입니다.

---

Your solution is a good one if k is large enough. There is no better solution in terms of time complexity; each element might be out of place by k places, which means you need to learn log2 k bits of information to place it correctly, which means you need to make log2 k comparisons at least--so it's got to be a complexity of at least O(N log k).

However, as others have pointed out, if k is small, the constant terms are going to kill you. Use something that's very fast per operation, like insertion sort, in that case.

If you really wanted to be optimal, you'd implement both methods, and switch from one to the other depending on k.

참고URL : https://stackoverflow.com/questions/2726785/sorting-an-almost-sorted-array-elements-misplaced-by-no-more-than-k