Java collection sort()를 사용하거나 직접 구현해야합니까?

Question

배열을 증가 순서로 정렬해야합니다. 배열 내의 가능한 값은 1에서 9 사이이며 반복되는 값이 많습니다. (fyi : 나는 스도쿠 해결사에서 일하고 있고, 백 트랙킹을 사용하여 최소한의 가능성으로 상자를 시작하는 퍼즐을 풀려고 노력하고있다.)

나의 제 아이디어는 쉘 정렬을 사용하는 것이다.

나는 좀 훑어 보았고 자바 컬렉션이 "하위 목록의 가장 낮은 요소가 상위 하위 목록의 가장 낮은 요소보다 작은 경우 병합이 생략 된"수정 된 mergesort를 사용한다는 사실을 발견했습니다.

그래서 내 자신의 정렬 알고리즘을 구현하면 성능 차이가 눈에 띄게되는지 알고 싶습니다. 만 9 개 가능한 값이있는 경우

Answer 1

, 당신은 아마 counting sort합니다 - 기본 개념은 다음과 같습니다

• 9.

• 으로 반복 배열을 크기의 카운트의 배열을 만들고을 증가 각 요소에 대한 개수 배열의 해당 색인

• 카운트 어레이를 통해 원래 어레이를 다시 만듭니다.

이것의 실행 시간이 O(n + 9) = O(n), 어디-으로 표준 API 정렬의 실행 시간이 될 것입니다 O(n log n) 될 것이다.

그렇습니다. 자바 API가 사용하는 표준 비교 기반 정렬보다 빠를 가능성이 높지만 벤치 마크 만 알려주고 데이터의 크기에 따라 달라질 수 있습니다. 일반적으로

---

, 나는 좋을 것 당신 먼저 표준 API 종류를 사용하여 시도하고 빠른 충분 있는지 - 당신이 비교 함수를 정의해야하는 경우를 제외하고 (코드 문자 그대로 단지 1 라인의), 자신의 정렬 기능을 만들기위한 꽤 많은 것들과 비교해 볼 때 상당히 많은 노력이 필요하다.

충분히 빠르지 않은 경우 데이터와 잘 작동하는 정렬을 찾아 구현하십시오. (데이터 정렬에서 멀리 경우 실행 시간이 꽤 끔찍한하지만)

• Insertion sort 이미 거의 정렬 된 데이터에 잘 작동 예를 들면 다음과 같습니다.

• Distribution sorts은 숫자 데이터가있는 경우 고려해 볼 가치가 있습니다. 주석에서 언급 한 바와 같이

---

는 Arrays.parallelSort (from Java 8)은하지 않는 sort (그것은 멀티 스레드 이후 작업도 고려 가치가 옵션입니다, 자신을 할 수있는 노력의 꽤 확실히이다 ... 효율적으로).