Hi all,
I wrote a pseudo code for a blocked/unrolled single linked list which does
global insertion sort(decreasing order) during insertion of elements in the
list.
Can someone look at pseudocode and let me know if it works correctly? I
think it does! Or do you see any corner cases which might create problems?
I think there might be also be some redundant logic...but I am not able to
figure out? I basically want to make it correct and more legible with
minimum amount of code.
There is also another issue of avoiding wastage due to partially filled
nodes which requires redistributing data between nodes. I am thinking about
some heuristic for this.
*BTW, first here are some test cases and expected results (Note: the sort
order in these test cases is in increasing order, but I wrote the algorithm
for decreasing order)*
eg1: insert 14 in (1,7)->(8,11)->(13,15)->NULL
result: (1,7)->(8,11)->(13,14)->(15,x)->NULL
eg2: insert 14 in (1,7)->(8,11)->(13,15)->(19,x)->NULL
result: (1,7)->(8,11)->(13,14)->(15,19)->NULL
eg3: (1,2)->(4,5)->NULL and 3 need to be inserted
result: (1,2)->(3,x)->(4,5)->NULL (NO redistribution)
eg4: insert 3 in (1,2)->(4,x)->NULL
result: (1,2)->(3,4)
eg5: (0,7,11,20,40)->(42,71,90,93,100)->NULL and 39 needs to be
inserted *[Assuming
ARRAY_SZ = 5]*
result: (0,7,11,20,39)->(40,x,x,x,x)->(42,71,90,93,100)->NULL (NO ReDIST)
(lot of space wasted in new Node N as chances of filling it are low and so
redistribution is required)
*And here is the pseudocode for the algorithm*
*------Data structure----------*
#define ARRAY_SZ 2
typedef struct node
{
struct node* next;
int Array[ARRAY_SZ];
int last_elem;
}NODE, *NODE_PTR;
*// isNotFull(node) function returns false when node=null or node.Array is
full. true otherwise*
*// Function that inserts element in a blocked linked list and maintains a
global decreasing sort order*
*
*
*Function insert(int elem, NODE_PTR* list): NODE_PTR*
*begin*
NODE_PTR currentNode = *list, startNode = NULL, oldNode = NULL
if(!currentNode)
{
create newNode
newNode.next = null
newNode.last_index=0
newNode.Array[newNode.last_index] = elem
return newNode
}
startNode = currentNode
while(currentNode)
{
if (isNotfull(currentNode))
{
// we can certainly insert elem in this non-full currentNode if either
next node is null(i.e. currentNode is last node in the list)
// or elem > currentNode.next.Array[0]
if(null == currentNode.next or elem > currentNode.next.Array[0])
{
currentNode.last_index++
insertionsort(elem, currentNode.Array)
return startNode
}
else
{
// even though currentNode is non-full we cannot insert in it, so we
move to next node
// TODO: redistribution
oldNode = currentNode
currentNode = currentNode.next
}
}
else
{
// currentNode is full
// case : elem should be inserted before currentNode
if(elem > currentNode.Array[0])
{
if(!oldNode)
{
// currentNode is the first node of list, so insert a newNode before this
and insert elem in this newNode
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = currentNode
return newNode
}
else
{
// currentNode is not the first node of the list because a previous node
i.e. oldNode exists
if(isNotfull(oldNode))
{
insertionsort(elem,oldNode)
return startNode
}
else
{
// previous node i.e. oldNode is full, so a newNode must be inserted
between currentNode and oldNode. insert elem in this newNode
create newNode
newNode.Array[newNode.last_index] = elem
oldNode.next = newNode
newNode.next = currentNode
return startNode
}
}
}
// case: elem should be inserted after currentNode. if next node is
null, create new node and insert elem in this new node. else,goto next
node.
else if (elem < currentNode.Array[currentNode.last_index])
{
if(null == currentNode.next)
{
// currentNode is last node of the list and is full
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = null
currentNode.next = newNode
return startNode
}
else
{
// nextNode is not null
if(elem < currentNode.next.Array[0] or isNotfull(currentNode.next))
{
// element cannot be in-between currentNode and nextNode. it must be
inserted in nextNode or ahead
oldNode = currentNode
currentNode = currentNode.next
}
else
{
// => elem > currentNode.next.Array[0] and nextNode is full
// elem must be inserted between currentNode and nextNode
// TODO: redistribution
create newNode
newNode.Array[newNode.last_index] = elem
newNode.next = currentNode.next
currentNode.next = newNode
return startNode
}
}
}
}
// case: elem needs to be inserted inside full currentNode
else
{
if(isNotfull(currentNode.next))
{
// there is some space in nextNode
insertionsort(currentNode.Array[last_index], currentNode.next)
insertionsort(elem, currentNode)
return startNode;
}
else
{
// nextNode doesnt exist i.e. null or nextNode must be full
// so a newNode must be inserted between currentNode and nextNode(or null)
create newNode
newNode.next = currentNode.next
newNode.Array[newNode.last_index] =
currentNode.Array[currentNode.last_index]
insertionsort(elem, currentNode)
currentNode.next = newNode
return startNode
}
}
}
}
}
*END Function*
*You can look at below email for more explanation of unrolled linked list.*
*
*
*
*
*Thanks *
*V.*
*
*
*
*
On Thu, Jul 28, 2011 at 6:43 PM, Varun Nagpal <varun.nagp...@gmail.com>wrote:
> Thanks a lot for your inputs Sunny. Your solution seems correct to me. Is
> this the only method ? Can you think of any other methods which could be
> more efficient. I heard merge sort or quick sort are also used for linked
> lists. Do you see their applicability in this case?
>
> What about duplicate avoidance ? Do I perform binary search on each node
> during the list construction to check for duplicates? Or you can think of a
> more efficient way?
>
> Thanks a lot
>
> Varun
>
>
>
>
> On Thu, Jul 28, 2011 at 11:02 AM, sunny agrawal
> <sunny816.i...@gmail.com>wrote:
>
>> Nice Problem :)
>>
>> i think taking care of duplicates is very simple.......but main point is
>> sorted insertion
>> that has to very carefully done
>> there are many cases that need to be taken care of
>> 1. if the value to be inserted is between two nodes and both nodes are
>> full....then a new node will be inserted in the link list and value to be
>> inserted will be the first element in the new node....
>> case: (1,2)->(4,5) and 3 need to be inserted
>> after insertion list will be
>> (1,2)->(3,x)->(4,5)->NULL
>>
>> 2. else the value that need to be inserted will be inside some node.......
>> if there is empty space in the node....simply insert using insertion sort
>> (1,2)->(4,x) and 3 is to be inserted, insertion sort in node 2 will
>> suffice
>> (1,2)->(3,4)->NULL
>> 3. but if the node in which the value need to inserted is full then last
>> number from that node will be shifted to a new node and then insert the
>> value in the node.
>> if array_sz is large the one instead of shifting the last element u can
>> split into two halves and put first half in first and second in 2nd
>> (1,2)->(3,5) 4 to be inserted
>> (1,2)->(1,4) ->(5,x) ->NULL
>> i think considering these 3 cases would suffice.......although first case
>> can be merged with 3rd if programmed carefully
>>
>>
>>
>> On Thu, Jul 28, 2011 at 3:35 AM, banu <varun.nagp...@gmail.com> wrote:
>>
>>> Anyone ?
>>>
>>> On Jul 26, 10:27 pm, banu <varun.nagp...@gmail.com> wrote:
>>> > Hi,
>>> > Basically I am trying to create a blocked linked list(unrolled linked
>>> > list) with following properties
>>> > - Configurable number of elements in each node
>>> > - No duplicate elements in the unrolled linked list
>>> > - Linked list is sorted either during insertion or after creating the
>>> > linked list
>>> > - In place
>>> >
>>> > Assuming I need to create a sorted unrolled linked list with no
>>> > duplicate elements with block size say 2
>>> >
>>> > Example: 10,2,4,2,5,7,9.11,11,5
>>> >
>>> > Final blocked linked list: (2,4)->(5,7)->(9,10)->(11,x) or in reverse
>>> > order
>>> >
>>> > Note: x means unutilized location in the array wihtin the node. In
>>> > case there are not enough elements to insert in a node, some memory
>>> > allocated for a node is unutilized
>>> >
>>> > // Following is node structure
>>> > #define ARRAY_SZ 2
>>> > typedef struct node
>>> > {
>>> > struct node* next;
>>> > long long int elements[ARRAY_SZ];
>>> > long long int elemIndex;
>>> >
>>> > }NODE, *NODE_PTR;
>>> >
>>> > Can you suggest me a way to do this correctly and efficiently? It
>>> > could be an pseudo text or C-code.
>>> >
>>> > Thanks
>>> > Varun
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
