@Ankur: The least significant digit of a[i], base n, is a[i]%n. The
middle digit is (a[i]/n)%n, and the most signficant digit is a[i]/
(n*n). So the code looks something like
int b[n], c[n], i, j;
for( i = 0 ; i n ; ++i ) // sort by least significant digit
c[i] = 0;
for( i = 0 ; i n ; ++i )
@Dave
Dude can u provide a sample code...What do u mean by radix n ..also radix
sort requires some other sorting algo to sort digits
Regards
Ankur
On Sun, Aug 14, 2011 at 1:33 PM, Dave dave_and_da...@juno.com wrote:
@Ankur: Use a radix sort with radix n. It will take 3 passes to sort
the 3
lets assume numbers are in range 0 - 4 ,and array is aarr . then range
would be 0- 4^3 .. (0 - 64)..
now allocate an arraay .. int *x = calloc(n^3,sizeof(int)) // can use even
bits aalso .. but for simplicity of algo , using array
for(int i=0;i4;i++)
{
x[arr[i]] = 1;
}
for(int i=0;i64;i++)
{
@Ankur: Use a radix sort with radix n. It will take 3 passes to sort
the 3 base-n digits, each of O(n), so the overall order will be O(n).
On Aug 14, 10:08 am, Ankur Garg ankurga...@gmail.com wrote:
This is one question from Coreman
3rd Edition -
8-3-4 -- Sort n integers in the range 0 to
@Gopi: Explain how a counting sort can be done without zeroing out an
array of size n^3, and then scanning it, or explain how to do these
operations in O(n).
Dave
On Aug 14, 10:52 am, *$* gopi.komand...@gmail.com wrote:
if extra space is allowed .. can use counting sort
On Sun, Aug 14,
Yes..i agree with Dave..Here is what i think.
As you have integers upto n^3 in your input, it would need [3*lg(n) + 1]
bits to represent each integer.
So take each group of r = ceil(lg(n)) bits at a time.
So this becomes number of bits needed to represent single digit.
Each digit thus can take 2^r
I guess it is binary search tree. Try this and you will get what you
want.
On Sep 26, 5:12 am, mukesh agrawal [EMAIL PROTECTED] wrote:
What is binary index tree ? I googled it finding irrelevent information ...
help needed ..
On 9/25/07, Mohammad Naser Zandy [EMAIL PROTECTED] wrote:
I
What is binary index tree ? I googled it finding irrelevent information ...
help needed ..
On 9/25/07, Mohammad Naser Zandy [EMAIL PROTECTED] wrote:
I am agree with Sticker,
I comes to write exactly what Sticker wrote. ;)
It's O(N^2 / 2) that is 1+2+3+4+5+...+N.
On 9/25/07, Sticker [EMAIL
I am agree with Sticker,
I comes to write exactly what Sticker wrote. ;)
It's O(N^2 / 2) that is 1+2+3+4+5+...+N.
On 9/25/07, Sticker [EMAIL PROTECTED] wrote:
I saw your ideas. Some of them are correct some are not. Here is what
I am thinking.
From the question we know that 1 ≤ M ≤ 100
I already know how to solve it.
Binary Index Tree is good approach to solve this problem. Thanks very
body involved in this discussion!
On Sep 22, 6:31 am, KK [EMAIL PROTECTED] wrote:
On Sep 5, 11:07 am, jliang [EMAIL PROTECTED] wrote:
how about a doubled linked list where you can remove
On Sep 5, 11:07 am, jliang [EMAIL PROTECTED] wrote:
how about a doubled linked list where you can remove item at any
index. the removing is O(1). you can also keep track of the current
removing from a doubled linked list is O(1)? How?
size S so if you are borrowing book at index greater
I can think of an o(n lg n) implementation that uses linked lists.
Maintain LL of original book array: 26- 1- 42- 15 -3 this shrinks
as books are removed.
maintan LL of borrowed books: 3-4 ..
Original LL now becomes 26-1-15
Sort the borrowed LL --(borrwored order may be 3-4-1 == 1-3-4)
using
I know the naive method. It's very straight. Just maintain an index
array which records the
index of the books. whenever one book is removed then update all
elements in the index array after its index.
It runs O (M N). I'd like to know is there any efficent data structure
to speedup it?
how about a doubled linked list where you can remove item at any
index. the removing is O(1). you can also keep track of the current
size S so if you are borrowing book at index greater than S/2, you
traverse the list from the end, if index S/2, you traverse from the
beginning.
every time a
Of course, the index numbers lower than the book being checked out,
don't need to be changed, just the higher numbers.
I like using an array of structs with structure members which can
group all the relevant data together that I want for that book, or
student, etc.
So Books[] might have: title,
15 matches
Mail list logo
