XML CO527 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for bubble-sort

Question 31 (2011):

Submission reference: IN2140

Hi, here is my bubble sort algorithm:

public void sortlist (ReadReq thelist[])
{
    int i, j;
    ReadReg t;

    for (i = (readqueue_size - 1); i >= readqueue_tail; i--) {
        for (j = readqueue_tail + 1; j <= i; j++) {
            // compare and maybe swap thelist[j-1] with thelist[j]
        }
    }
}

I thinks it's broken in some way but I can't seem to figure out what's wrong.

Answer 31:

This looks like a wrap-around related problem: if "readqueue_tail" is not zero, this code will go wrong. See Question 28 (2011) for a description of why. Expressing the bubble sort's loops over the circular buffer (assuming readqueue_head and readqueue_tail are both changing) will not produce pretty looking code, though it should work. It would probably be simpler to ensure readqueue_tail is always zero (i.e. remove it), and swap with the request block at the other (head) end of the array — beware though, the request at the head end of the buffer is at index ((readqueue_head - 1) + readqueue.length) % readqueue.length, ugly because "%" doesn't generally behave nicely with negative numbers).

Keywords: assess4-1112 , bubble-sort