Как слить отсортированную последовательность с разным размером?

Question

Я ищу алгоритм для объединения нескольких отсортированных последовательностей, скажем, X отсортированных последовательностей, в одну упорядоченную последовательность в c, можете ли вы привести несколько примеров?

Обратите внимание, что каждая последовательность имеет разный размер.

Я думал об этом, но последовательности могут иметь перекрывающиеся интервалы. так что это не сработает.

x=s1[first] 
y=s2[last] 
if(x<y) then put s1 after s2 in the output. 
... 

примечание: Я не хочу, чтобы использовать любую библиотеку

Answer 1

можно объединить входные последовательности, как в N-полосная merge sort делает.

В принципе, вы изучаете голову каждой из упорядоченных входных последовательностей и добавляете минимальную голову в новую упорядоченную последовательность (и обновляете главу последовательности, из которой вы потребляете). Вы делаете это до тех пор, пока все ваши входные последовательности не будут пустыми.

Если у вас есть значительное количество входных последовательностей для слияния, вы можете захотеть сохранить минимальную кучу головок ваших входных последовательностей, а не выполнять линейное сканирование минимальной головки каждый раз.

#include <stddef.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <assert.h> 

typedef struct 
{ 
    size_t size; 
    int *seq; 

} Sequence; 

Sequence *mergeSortedSequences(const Sequence *seqs[], size_t num_seqs) 
{ 
    Sequence *ret = malloc(sizeof(Sequence)); 
    size_t indexes[num_seqs]; /* NOTE: not valid C89; in C89 need to malloc instead or have seqs be non-const and trash the Sequences themselves */ 
    size_t tot_size; 
    size_t i; 

    if (NULL == ret) 
    goto FAIL; 

    ret->size = 0; 

    /* calculate total size of merged Sequence, init indexes and cull any empty sequences from seqs */ 

    for (i = 0, tot_size = 0; i < num_seqs;) 
    { 
    if (0 != seqs[i]->size) 
    { 
     tot_size += seqs[i]->size; 
     indexes[i] = 0; 
     ++i; 
    } 
    else 
    { 
     seqs[i] = seqs[--num_seqs]; /* cull empty seq from seqs */ 
     printf("Swapping original seq %lu into position %lu\n", num_seqs, i); 
    } 
    } 

    printf("Return sequence size is %lu; number of non-empty sequences: %lu\n", tot_size, num_seqs); 

    ret->seq = calloc(tot_size + 1, sizeof(int)); /* NOTE: +1 so we don't ever calloc(0) */ 

    if (NULL == ret->seq) 
    goto FAIL_RET; 

    /* loop while non-empty sequences left */ 

    while (num_seqs) 
    { 
    /* find minimum of remaining seqs */ 

    int min  = seqs[0]->seq[indexes[0]]; 
    size_t min_seq = 0; 

    for (i = 1; i < num_seqs; ++i) 
    { 
     if (seqs[i]->seq[indexes[i]] < min) 
     { 
     min  = seqs[i]->seq[indexes[i]]; 
     min_seq = i; 
     } 
    } 

    /* update ret */ 

    ret->seq[ret->size++] = min; 

    printf("minimum value was from head of seq %lu; ret[%lu] = %d\n", min_seq, ret->size, min); 

    /* update indexes, min_seq and seqs */ 

    ++indexes[min_seq]; /* "consume" the head of min_seq */ 

    if (indexes[min_seq] == seqs[min_seq]->size) /* we've exhausted min_seq */ 
    { 
     seqs[min_seq] = seqs[--num_seqs];  /* cull empty sequence */ 
     indexes[min_seq] = indexes[num_seqs]; 
     printf("Swapping seq %lu into position %lu (2)\n", num_seqs, min_seq); 
    } 
    } 

    printf("Success ret->size = %lu\n", ret->size); 

    assert(NULL != ret && ret->size == tot_size); 
    goto END; 

    /* error handling and return */ 

FAIL_RET: 
    free(ret); 
    ret = NULL; 

FAIL: 
    assert(NULL == ret); 

END: 
    return ret; 
} 

int main(int argc, char **argv) 
{ 
    int  arr1[] = { -44, 0, 22, 49, 58, 101 }; 
    int  arr3[] = { -101, 14, 22, 31, 151 }; 
    int  arr4[] = { -1, 0, 1, 50, 200 }; 
    Sequence seq0 = { 0, NULL }; 
    Sequence seq1 = { sizeof(arr1)/sizeof(arr1[0]) }; 
    Sequence seq2 = { 0, NULL }; 
    Sequence seq3 = { sizeof(arr3)/sizeof(arr3[0]) }; 
    Sequence seq4 = { sizeof(arr4)/sizeof(arr4[0]) }; 
    Sequence seq5 = { 0, NULL }; 
    Sequence *seqs[6]; 
    Sequence *ret; 
    size_t i; 

    seq1.seq = arr1; 
    seq3.seq = arr3; 
    seq4.seq = arr4; 

    seqs[0] = &seq0; 
    seqs[1] = &seq1; 
    seqs[2] = &seq2; 
    seqs[3] = &seq3; 
    seqs[4] = &seq4; 
    seqs[5] = &seq5; 

    ret = mergeSortedSequences((const Sequence**) seqs, sizeof(seqs)/sizeof(seqs[0])); 

    if (NULL == ret) 
    { 
    perror("Allocation failure!"); 
    abort(); 
    } 

    printf("Merged sequence contains %lu elements:\n", ret->size); 

    for (i = 0; i < ret->size; ++i) 
    printf("\t%d\n", ret->seq[i]); 

    return 0; 
}