Skip to content

unique way of finding second largest element using Stepanov_BinaryCounter method.

Notifications You must be signed in to change notification settings

niksram/Stepanov-Binary-Counter-findSecondLargest

Repository files navigation

DATA STRUCTURES USED:-

Hanger:-
Its the data-type which contains the entire frame for storing the skewed adjacency-list.
It consists of an integer 'stretch' which stores the size of the list of 'deck's.
The pointer 'deck' consists of an array of decks which is of length ceil(log(n)), where n is the numer of elements fed in.

Deck:-
The pointer array of the adjacency list in the 'Hanger' frame is nothing but an array of 'Deck' type.
It has a pointer 'head' of type 'Node*' which shall point to the head node of the linked list stored at a particular 'level'
(level:- naming 'level' is used to indicate the index in the 'deck' array)

Node:-
The data-type Node is nothing but the fundamental element of a linked list.
It consists of an integer variable 'val' which stores the value in the node.
The 'Node*' pointer 'link' points to the next Node of the list and point to NULL if its the end element.

Functioning---
once an element is read, a 'node' is created for the respective element and fed into the 'Hanger' through the recursive function 'compete'.
the node shall occupy the deck at level 0 if its NULL or shall fight with the list there and proceed to the next level recursively.
In n=powers of 2, the resultant Hanger shall only contain a final linked list at the last_level= hanger->stretch-1 th deck.
else when n is not power of 2, the residual non-empty decks are cascaded onto each other.

KEY TAKEAWAY:-

The following simulation helps us to understand how a tournament is conducted and how the winners and losers are arranged accordingly.
The following implementation can be tweaked with the merge-function to simulate Merge-Sort.
the number of comparisons in the given alorithm is around n+log(n) which is less than 2*(n-1) in the Brute-Force method of finding second largest element. 

About

unique way of finding second largest element using Stepanov_BinaryCounter method.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published