flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Heap > O(n) sort

Author
Thread Post new topic Reply to topic
l4m2



Joined: 15 Jan 2015
Posts: 584
O(n) sort
Usually when we say complexity, we have some assumptions. Michael Brand's assumptions, however, have some bugs. This code can sort an array of non-negative integers(add -min if not sure) in O(n):

Code:
; Fasm G
; Init
x1 = 13
x2 = 7
x3 = 11
x4 = 3
n = 4
; Sort
; Assuming any two numbers differ. 
; If not sure, multiply them by n and plus its index
; Also assuming n is at least 2
a = 0
rept n i
  a = a + (1 shl (x##i * n))
end rept
rept n i
  rept 1 t:(a shr (x##i * n)) mod ((1 shl n) - 1)
    y##t = x##i
  end rept
end rept
; Output
rept n i
  rept 1 t:y##i
    display `t1310
  end rept
end rept


Now your task is to
1. sort an array of real in O(n).
Note: Real constants are unnecessary, but allowed as a step.

2. factorize a positive integer in o(lg^c n), where c is constant
real numbers are banned


Last edited by l4m2 on 29 Jul 2017, 15:34; edited 3 times in total
Post 28 Jul 2017, 13:24
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14929
Location: 6EQUJ5
What is the average run complexity? The worst case complexity?

Because I expect when you claim O(n) you are suggesting the best case, right? I don't think anyone has yet discovered a sorting algorithm in the O(n) complexity class yet, except in the best case where the list is already sorted. Quite a few algorithms can do O(n) in the best case, but they can't keep such a low complexity when sorting non-ordered lists.
Post 28 Jul 2017, 13:39
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584
I meant the worst case complexity.
In reality it is not O(n), but here we assumed any number, no matter how large, goes calculated in O(1), thus something weird happened.
Post 28 Jul 2017, 13:46
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14929
Location: 6EQUJ5
The code fails for this input set:

Code:
x1 = 1
x2 = 1
n = 2

Post 28 Jul 2017, 14:02
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584

Quote:

Code:
; Sort 
; Assuming any two numbers differ.  
; If not sure, multiply them by n and plus its index 


Post 28 Jul 2017, 14:04
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584
another prob comes
Post 29 Jul 2017, 15:35
View user's profile Send private message Reply with quote
Furs



Joined: 04 Mar 2016
Posts: 567
That's just a very inefficient way to do Radix Sort.
Post 29 Jul 2017, 17:16
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584

Furs wrote:
That's just a very inefficient way to do Radix Sort.

Why Radix, not Counting? It does the whole sort in one run
Post 30 Jul 2017, 13:39
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584
Answer to the 1st problem in Python 2:

Code:
import math

def sh(n,a):
  return ((1<<(a*n))-1)/((1<<a)-1)

def sortr(a):
  #;Assuming all values are in [0,1)
  n=len(a) #;length
  s=l=0 #;s means [0,1) is cutted into 2**s equal part, l is the list to store indices
  m=y=int(math.log(n,2)+1) #;every part costs y bits, but only the last m bits mean
  for i in range(1,n):
    r=int((1<<s)*a[i])
    t=(l>>(y*r))%(1<<m)
    if (int((1<<s)*a[t])==r) & (a[t]!=a[i]): #;Another value is in the same part
      d=int(math.floor(-math.log(abs(a[t]-a[i]),2))) #; New s that is enough. easily proved
      w=(y<<s)+y #; Old l's length plus y, so the next code won't overlap
      l=l*sh(1<<(d-s),w)*sh(1<<s,(w<<(d-s))-y)
      #; abcd -> Abcd0AbcdaBcd0aBcdabCd0abCdabcD0abcD if s=2 and d=3
      s=d
      y=w
      r=int((1<<s)*a[i]) #; The old r won't work, so recomputing is necessary
    l=l-(l>>(y*r))%(1<<y)*(1<<(y*r))+(i<<(y*r)) #; Set the value there to the new one
  #;sort ints, every number mult by 2**s
  x=[int(a[i]*(1<<s))*n+i for i in range(0,n)]
  b=sum([1<<(x[i]*nfor i in range(0,n)])
  y=range(0,n)
  for i in range(0,n):
    y[b%(1<<(x[i]*n))%((1<<n)-1)] = a[i] #; Count those who are smaller than the current item
  return y

sortr([.67.233.2328])



Last edited by l4m2 on 01 Aug 2017, 03:52; edited 2 times in total
Post 30 Jul 2017, 13:41
View user's profile Send private message Reply with quote
Furs



Joined: 04 Mar 2016
Posts: 567

l4m2 wrote:
Why Radix, not Counting? It does the whole sort in one run

To me it looked like counting based on a large array (well in your case, just stuffed into an integer, but that's just semantics...) which works in your specific case since the numbers are small, but otherwise is inefficient. I'm not very familiar with counting sort, but doesn't it have 3 steps? (iterating through the range)
Post 30 Jul 2017, 13:52
View user's profile Send private message Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 584

The Usual Complexity Assumptions
"The usual complexity assumptions" is a term refering to a set of conventions employed so often in complexity calculations that they are usually taken for granted.

For example, one often refers to Bubble sorting as an O(n2)-time operation, when, in fact, it is not. It merely requires O(n2) comparison operations. If we were to compare two integers, a and b using (for example) a Turing machine, we would, in the general case, need to go over all their bits in order to find a difference, so this operation may take as long as O(log(min(|a|,|b|))), rather than O(1).

Similarly, we casually refer to storing real numbers and performing operations on them, when, in fact, it is impossible to store a full representation of a general real number on any computer or any Turing machine.

"The usual complexity assumptions" therefore refers to the most commonly used (and least commonly explicitly specified) computational model. It defines "integers", "reals" and "arrays" as abstract data types, and also defines an execution model that uses them. This, in turn, means that certain operations are assumed to be atomic O(1)-time operations.

The following are the O(1) operations assumed:

Regarding integers

An integer can be stored in O(1) space.
The four basic arithmetic operations (addition, subtraction, multiplication and division) as well as modulo-taking are all O(1).
Comparisons (less than, greater than, equal to) are all O(1).
Shift-left and shift-right by n bits, for any integer n, are O(1). (The result of this is the same as multiplication/division by 2n.)
Conversion to real numbers is O(1).

Note that bitwise operations other than shifts are not considered O(1), unless explicitly stated.
Regarding real numbers

A real number can be stored in O(1) space.
The four basic arithmetic operations (addition, subtraction, multiplication and division) are all O(1).
Comparisons (less than, greater than, equal to) are all O(1).
All trigonometric and inverse trigonometric functions are O(1).
Exponentiation and log-taking are both O(1).
Conversion to integers by either "floor" or "ceil" is O(1).

Regarding arrays

Allocating/deallocating an array (of reals or integers) of any size is O(1) time. (An array stores a single integer/real in each of its cells. Cell indices are integers. Arrays start off as non-initialized, meaning that if an array cell is read before it was ever written to, the value read may be any integer or real. Arrays cannot change their sizes once allocated.)
Accessing a given array position for either reading or writing is O(1). (Accessing an array position outside the array bounds [either by use of an index with a negative value or one larger than the array's maximum] leads to undefined results. Array indices are zero based.)
Input and output of the program are special cases of array reading and array writing (respectively), and follow the same complexity.

Note that use of an integer/real variable is modeled as the use of an array of size 1. Integer/real constants (i.e. program literals) are like variables, but unlike regular arrays/variables do get initialized and cannot be overwritten with new values.
Regarding flow control

Jumps are performed in O(1) time.
Conditional jumps are perfomed in O(1) time, in addition to the time it takes to evaluate the condition.

Though anybody who has done any complexity calculation has probably been exposed to this computational model, its assumptions are rarely stated explicitly. They are repeated here because in riddles they are often stretched ad absurdum, so it is useful to keep them in mind.
Post 01 Aug 2017, 15:20
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >

Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.