UNIT-3
Sorting Networks
Introduction
A "sorting network" is a computational model where data is sorted by passing
through a network of wires and comparators, allowing multiple comparisons to
happen simultaneously, effectively sorting a list of elements in parallel by
comparing pairs of values at each stage; essentially, it's a way to arrange data
in ascending order by performing comparisons in a structured, parallel
manner, unlike traditional sorting algorithms that compare only one pair at a
time.
Key points about sorting networks:
Components:
A sorting network consists of wires that carry data and comparators that
perform pairwise comparisons between values on connected wires.
Parallelism:
The key feature is that multiple comparisons can happen simultaneously at
different levels of the network, enabling faster sorting for larger datasets.
Comparator function:
When two values meet a comparator, the comparator swaps them if the
value on the "top" wire is greater than the value on the "bottom" wire.
Applications:
Sorting networks are useful in hardware design for parallel processing,
particularly in situations where fast sorting with minimal latency is required.
Comparison Networks
Comparison Networks are a type of sorting networks which
always sort their inputs. Wires and comparator comprise comparison
network. A Comparator is a device which has two inputs (x, y) and
outputs (x’, y’). It performs the following function:
x' = min(x, y),
y' = max(x, y)
Comparators are conventionally drawn as single vertical lines where
input is on the left and output on right. Smaller input values are put
on top output while larger input values are put on bottom output.
thus comparator can be thought of as sorting its two inputs. It is
assumed that each comparator operates in O(1) time i.e time
between appearance of input values and production of output is
constant.
The second component of comparison networks i.e. wires performs the function
of transmitting a value from one place to another. These are either network input
wires or network output wires. Wires are capable of connecting input of a
comparator to output of other.
Properties:
Graph is required to be acyclic.
Output is produced only when input is available.
Comparators process in parallel if input is available.
Sorting network is a comparison network where the output is sorted.
Not all comparison networks are sorting networks.
A comparison network is like a procedure which specifies how comparisons
are to occur.
Ex:
The zero-one principle
The zero-one principle says that if a sorting network works correctly when
each input is drawn from the set {0, 1}, then it works correctly on arbitrary input
numbers. (The numbers can be integers, reals, or, in general, any set of values
from any linearly ordered set.)
As we construct sorting networks and other comparison networks, the
zero-one principle will allow us to focus on their operation for input sequences
consisting solely of 0’s and 1’s. Once we have constructed a sorting network and
proved that it can sort all zero-one sequences, we shall appeal to the zero-one
principle to show that it properly sorts sequences of arbitrary values.
Lemma 27.1 If a comparison network transforms the input sequence a =
ha1, a2, . . . , ani into the output sequence b = hb1, b2, . . . , bni, then for any
monotonically increasing function f , the network transforms the input sequence f
(a) = h f (a1), f (a2), . . . , f (an)i into the output sequence f (b) = h f (b1), f (b2), . . . ,
f (bn)i. Proof We shall first prove the claim that if f is a monotonically increasing
function, then a single comparator with inputs f (x) and f (y) produces outputs f
(min(x, y)) and f (max(x, y)). We then use induction to prove the lemma.
Bitonic Sequence
A bitonic sequence is a sequence of numbers that increases and then
decreases:
Definition: A bitonic sequence is a sequence of numbers that is first
strictly increasing and then strictly decreasing.
A bitonic sorter is a comparison network that sorts bitonic sequences of 0's
and 1's. It works by recursively connecting half-cleaners to produce two
bitonic sequences of half the size. The process continues until the last
merges them into a single, sorted list.
The half-cleaner
A bitonic sorter is composed of several stages, each of which is called a
halfcleaner. Each half-cleaner is a comparison network of depth 1 in which
input line i is compared with line i + n/2 for i = 1, 2, . . . , n/2.
Merging Network
Our sorting network will be constructed from merging networks, which are networks that can merge
two sorted input sequences into one sorted output sequence. We modify BITONIC-SORTER[n] to
create the merging network MERGER[n]. As with the bitonic sorter, we shall prove the correctness
of the merging network only for inputs that are zero-one sequences.
The merging network is based on the following intuition. Given two sorted sequences, if we reverse
the order of the second sequence and then concatenate the two sequences, the resulting sequence
is bitonic. For example, given the sorted zero-one sequences X = 00000111 and Y = 00001111, we
reverse Y to get Yr = 11110000.
Concatenating X and Y R yields 0000011111110000, which is bitonic. Thus, to merge the two input
sequences X and Y , it suffices to perform a bitonic sort on X concatenated with Yr .
Ch-2 Matrix operations
Strassens matrix multiplication,
Inverting Matrices
Before calculating the inverse of a matrix let us understand what a matrix is?
A matrix is a definite collection of objects arranged in rows and columns These objects
are called elements of the matrix.
The order of a matrix is written as number rows by number of columns. For example, 2 ×
2, 2 × 3, 3 × 2, 3 × 3, 4 × 4 and so on.
We can find the matrix inverse only for square matrices, whose number of rows and
columns are equal such as 2 × 2, 3 × 3, etc.
Matrix Inverse
If A is a non-singular square matrix, there is an existence of n x n matrix A-1, which is
called the inverse matrix of A such that it satisfies the property:
AA-1 = A-1A = I, where I is the Identity matrix
The identity matrix for the 2 x 2 matrix is given by
---------------------------------------------------------------------------------------
Identity Matrix Definition
An identity matrix is a square matrix in which all the elements of principal diagonals are
one, and all other elements are zeros. It is denoted by the notation “I n” or simply “I”. If
any matrix is multiplied with the identity matrix, the result will be given matrix. The
elements of the given matrix remain unchanged. In other words, if all the main diagonal
of a square matrix are 1’s and rest all o’s, it is called an identity matrix. Here, the 2 × 2
and 3 × 3 identity matrix is given below:
2 × 2 Identity Matrix
This is also called the identity matrix of order 2.
3× 3 Identity Matrix
This is known as the identity matrix of order 3 or unit matrix of order 3 × 3.
---------------------------------------------------------------------------------------------------
It is noted that in order to find the inverse matrix, the square matrix should be non-
singular whose determinant value does not equals to zero.
Let us take the square matrix A
Where a, b, c, and d represents the number.
The determinant of the matrix A is written as ad-bc, where the value of determinant
should not equal to zero for the existence of inverse. The inverse matrix can be found
for 2× 2, 3× 3, …n × n matrices. Finding the inverse of a 3×3 matrix is a bit more difficult
than finding the inverses of a 2 ×2 matrix.
Inverse Matrix Method
The inverse of a matrix can be found using the three different methods. However, any
of these three methods will produce the same result.
Method:
Inverse Matrix 2 x 2 Example
To understand this concept better let us take a look at the following example.
Example: Find the inverse of matrix A given below:
System of linear equation:
https://www.geeksforgeeks.org/system-linear-equations/
