3

Estava tentando escrever o merge sort em python por minha conta, mas retornou uma lista nada a ver com vários números repetidos. Ao verificar online o código solução, fiquei com dúvida sobre como criar e passar valores de uma lista para a outra, segue como é escrito no código correto:

# a variável m desse código representa meio da lista
# create two empty arrays L[0..nL] and R[0..nR]
L = [0] * (nL + 1)
R = [0] * (nR + 1)

# copy left half of arr in L[0..nL-1]
for i in range(0, nL):
L[i] = arr[l + i]

# copy right half of arr in R[0..nR-1]
for j in range(0, nR):
R[j] = arr[m + 1 + j]

Em seguida como eu escrevi:

# criei duas listas vazias
    R = []
    L = []
# passei metade da lista original para L
    for i in range(0, nL):
        tmp = a[i]
        L.append(tmp)
# a outra metade para R
    for j in range(nR, end):
        tmp = a[j]
        R.append(tmp)

considerando que nL e nR dividem a lista em meio a meio, a maneira em que eu escrevi resulta em uma lista diferente da do código correto?

p.s.:link pro código correto

1 Resposta 1

1

Dei uma olhada no link do código que você passou, sua forma de escrever também está correta mas é preciso levar em consideração alguns pontos específicos, por exemplo:

# a variável m desse código representa meio da lista
# create two empty arrays L[0..nL] and R[0..nR]
L = [0] * (nL + 1)
R = [0] * (nR + 1)

Nessa parte, percebe-se que foi criado uma lista L e R com um índice a mais, diferente do que vc fez, mas isso tem uma explicação.

Durante o código, percebe-se que foi usado o "math.inf" como um valor sentinela, ou seja:

# put infinity as sentinel value at the end of Both L and R
    L[nL] = math.inf
    R[nR] = math.inf

Para facilitar no momento de análise e ordenamento, ele determinou um valor "infinito" no final de cada uma dessas listas, dessa forma:

# iterate over L and R
    # and copy the smallest of L[i] and R[j] to arr[k]
    i = 0
    j = 0
    for k in range(l, r + 1):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1

Quando for feita a iteração, ele não irá correr o risco de sofrer uma "index out of range exception", pois, sempre que ele chegar ao final da lista, esse valor (infinito) nunca vai ser menor, dessa forma, o indice "i", ou "j" pra esse caso, não irá ultrapassar o limite.

Ou seja, se você quiser resolver da mesma forma, é preciso que você use a mesma estratégia, a não ser que prefira fazer de outra forma, exemplo:

i=j=k=0
while i<len(L) and j<len(R):
    if L[i]<R[j]:
        arr[k]=L[i]
        i+=1
    elif R[j]<L[i]:
        arr[k]=R[j]
        j+=1
    k+=1
#Essa parte adiciona os elementos que sobraram
while j<len(R):
    arr[k]=R[j]
    j+=1
    k+=1
while i<len(L):
    arr[k] = L[i]
    i+=1
    k+=1

Uma boa explicação desse método pode ser encontrada aqui: https://www.geeksforgeeks.org/merge-sort/

Observação: Na sua iteração, você não precisa criar a variável "tmp", pois como a lista "arr" é uma lista de inteiros, os inteiros sao imutáveis, logo, vc pode simplismente: L.append(a[1])

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .