Algorithm to add an element into sorted matrix of linked list

[srivardhanms]

Hi,

Can anyone give me an efficient algorithm for adding an element into a sorted matrix of linked list such that the size of the columns remains constant.

Thank-you,
Sri

[nitin1]

please elborate your problem so that I can help you more. thanks.

[rubberman]

And when asking us to help you with your homework, please post some code that you have written to solve this problem. Part of your education in computer science is to work up algorithms to solve these sort of problems. FWIW, the code can be pseudo code if you aren't ready to commit it to compilable/executable code as yet.

[srivardhanms]

Actually, Was looking for a psudo code.
The Problem is:
There is a Sorted Matrix. I need to add numbers to it dynamically so that the matrix remains sorted. I cannot change the number of columns. The Size of the column doesn't matter. Need an algorithm for adding numbers.

I tried to arrive, but what ever I try, the algorithm is creating holes in the matrix. So not able to proceed.

Once I get the algorithm, I can write the code. So looking for the algorithm.

Thank-you,
Sri

[Nutster]

What is the construction of this sorted matrix? I am assuming that it is a 2-dimentional set of linked lists, by the way you worded your question. The first linked list runs vertically. Each node of that linked list starts another linked list of the actual values. The matrix is sorted by the first value of each linked list. If any of this is different, then my solution would be different.

The algorithm that I would start with (it may need changes or tweeks as the code is written) would look down the main linked list, checking if the sorted key in the existing data is still greater than the element to be inserted. If it is less, or you reach the end of the linked-list, insert the given record.

[rubberman]

This is a variety of an insertion sort - inserting an element in the proper location of a sorted list so that the list / array remains sorted. I developed code for this 20 years ago (in C/C++). I used a modified combination of bsearch and qsort. It would search for the insertion index of the array, push the following elements down one position, and then set the element in the index provided. Doing this efficiently means that you want to intellegently resize the array so that you aren't doing reallocs for each insert, especially if you are dealing with 10's of thousands (or 100's of thousands) of records, which we had to deal with. I used a binary reallocation scheme, so that every time I had to reallocate the array, I would double the number of elements.

I'd provide sample code, but it belongs now to Applied Materials (the 800lb gorilla of semiconductor manufacturing equipment and software).

In any case, the algorithm goes like this:

1. Use a binary search of the array for the location to place the new element.
2. If necessary, reallocate the array to hold the new element.
3. Move the rest of the data down one element (memmove() works well for that).
4. Set the array location found to the new element.
5. You are done. :-)

FWIW, you only need 32 comparisons to find the location in an array of 4 billion elements.

[Nutster]

Binary search is very efficent, if done properly, for an array, but is not practical for a linked list, unless it is specifically designed for that, in which case it is called a binary tree.

[srivardhanms]

Actually, I was looking for the algorithm to insert in a sorted matrix. The following is the algorithm which I developed:

Check whether the element already exits.
if (exits)
    return;

Traverse vertically down until
    (Next value is greater than inserting value 
        OR 
    End of the rows.)

Traverse Horizontally right until
    (Next value is greater than inserting value 
        OR
    End of the columns)

if (Current slot is free)
    insert the number there.
else
    Insert a row below and insert the number just below the current slot.

I used a matrix which has link for its up, down, right and left element for the simplicity.