선형 시간에 배열을 정렬하는 알고리즘

Question

Skiena 's Algorithm Design Manual을 읽었으므로이 문제를 해결할 수 없습니다.

배열 A가 각각 빨간색, 흰색 또는 파란색 인 n 개의 요소로 이루어져 있다고 가정합니다. 모든 붉은 색이 빨간색 흰색에 대한 정확하고 효율적인 알고리즘을 찾기 모든 유일한 작업은 키에서 허용 블루스 있습니다

Examine(A,i) { report the color of the ith element of A. 
Swap(A,i,j) { swap the ith element of A with the jth element. 

전에 오는 모든 백인, 이전에 올 수 있도록 우리는 요소를 정렬 추구 - 파란색 정렬. 선형 시간 솔루션이 있습니다.

quicksort를 사용하여 시도해 보았습니다. 3 피벗에서 해결할 수 있어야하지만 빠른 정렬에서 복제본을 볼 때 무엇을해야할지 모르겠습니다.

Answer 1

매우 간단한 선형 시간 알고리즘은 다음

1. 번 반복 배열 통해 rcount, wcount, bcount 같이 빨강, 백색과 청색의 카운트를 발견.

2. 0, rcount, (rcount + wcount)에서 시작하는 세 개의 카운터가 있습니다. 그들을 rcounter, wcounter 및 bcounter라고 부르십시오. 각 카운터에 대한

3. , 당신이 컬러가 발생할 때마다, 0에서 시작하여 그 범위

4. 에 적합한 하나가 아닌 색에 도달 할 때까지 증가 : 을 수행합니다. 색상이 빨간색이고 (카운터 <)이면 rcount를 증가시키고 계속하십시오 (범위에 따라 흰색과 파란색과 마찬가지로) b. 색상이 흰색 인 경우, wcounter 및 wcounter와 교환하십시오. ++ c. 색상이 파란색 인 경우, bcounter 및 bcounter와 교환하십시오. ++

루프가 끝나면 배열이 완성됩니다.

Answer 2

이것은 실제로는 으로 알려진 Dijkstra가 제시 한 매우 유명한 문제입니다.

위와 연결된 위키 백과는 이러한 문제와 다른 문제에 어떻게 대처할 수 있는지에 대한 꽤 적절한 설명을 제공합니다.

3 방향 퀵 소트가 단독으로 적용될 수도 있습니다. This presentation은 어떻게하는지 잘 알려줄 것입니다 (관련 내용은 37 페이지에서 시작). 또한 구별되는 키의 수가 3이므로 O (n)에서 작동합니다 (43 페이지에서 설명).

Answer 3

처음에는 0을 가리키는 빨간색 포인터와 배열의 마지막 요소를 가리키는 파란색 포인터라는 두 개의 포인터를 유지 관리합니다.

Examine 기능을 사용하여 왼쪽에서 오른쪽으로 배열을 스캔하십시오.

• 빨간색 요소가 나타날 때마다 Swap 함수를 사용하여 현재 빨간색 포인터로 바꾸고 빨간색 포인터를 증가시킵니다.
• 마찬가지로 파란색 요소가 나타날 때마다 현재 파란색 포인터로 바꾸고 파란색 포인터를 감소시킵니다.
• 흰색 요소가 발견되면 현재 포인터를 증가시킵니다.
• 현재 포인터가 파란색 포인터를 지나칠 때 중지하십시오.

이제 배열을 원하는대로 정렬해야합니다.

이것은 Dutch National Flag Problem입니다.

Answer 4

이것은 실제로 정렬 문제가 아닙니다. 그것은 그룹화 문제입니다.

빨간색, 흰색 및 파란색 요소의 수를 세어 목록을 반복합니다. 이제 당신은 X가 빨간색 솔루션의 정확한 구조, 예컨대 :

XXXXYYYYZZZZZZZZZ

을 알고, Y는 흰색이며, Z는 파란색입니다.

지금 세 포인터를 생성 : Y의 시작 X, 하나의 처음의 위치에서, 다른 하나를 Z의 시작 부분 A.에서

어드밴스 각 포인터는 첫번째 요소가 될 때까지 그것의 세트에서 틀리다. 예를 들어,이는 경우 :

XYXXYYXYZZZZZZZZZ

I

그 요소는 장소의 부족 때문에 우리는 두 번째 위치 (인덱스 1)로 I의 X 포인터를 전진 것이다.

각 포인터에 대해이 작업을 수행하면 세 포인터 각각이 잘못된 위치의 요소를 가리키고 있음을 알 수 있습니다. 그런 다음 목록을 반복합니다. 요소를 찾지 못하면 해당 포인터로 바꿉니다. 예를 들어 Y에서 X를 찾은 경우 Y 포인터로 바꾼 다음 포인터가 Y 방향으로 증가하여 포인터가 잘못된 위치를 가리킬 때까지 다시.

배열을 정렬 할 때까지 계속하십시오.

구조를 얻기 위해 목록을 한 번 반복 (n ops) 한 다음 최대로 각 포인터를 한 번씩 (4 포인터 → 4n) 한 번 반복하므로 총 최대 런타임은 5n이됩니다 (n).

Answer 5

나는 Skiena 책을 통해이 문제를 보았습니다.

내가 O와 용액 (2N) 얻었다 :

가정하자 A = [B, R, W, R, W를 B]

1. 먼저 배열 및 파티션 회동 B 통과 , 그래서 R 또는 W 인 모든 값이 배열의 앞쪽으로 밀려납니다.

이제 A가됩니다.

2. 다시 A를 통과하여 피봇 팅합니다. W에서 모든 값이 배열 앞쪽으로 푸시됩니다. 우리는 B가 이미 자리에 있음을 무시할 수 있습니다.

결과 : 'R', 'R', 'W', 'W', 'B', 'B'] => O (2N)

이 선형 솔루션이다.

올바른 방법입니까?

Answer 6

나는 Skiena 책을 읽고이 문제를 보았습니다. 그리고 여기 내 해결책입니다.

#include <stdio.h> 

//swap the ith element of A with the jth element. 
void swap(char arr[], int i, int j) { 
    char temp; 
    temp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = temp; 
    return; 
} 

int partition_color(char arr[], int low, int high, char color) 
{ 
    int i;   // counter 
    char p;   // pivot element 
    int firsthing; // divider position for pivot 

    p = color;   // choose the pivot element 
    firsthing = high; // divider position for pivot element 

    for (i = low; i < firsthing; i++) { 
     if (arr[i] == color) { 
      swap(arr, i, firsthing); 
      firsthing--; 
     } 
    } 

    return(firsthing); 
} 

void red_white_blue_sorting(char arr[], int n) { 
    int pos; 
    pos = partition_color(arr, 0, n, 'b'); 
    partition_color(arr, 0, pos, 'w'); 
    return; 
} 

int main() { 

    char arr[] = {'r', 'b', 'r', 'w', 'b', 'w', 'b', 'r', 'r'}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    red_white_blue_sorting(arr, n); 
    for (int i = 0; i < n; i++) 
     printf("%c ", arr[i]); 

    printf("\n"); 
    return(0); 
}