2018-08-11, post № 201

**C**, **programming**, #algorithms, #sorting

## Introduction

Continuing my journey implementing various sorting algorithms in C, in this post I am departing from the most well-known algorithms and implementing one of my personal favourites — heapsort.

Download the C source file here: heapsort.c.

Contrary to algorithms like quicksort which immediately jump into action sorting the given array, heapsort operates on a data structure called a *heap* which it efficiently transforms into a sorted list. However, as most arrays are not of the heap structure, heapsort first needs to transform a given array into a heap. Thus heapsort is a two-step process — first creating a heap and then sorting said heap.

Sorting can be applied to an infinite number of objects provided there is an order defined among them. However, not much is gained from changing the underlying value one is sorting which is why in this post I will only focus on sorting integers — technically even only integers in the C type sense; .

## The Heap

A heap is a special type of binary tree that satisfies the *heap property* — every parent node’s value is not less than its child node’s (if existent) values. Furthermore, a heap is maximally filled at every level but possibly the last where the elements are as far left as possible.

From these properties it follows that the greatest value will be located at the root node.

One can also define a heap such that the root node will house the smallest element; such a heap would lead to a list sorted in descending order (more on that later).

( 86 )
/ \
(31) (64)
/ \ /
(20)(-4) (17)
*A heap containing integers.*

2018-07-14, post № 200

**mathematics**, #analysis, #formal calculation, #symbolic

2018-06-28, post № 199

**C**, **programming**,

int
O=19,I=19;typedef long double f
;long fac(long n){return n?n--*fac(
n):1;}f pow(f x,int p){return p--?x
*pow(x,p):1;}f sin(f x){f v=0;for
(int k=~0;++k
<= O;)k%2&&
(v+=(~-k
%4?-1:1)*
pow(x,k)
/fac(k));
return v
;}main()
{f a=6,b
=7, tau;
for (int
j=~0;++j
<I;)sin( tau
=a+(b-a) /2
)>0? (b= tau
):(a=tau ) ;
printf ( "%ca"
"u ~ %.*Lf",116,
O,tau);}

*Try it online!*

Happy tau day.

2018-06-16, post № 198

**mathematics**, **programming**, **Python**, #logic, #proposition calculus

Proposition calculus deals with statements and the relation between statements, where each of them can only be in one of two states; . Therefore, when working with finitely many connected propositions, one can algorithmically determine all possible truth values of all atomic and thus connected propositions.

*Truth* is command-line tool which was written to precisely perform those computations; computing a logical expression’s truth value. Download link: truth.py

A list of all supportet operators can be seen by invoking the tool with a `--help`

flag.

This project was inspired by Albert Menne’s *Einführung in die Logik*; the operator syntax used is similar to his, translated to be 7-bit-ASCII-compatible.

*Truth* can be used to either verify universally true statements, e. g. *tertium non datur* and a property of the replication, *verum sequitur ex quodlibet*.

-(p&-p) <-> 1 , 1 <- p
1 0010 1 1 1 1 0
1 1001 1 1 1 1 1

Though not only absolute truth, but also complete relational equivalence between two expressions can be shown.

(p->q)|(r>-<s) <-> q|(r|s)&-(r&s)|-p
01 0 1 0 0 0 1 00 000 01 000 110
10 0 0 0 0 0 1 00 000 01 000 001
01 1 1 0 0 0 1 11 000 01 000 110
11 1 1 0 0 0 1 11 000 01 000 101
01 0 1 1 1 0 1 01 110 11 100 110
10 0 1 1 1 0 1 01 110 11 100 101
01 1 1 1 1 0 1 11 110 11 100 110
11 1 1 1 1 0 1 11 110 11 100 101
01 0 1 0 1 1 1 01 011 11 001 110
10 0 1 0 1 1 1 01 011 11 001 101
01 1 1 0 1 1 1 11 011 11 001 110
11 1 1 0 1 1 1 11 011 11 001 101
01 0 1 1 0 1 1 00 111 00 111 110
10 0 0 1 0 1 1 00 111 00 111 001
01 1 1 1 0 1 1 11 111 00 111 110
11 1 1 1 0 1 1 11 111 00 111 101

Complete contravalence can also be shown.

-(p/-p>-<0)|p->q<-r >-< p&-q&r
0 0110 1 0 101 01 0 1 001000
0 1101 1 0 110 01 0 1 111000
0 0110 1 0 101 11 0 1 000100
0 1101 1 0 111 11 0 1 100100
0 0110 1 0 101 01 1 1 001001
0 1101 1 0 010 00 1 1 111011
0 0110 1 0 101 11 1 1 000101
0 1101 1 0 111 11 1 1 100101

2018-05-19, post № 197

**art**, #analogue, #photography, #pinhole photography, #WWPD

On the last sunday in April of 2018, the 29th, to commemorate Worldwide Pinhole Day, I ventured out in the wilderness to capture a few photons.

2018-05-12, post № 196

**JavaScript**, **programming**, #lambda function

2018-04-21, post № 195

**art**, #LED, #photography

2018-03-28, post № 194

, #2017, #collage

Today marks this blog’s third anniversary. To celebrate and take a look back at the year, I have collected a few image highlights.

17500615947440398742637684298448259300459653195179624088723406481656498345927782897306957959023081425157582777952426879442535942327333206022815634243070984075006080698433225695442819778347008.0

Posts:

249-242, 241-234, 233-226, 225-218, 217-210, 209-202, **201-194**, 193-186, 185-178, 177-170, 169-162, 161-154, 153-146, 145-138, 137-130, 129-122, 121-114, 113-106, 105-98, 97-90, 89-82, 81-74, 73-66, 65-58, 57-50, 49-42, 41-34, 33-26, 25-18, 17-10, 9-2, 1-1Jonathan Frech's blog; built 2021/10/02 17:36:09 CEST