Am I interpreting this pseudocode wrong?

I've got this pseudocode:

COMPARE-EXCHANGE(A,i,j)
    if A[i] > A[j]
        exchange A[i] with A[j]

INSERTION-SORT(A)
    for j = 2 to A.length
        for i = j-1 downto 1
            COMPARE-EXCHANGE(A,i,i+1)

I would interpret it as:

void insertSort( )
{
    int tmp;

    for( int j = 2 ; j < MAX ; ++j )
    {
        for( int i = j - 1 ; i > 0 ; --i )
        {
            if( unsortedArr[i] > unsortedArr[i + 1] )
            {
                tmp                 = unsortedArr[i];
                unsortedArr[i]      = unsortedArr[i + 1];
                unsortedArr[i + 1]  = tmp;
            }
        }
    }
}

However that would skip unsortedArr[0]. Which means it won't work.

Changing the 2nd for to:

for( int i = j - 1 ; i >= 0 ; --i )

Will make it run as intended. Is there a mistake in the pseudocode or was my first try of interpreting it wrong?

Answers


However that would skip unsortedArr[0]. Which means it won't work.

It is nearly universal for pseudocode to number array elements from 1, not from zero, as in C/C++

Changing the 2nd for to:

for( int i = j - 1 ; i >= 0 ; --i )

Will make it run as intended.

That is not enough: you also need to start j at 1 rather than 2 in the outer loop.

Also note that the C++ standard library offers a std::swap function which takes care of exchanging the elements of the array for you:

if( unsortedArr[i] > unsortedArr[i + 1] )
{
    std::swap(unsortedArr[i], unsortedArr[i+1]);
}

I think your pseudo code is assuming that arrays start with index one [1] -- where in C & C++ they start at zero [0].


I'm guessing that the pseudocode is using 1-based indexing, rather than the 0-based indexing that C++ uses.


Need Your Help

Flex - change in Timezone only picked up on Minutes Change. Why?

actionscript-3 flex flex4

I have a timer running, that every second, checks the systems Date/Time, and updates

XSLT 1.0: Muenchian grouping does not work

xslt xslt-1.0 muenchian-grouping

I have the following simplified XML structure:

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.