요소가 3 개 뿐인 100 개 요소의 정수 배열 정렬

배열에 100 개의 숫자가 있다고 가정합니다. 배열의 유일한 값은 1, 2 및 3입니다. 값은 배열 전체에서 임의로 정렬됩니다. 예를 들어, 배열은 다음과 같이 채워질 수 있습니다.요소가 3 개 뿐인 100 개 요소의 정수 배열 정렬

int values[100]; 

for (int i = 0; i < 100; i++) 
    values[i] = 1 + rand() % 3;

어떻게 이런 배열을 효율적으로 정렬 할 수 있습니까?

닫기 - 배열은 본질적으로 연속적입니다 - 숙제와 같은 소리가납니다 –

@Adrian : 나는 연속적인 색인 장소에 배치되지 않는다고 말합니다. – ExploringApple

@AdrianCornish : 나는 동의하지 않을 것입니다. 이것은 완전히 정당한 질문입니다. OP는 이상하게도 그것을 표현했습니다. –

가장 빠른 해결책은되지를 "일종의"모든입니다 : 배열을 통해

결국 완전히 정렬 된 배열을 갖게됩니다.

일반적으로 어레이의 크기에 비해 가능한 작은 범위의 값을 가지고있을 때 유용한 O (n) 정렬 알고리즘이 될 수 있습니다.

2012-09-16 02:53:59 mikera

이것은 버킷 정렬이라고 불리며 이후의 추가 읽기에 관심이있는 경우 기수 정렬의 가장 간단한 형식입니다. –

@mikera : 모든 배열에 값 1,2,3이 없습니다. 100 개의 배열에는 초기화 된 요소가 3 개 뿐이며 나머지 필드는 초기화되지 않았으며 세그먼트 나 쓰레기 값이 있다고 말할 수 있습니다. – ExploringApple

@ExploringApple - 초기화되지 않은 값을 무시하면 기술이 계속 작동합니다. 그러나 1,2와 3 중 하나만 가질 것이라는 것을 안다면 배열을 계산할 필요조차 없습니다 - 배열의 처음 세 요소에 1, 2, 3을 출력하십시오. – mikera

Dutch National flag algorithm이 일반적으로 인용 된 알고리즘이며 실제로는 quicksort (1은보다 작음, 2는 같음, 3은 ~보다 큼)의 파티션 단계입니다. 이 변형에서 중간 부분을 정렬 할 필요가 없습니다.

2012-09-16 15:40:08

답변