UNITY (programming language): Difference between revisions

Revision as of 17:32, 8 November 2005

Revision as of 22:29, 8 November 2005

Line 2:

All statements are assignments, and are separated by <code>#</code>. A statement can consist of multiple assignments, on the form <code>a,b,c := x,y,z</code>, or <code>a := x || b := y || c := z</code>. You can also have a ''quantified statement list'', for example <code>&lt;# x,y : 0 &lt; x &lt; y &lt; n :: ''statement''&gt;</code>, where x and y are chosen randomly among the values that satisfy the quantification. A ''quantified assignment'' is similar. In <code><|| x,y : 0 &lt; x &lt; y &lt; n :: ''statement'' &gt;<code>, the statement is executed simultaneously for ''all'' <code>x</code> and <code>y</code> satisfying <code>0 &gt; x &gt; y &lt; n</code>.

==Examples==

===Randomsort===

[[Random sort]] the array by randomly choosing chosing two numbers, and swap them if they are in the wrong order. Using expected exponential time, one processor and expected exponential work.

Program sort

declare

n: integer,

A: array [0..n-1] of integer

initially

n = 20 #

<# i : 0 <= i and i < n :: A[i] = rand() % 100 >

assign

<# i,j : 0 <= i < n and 0 <= j < n ::

A[i], A[j] := A[j], A[i] if i < j and A[i] > A[j] >

end

===Insertionsort===

[[Insertion sort]] the array by comparing adjacent numbers, and swapping them if they are in the wrong order. Using <math>\Theta(n)</math> time, <math>\Theta(n)</math> processors and <math>\Theta(n^2)</math> workprocessors.

Program sort2

Line 40 ⟶ 25:

===Mergesort===

[[Merge sort]] the array using a constant time merge. Using <math>\Theta(\log n)</math> time, <math>\Theta(n^2)</math> processors and <math>\Theta(n^2 \log n)</math> workprocessors. In this example, a value may be written many times simultaneously, and values might be duplicated, since we are not carefull with the <code>&lt;=</code> operator. If you expand the <code>a,b</code> quantification, you can get CREW [[PRAM]] complexity.

Program sort3