Scalanie przy użyciu jednej tablicy pomocniczej

Question

Witam forumowiczów. Mam do przerobienia algorytm sortowania przez scalanie z książki "Wprowadzenie do algorytmów" Cormena, a dokładniej algorytm samego scalania. Zadanie polega na tym, aby zamiast dwóch tablic pomocniczych użyć jednej.

SCAL(A, p, q, r)
    n=q-p+1
    m=r-q
    for i=1 to n
        do B[i]=A[p+i-1]
    B[n+1]=nieskonczonosc
    for j=1 to m
        do B[q+1+j]=A[q+j]
    B[r+2]=nieskonczonosc

 

Problem zachodzi w drugiej pętli. Dla podciągu o indeksach np. 2-12 następuje sytuacja, w której wartownik (nieskończoność) stoi na 7. miejscu, a rozpoczęcie przypisywania od B[q+1+j] pomija jedną komórkę tablicy. q = 7, j = 1 - q + 1 + j = 9. Dla innych podciągów ta pętla działa prawidłowo. Nie mam kompletnie pomysłu na ten problem, a nie chcę używać ifów dla różnych przypadków. Jak więc znaleźć uniwersalne rozwiązanie?

PS: Tablice muszą zaczynać się od indeksu 1, gdyż tak jest w oryginalnym algorytmie w książce.

Pozdrawiam.

Answer 1

A czy zadawalałoby cię, w tym scalaniu użyć sortowania przez wstawianie ? Wtedy mając te dwie tablice połączyłbyś je w jedną uporządkowaną.

Comments

Musi być koniecznie przez scalanie. To jest zadanie od wykładowcy. A tak poza tym, to nie wiem jaki tu jest stosunek do ludzi szukających pomocy w zadaniach - na niektórych forach można dostać niezłą "lekcje" za szukanie pomocy, także przepraszam z góry. :D

---

W sumie, to przecież, wystarczy jedna tablica lol. Jak masz w tym właściwym algorytmie Tablice B i C to B rób od 1 do n/2 a B od n/2 + 1 do n.

Answer 2

Nie rozumiem , chcesz scalić tablicę w tablicę ?

Comments

Chodzi mu o algorytm sortujący, tam on wykkożysutuej 2 tablice pomocnicze do posortowania, a tu on chce jedno.

---

To nie jest pełny algorytm scalania. Wstawiłem część, która sprawia problem, a jest niezależna od tej niewstawionej.

Answer 3

Chyba udało mi się wymyślić działający algorytm:

 

SCAL(A, p, q, r)
    n=q-p+1
    m=r-q
    for i=1 to n
        do B[i]=A[p+i-1]
    B[n+1]=nieskonczonosc
    for j=1 to m
        do B[n+1+j]=A[q+j]
    B[n+2+j]=nieskonczonosc
    i=1
    j=n+2
    for k=p to r
       do if B[i] <= B[j]
              then A[k]=B[i]
             i=i+1
              else A[k]=B[j]
                   j=j+1

 

Jak oceniacie?