On Mon, Dec 22, 2008 at 12:29 PM, wrote:
> On Dec 15, 10:00 pm, "cmdrrickhun...@yaho.com"
> wrote:
>> It can be proven that you cannot sort an arbitrarily large set of
>> numbers, given no extra information, faster than O(n log n).
>
> Cormen Leiserson and Rivest, "Algorithms", have a short clea
On Dec 15, 10:00 pm, "cmdrrickhun...@yaho.com"
wrote:
> It can be proven that you cannot sort an arbitrarily large set of
> numbers, given no extra information, faster than O(n log n).
Cormen Leiserson and Rivest, "Algorithms", have a short clear chapter
on
"Sorting in linear time":
" ... cou
Just because its such an interesting problem, I'll take a stab at it.
It can be proven that you cannot sort an arbitrarily large set of
numbers, given no extra information, faster than O(n log n). It is
provable using information theory. However, if your teacher is giving
you evil problems, ther
Dan Upton wrote:
And if n is small and sparse (ie, k > n) , O(k*n) for radix sort could
be worse than O(n^2). You could also ask why people make such a big
deal about quicksort over mergesort, since mergesort has a guaranteed
O(n log n) time whereas quicksort can be O(n^2) on pathological cases
On Mon, Dec 15, 2008 at 11:05 AM, wrote:
>> Non-comparison sorts are a useful technique, but it's changing the
>> problem, and they are only useful in very limited circumstances. There's
>> a good reason that most sort routines are based on O(n*log n) comparison
>> sorts instead of O(n) bucket so
On Dec 15, 11:05 am, prueba...@latinmail.com wrote:
> > Non-comparison sorts are a useful technique, but it's changing the
> > problem, and they are only useful in very limited circumstances. There's
> > a good reason that most sort routines are based on O(n*log n) comparison
> > sorts instead of O
> Non-comparison sorts are a useful technique, but it's changing the
> problem, and they are only useful in very limited circumstances. There's
> a good reason that most sort routines are based on O(n*log n) comparison
> sorts instead of O(n) bucket sorts or radix sorts.
>
This is an assumption tha
On Sun, 14 Dec 2008 21:12:13 -0800, Aaron Brady wrote:
> On Dec 14, 8:18 pm, Roy Smith wrote:
>> Steven D'Aprano wrote:
>> > All the positive thinking in the world won't help you:
>>
>> > * make a four-sided triangle;
>>
>> > * split a magnet into two individual poles;
>>
>> These two are fundam
On Mon, 15 Dec 2008 01:48:43 +, Steven D'Aprano wrote:
> Some things really don't have a solution, no matter how much power of
> positive thinking you apply to it.
Some may, only not with the current understanding of the universe. Well,
I agree that there are a few things that is straight ou
On Sun, 14 Dec 2008 21:18:03 -0500, Roy Smith wrote:
> Steven D'Aprano wrote:
>
>> All the positive thinking in the world won't help you:
>>
>> * make a four-sided triangle;
>>
>> * split a magnet into two individual poles;
>
> These two are fundamentally different problems.
>
> The first is
On Mon, Dec 15, 2008 at 2:12 PM, Aaron Brady wrote:
>
> I agree. Most of his examples were tautologies. The magnet one was
> the exception.
A proof is nothing more than a tautology :) The fact that pi is not
rational is not trivial (but certainly has been proved for some time
now).
cheers,
D
On Dec 14, 8:18 pm, Roy Smith wrote:
> Steven D'Aprano wrote:
> > All the positive thinking in the world won't help you:
>
> > * make a four-sided triangle;
>
> > * split a magnet into two individual poles;
>
> These two are fundamentally different problems.
>
> The first is impossible by definit
Steven D'Aprano wrote:
> All the positive thinking in the world won't help you:
>
> * make a four-sided triangle;
>
> * split a magnet into two individual poles;
These two are fundamentally different problems.
The first is impossible by definition. The definition of triangle is, "a
three-si
On Sun, 14 Dec 2008 21:42:33 +, Lie Ryan wrote:
> I'm sure someday, there will be a student who comes to class late and
> sees this on the board: "Design a comparison sorting algorithm that has
> better than O(n * log n) lower bound complexity." The unsuspecting
> student copied it, thinking i
On Dec 14, 6:04 pm, greg wrote:
> Lie Ryan wrote:
> > "You know what you just did? You've
> > just found a problem that was supposed to be an example of unsolvable
> > problem."
>
> > It has happened before, why not again?
>
> There's a big difference between an unsolvable problem and an
> unsolve
Lie Ryan wrote:
"You know what you just did? You've
just found a problem that was supposed to be an example of unsolvable
problem."
It has happened before, why not again?
There's a big difference between an unsolvable problem and an
unsolved problem. In the cases you're talking about, nobody
On Sat, 13 Dec 2008 19:17:41 +, Duncan Booth wrote:
> "Diez B. Roggisch" wrote:
>
>> David HláÄik schrieb:
>>> Hi guys,
>>>
>>> i am really sorry for making offtopic, hope you will not kill me, but
>>> this is for me life important problem which needs to be solved within
>>> next 12 hours
Thank you guys for help and support! My homework is done and waiting
for grading.
Here it comes - bucket sort with time complexity O(n) == linear complexity
#! /usr/bin/python
def sort(numbers):
"sort n positive integers in O(n) provided that they are all from
interval [1, n^2]"
Steven D'Aprano writes:
> On Sat, 13 Dec 2008 19:17:41 +, Duncan Booth wrote:
>
>> I think you must have fallen asleep during CS101. The lower bound for
>> sorting where you make a two way branch at each step is O(n * log_2 n),
>> but if you can choose between k possible orderings in a single
1. Comparison sorts have n*ln(n) complexity - does not do
2. Counting sort has the complexity O(d), where d is domain (in our
case n^2) - does not do.
3. Radix sorts have the complexity O(n*k), where k is number of bits
in integer. (32?) There are 2 variants:
a. most significant digit (MSD),
b. lea
On Sat, 13 Dec 2008 19:17:41 +, Duncan Booth wrote:
> I think you must have fallen asleep during CS101. The lower bound for
> sorting where you make a two way branch at each step is O(n * log_2 n),
> but if you can choose between k possible orderings in a single
> comparison you can get O(n *
"David Hláčik" writes:
> Hi guys,
>
> i am really sorry for making offtopic, hope you will not kill me, but
> this is for me life important problem which needs to be solved within
> next 12 hours..
>
> I have to create stable algorithm for sorting n numbers from interval
> [1,n^2] with time compl
Aaron Brady wrote:
>So, what's the group policy on helping with homework? rhetorical>
In my book anyone who is dumb enough to ask for homework help on a
newsgroup and doesn't acknowledge that when they hand in their answer
deserves whatever they get. Oh, and of course there are 2 deliberate
2008/12/13 Aaron Brady
> On Dec 13, 1:17 pm, Duncan Booth wrote:
> > "Diez B. Roggisch" wrote:
> >
> >
> >
> > > David Hláčik schrieb:
> > >> Hi guys,
> >
> > >> i am really sorry for making offtopic, hope you will not kill me, but
> > >> this is for me life important problem which needs to be
On Dec 13, 1:17 pm, Duncan Booth wrote:
> "Diez B. Roggisch" wrote:
>
>
>
> > David Hláčik schrieb:
> >> Hi guys,
>
> >> i am really sorry for making offtopic, hope you will not kill me, but
> >> this is for me life important problem which needs to be solved within
> >> next 12 hours..
>
> >> I h
Duncan Booth schrieb:
"Diez B. Roggisch" wrote:
David Hlá�ik schrieb:
Hi guys,
i am really sorry for making offtopic, hope you will not kill me, but
this is for me life important problem which needs to be solved within
next 12 hours..
I have to create stable algorithm for sorting n number
Diez B. Roggisch wrote:
David Hláčik schrieb:
Hi guys,
i am really sorry for making offtopic, hope you will not kill me, but
this is for me life important problem which needs to be solved within
next 12 hours..
I have to create stable algorithm for sorting n numbers from interval
[1,n^2] with
"Diez B. Roggisch" wrote:
> David HláÄik schrieb:
>> Hi guys,
>>
>> i am really sorry for making offtopic, hope you will not kill me, but
>> this is for me life important problem which needs to be solved within
>> next 12 hours..
>>
>> I have to create stable algorithm for sorting n numbers f
"David Hláčik" wrote:
> I have to create stable algorithm for sorting n numbers from interval
> [1,n^2] with time complexity O(n) .
Some kind of radix sort or counting sort. These algo. has O(n) complexity.
w.
--
http://mail.python.org/mailman/listinfo/python-list
On Sat, Dec 13, 2008 at 2:00 PM, David Hláčik wrote:
>> Unless I grossly miss out on something in computer science 101, the lower
>> bound for sorting is O(n * log_2 n). Which makes your task impossible,
>> unless there is something to be assumed about the distribution of numbers in
>> your sequen
> Unless I grossly miss out on something in computer science 101, the lower
> bound for sorting is O(n * log_2 n). Which makes your task impossible,
> unless there is something to be assumed about the distribution of numbers in
> your sequence.
There is n numbers from interval [1 , n^2]
I should d
David Hláčik schrieb:
Hi guys,
i am really sorry for making offtopic, hope you will not kill me, but
this is for me life important problem which needs to be solved within
next 12 hours..
I have to create stable algorithm for sorting n numbers from interval
[1,n^2] with time complexity O(n) .
C
Hi guys,
i am really sorry for making offtopic, hope you will not kill me, but
this is for me life important problem which needs to be solved within
next 12 hours..
I have to create stable algorithm for sorting n numbers from interval
[1,n^2] with time complexity O(n) .
Can someone please give m
33 matches
Mail list logo
