Programming Basics

Insertion Sort

The implementation of Insertion sort - the helper function “swap” swaps two elements of a list, and then InsertionSort itself goes through the list swapping elements that are “out of order”.

Swap[inlist_, a_, b_] := Module[{holder, outlist},
outlist = inlist;
holder = outlist[[b]];
outlist[[b]] = outlist[[a]];
outlist[[a]] = holder;
Return[outlist];
]

InsertionSort[inlist_] := Module[{outlist, indexx, indexy, curelm, Nlist},
outlist = inlist;
Nlist = Length[outlist];
For[indexx = 2, indexx ≤ Nlist, indexx = indexx + 1,
curelm = outlist[[indexx]];
indexy = indexx - 1;
While[indexy >  0 && outlist[[indexy]] > curelm, 
outlist = Swap[outlist, indexy, indexy+1];
indexy = indexy - 1;
];
outlist[[indexy+1]] = curelm;
];
Return[outlist]
]

A simple test:

InsertionSort[{5,2,4,6,1,3}]

Make sure negative numbers are handled appropriately:

InsertionSort[{-4,1,7,2,3,-10}]

We can time the function using “Timing”:

X = Table[RandomReal[{-10,10}],{j,1,100}];
Timing[InsertionSort[X]]

According to the Timing function, InsertionSort took ~.03 seconds to sort this list of 100 elements.

Plotting

We can plot lists - if there is only one element at each location in a table, the x-component is the integer index of that location, the y-component is the value found there:

X = Table[Sin[2.0 Pi t],{t,0.0,1.0,.01}];
ListPlot[X,PlotStyle->GrayLevel[0.5]]

If the table consists of pairs, the first of each pair is taken as the x-value, the second as the y-value:

Y = Table[{t, t^2},{t,0.0,6.0,1.0}];
ListLinePlot[Y,PlotStyle->GrayLevel[0.5]]

Recursion

IsDivisableByTwo returns True if “inx” is divisible by two, and False if not.

IsDivisableByTwo[inx_] := Module[{retval,div,NZERO},
NZERO = 10^(-10);
div = inx/2;
If[Abs[div - Round[div]] >  NZERO,
retval = False;
,
retval = True;
];
Return[retval];
]

A simple recursive function, DivideByTwo takes “num” and, if it is divisible by two, calls itself with num/2 as input, otherwise, the function returns num.

DivideByTwo[num_] := Module[{retval},
Print[num];
retval = num;
If[IsDivisableByTwo[retval] == True,
retval = DivideByTwo[num/2];
];
Return[retval];
]

DivideByTwo[88]

Merge Sort

A recursive form of sorting, MergeSort takes a list, divides it in two and MergeSorts each side, then calls Merge to re-assemble the lists in order.  The recursion continues until there is only one element in the list.

MergeSort[inlist_] := Module[{outlist, oleft, oright,mid},
outlist = inlist;
If[Length[outlist] == 1, Return[outlist];];
mid = Floor[Length[outlist]/2];
oleft = MergeSort[Take[outlist,{1,mid}]];
oright = MergeSort[Take[outlist,{mid+1,Length[outlist]}]];
outlist = Merge[oleft,oright];
Return[outlist];
]

Merge[inla_, inlb_] := Module[{outlist, lista, listb,
index=1, adex=1, bdex=1},
If[Length[inla] == 0, lista = {inla};, lista = inla;];
If[Length[inlb] == 0, listb = {inlb};, listb = inlb;];

outlist = Table[0,{j,1,Length[lista] + Length[listb]}];
While[adex ≤ Length[lista] && bdex ≤ Length[listb],
If[lista[[adex]] ≤  listb[[bdex]],
outlist[[index]] = lista[[adex]];
adex = adex + 1;
,
outlist[[index]] = listb[[bdex]];
bdex = bdex + 1;
];
index = index + 1;
];
If[adex >  Length[lista],
For[bdex = bdex, bdex ≤ Length[listb], bdex = bdex+1,
outlist[[index]] = listb[[bdex]];
index = index + 1;
];
,
For[adex = adex, adex ≤ Length[lista], adex = adex+1,
outlist[[index]] = lista[[adex]];
index = index + 1;
];
];
Return[outlist];
]

First, we’ll run a simple test:

MergeSort[{10,-1,8,3,5,6,0,-20}]

X = Table[RandomReal[{-10,10}],{j,1,100}];
Timing[MergeSort[X]]

To sort a table of size 100, MergeSort takes ~.01 seconds, less than the InsertionSort case above.

Time Average

An example of a “function pointer” - TimeAverage takes, as input, a function “f” and the time over which to average, “T”.

TimeAverage[f_,T_] := Module[{retval},
retval = (1/T) Integrate[f[t],{t,0,T}];
Return[retval];
]

userfunction1[t_] := Sin[t]^2

We send in the function to time average, it can be called anything:

TimeAverage[userfunction1,2.0Pi]

userfunction2[t_] := Sin[t] Cos[t]

TimeAverage[userfunction2,2.0 Pi]

Array Indexing

This is an example of a table of tables, meant to illuminate the indexing used in Mathematica to isolate elements:

tXV = { {0.0,{0.1,0.0}}, {0.1,{0.11,0.2}},{0.2,{0.14,0.4}},{0.3,{0.19, 0.6}} }

The second element of tXV:

tXV[[2]]

This is the first element of tXV[[2]]

tXV[[2,1]]

and here is the second:

tXV[[2,2]]

the first element of above

tXV[[2,2,1]]

We can also refer to these elements in a nested fashion:

tXV[[2]][[2]][[1]]

The generation of this example table can be automated:

tXV = Table[{t, {.1+  t^2 , 2 t}},{t,0,.3,.1}]