Describe a function for performing a card shuffle of an array of 2n elements, by

Question

Describe a function for performing a card shuffle of an array of 2n elements, by converting it into two lists. A card shuffle is a permutation where a list L is cut into two lists,L1 and L2, where L1 is the first half of L and L2 is the second half of L, and then these two lists are merged into one by taking the first element in L1, then the first element in L2, followed by the second element in L1, the second element in L2, and so on. Write the function in pseudocode. State correctness and complexity of your algorithm with justification.

Explanation / Answer

Pesdo code for Merging of two sub lists into single ..
See the below code will help you understand the concept of merging element from lista and listb into result list

This below algorthim will work based on the comprision of lista element with listb elements in asedning oredr then combine them in result and will return the result.

function merge (lista, listb) {

toReturn = your 'third list'

while lista and listb both still have elements {
if lista's smallest element < listb's smallest element {
add lista's smallest element to toReturn
remove lista's smallest element
} else {
add listb's smallest element to toReturn
remove listb's smallest element
}
}

// if lista has no elements, this loop is skipped
while lista still has elements {
add them to toReturn
}

// if listb has no elements, this loop is skipped
while listb still has elements {
add them to toReturn
}

return toReturn

}

Time Complexity is : O(nlogk)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.