Subjects | Gate Vidyalay

Converting NFA to DFA | Solved Examples

Non-Deterministic Finite Automata-

Before you go through this article, make sure that you have gone through the previous article on Non-Deterministic Finite Automata.

In Non-Deterministic Finite Automata,

For some current state and input symbol, there exists more than one next output states.
A string is accepted only if there exists at least one transition path starting at initial state and ending at final state.

In this article, we will discuss how to convert a given NFA to a DFA.

Converting NFA to DFA-

The following steps are followed to convert a given NFA to a DFA-

Step-01:

Let Q’ be a new set of states of the DFA. Q’ is null in the starting.
Let T’ be a new transition table of the DFA.

Step-02:

Add start state of the NFA to Q’.
Add transitions of the start state to the transition table T’.
If start state makes transition to multiple states for some input alphabet, then treat those multiple states as a single state in the DFA.

In NFA, if the transition of start state over some input alphabet is null,

then perform the transition of start state over that input alphabet to a dead state in the DFA.

Step-03:

If any new state is present in the transition table T’,

Add the new state in Q’.
Add transitions of that state in the transition table T’.

Step-04:

Keep repeating Step-03 until no new state is present in the transition table T’.

Finally, the transition table T’ so obtained is the complete transition table of the required DFA.

PRACTICE PROBLEMS BASED ON CONVERTING NFA TO DFA-

Problem-01:

Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)-

Solution-

Transition table for the given Non-Deterministic Finite Automata (NFA) is-

State / Alphabet	a	b
→q0	q0	q0, q1
q1	–	*q2
*q2	–	–

Step-01:

Let Q’ be a new set of states of the Deterministic Finite Automata (DFA).

Let T’ be a new transition table of the DFA.

Step-02:

Add transitions of start state q0 to the transition table T’.

State / Alphabet	a	b
→q0	q0	{q0, q1}

Step-03:

New state present in state Q’ is {q0, q1}.

Add transitions for set of states {q0, q1} to the transition table T’.

State / Alphabet	a	b
→q0	q0	{q0, q1}
{q0, q1}	q0	{q0, q1, q2}

Step-04:

New state present in state Q’ is {q0, q1, q2}.

Add transitions for set of states {q0, q1, q2} to the transition table T’.

State / Alphabet	a	b
→q0	q0	{q0, q1}
{q0, q1}	q0	{q0, q1, q2}
{q0, q1, q2}	q0	{q0, q1, q2}

Step-05:

Since no new states are left to be added in the transition table T’, so we stop.

States containing q2 as its component are treated as final states of the DFA.

Finally, Transition table for Deterministic Finite Automata (DFA) is-

State / Alphabet	a	b
→q0	q0	{q0, q1}
{q0, q1}	q0	*{q0, q1, q2}
*{q0, q1, q2}	q0	*{q0, q1, q2}

Now, Deterministic Finite Automata (DFA) may be drawn as-

Problem-02:

Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)-

Solution-

Transition table for the given Non-Deterministic Finite Automata (NFA) is-

State / Alphabet	0	1
→q0	q0	q1, *q2
q1	q1, *q2	*q2
*q2	q0, q1	q1

Step-01:

Let Q’ be a new set of states of the Deterministic Finite Automata (DFA).

Let T’ be a new transition table of the DFA.

Step-02:

Add transitions of start state q0 to the transition table T’.

State / Alphabet	0	1
→q0	q0	{q1, q2}

Step-03:

New state present in state Q’ is {q1, q2}.

Add transitions for set of states {q1, q2} to the transition table T’.

State / Alphabet	0	1
→q0	q0	{q1, q2}
{q1, q2}	{q0, q1, q2}	{q1, q2}

Step-04:

New state present in state Q’ is {q0, q1, q2}.

Add transitions for set of states {q0, q1, q2} to the transition table T’.

State / Alphabet	0	1
→q0	q0	{q1, q2}
{q1, q2}	{q0, q1, q2}	{q1, q2}
{q0, q1, q2}	{q0, q1, q2}	{q1, q2}

Step-05:

Since no new states are left to be added in the transition table T’, so we stop.

States containing q2 as its component are treated as final states of the DFA.

Finally, Transition table for Deterministic Finite Automata (DFA) is-

State / Alphabet	0	1
→q0	q0	*{q1, q2}
*{q1, q2}	*{q0, q1, q2}	*{q1, q2}
*{q0, q1, q2}	*{q0, q1, q2}	*{q1, q2}

Now, Deterministic Finite Automata (DFA) may be drawn as-

Problem-03:

Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA)-

Solution-

Transition table for the given Non-Deterministic Finite Automata (NFA) is-

State / Alphabet	a	b
→q0	*q1, q2	–
*q1	–	–
q2	*q1, q2	q2

Step-01:

Let Q’ be a new set of states of the Deterministic Finite Automata (DFA).

Let T’ be a new transition table of the DFA.

Step-02:

Add transitions of start state q0 to the transition table T’.

State / Alphabet	a	b
→q0	{q1, q2}	Ø (Dead State)

Step-03:

New state present in state Q’ is {q1, q2}.

Add transitions for set of states {q1, q2} to the transition table T’.

State / Alphabet	a	b
→q0	{q1, q2}	Ø
{q1, q2}	{q1, q2}	q2

Step-04:

New state present in state Q’ is q2.

Add transitions for state q2 to the transition table T’.

State / Alphabet	a	b
→q0	{q1, q2}	Ø
{q1, q2}	{q1, q2}	q2
q2	{q1, q2}	q2

Step-05:

Add transitions for dead state {Ø} to the transition table T’.

State / Alphabet	a	b
→q0	{q1, q2}	Ø
{q1, q2}	{q1, q2}	q2
q2	{q1, q2}	q2
Ø	Ø	Ø

Step-06:

Since no new states are left to be added in the transition table T’, so we stop.

States containing q1 as its component are treated as final states of the DFA.

Finally, Transition table for Deterministic Finite Automata (DFA) is-

State / Alphabet	a	b
→q0	*{q1, q2}	Ø
*{q1, q2}	*{q1, q2}	q2
q2	*{q1, q2}	q2
Ø	Ø	Ø

Now, Deterministic Finite Automata (DFA) may be drawn as-

Important Points-

It is important to note the following points when converting a given NFA into a DFA-

Note-01:

After conversion, the number of states in the resulting DFA may or may not be same as NFA.
The maximum number of states that may be present in the DFA are 2^{Number of states in the NFA}.

Note-02:

In general, the following relationship exists between the number of states in the NFA and DFA-

1 <= n <= 2^m

Here,

n = Number of states in the DFA
m = Number of states in the NFA

Note-03:

In the resulting DFA, all those states that contain the final state(s) of NFA are treated as final states.

To gain better understanding about Converting NFA to DFA,

Watch this Video Lecture

Next Article- Parse Tree | Derivations

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Non Deterministic Finite Automata | NFA

Theory of Automata & Computation

Non-Deterministic Finite Automata-

Non-Deterministic Finite Automata (NDFA / NFA) is an automata in which

for some current state and input symbol, there exists more than one next output states.

It is also known as Non-Deterministic Finite Accepter (NFA).

Formal Definition-

Non-Deterministic Finite Automata is defined by the quintuple-

M = (Q, ∑, δ, q₀, F)

where-

Q = finite set of states
∑ = non-empty finite set of symbols called as input alphabets
δ : Q x ∑ → 2^Q is a total function called as transition function
q0 ∈ Q is the initial state
F ⊆ Q is a set of final states

Example of Non-Deterministic Finite Automata Without Epsilon-

Following automata is an example of Non-Deterministic Finite Automata without epsilon-

The above NFA can be defined in form of five tuples as-

{ {A, B, C, D, E, F}, {a, b, c}, δ, A, {D, F} }

where-

{A, B, C, D, E, F} refers to the set of states
{a, b, c} refers to the set of input alphabets
δ refers to the transition function
A refers to the the initial state
{D, F} refers to the set of final states

Transition function δ is defined as-

δ (A, a) = B
δ (A, a) = E
δ (B, b) = C
δ (C, c) = D
δ (E, b) = F
δ (F, c) = E

Transition Table for the above Non-Deterministic Finite Automata is-

States / Alphabets	a	b	c
A	{B, F}	–	–
B	–	C	–
C	–	–	D
D	–	–	–
E	–	F	–
F	–	–	E

Example of Non-Deterministic Finite Automata With Epsilon-

Following automata is an example of Non-Deterministic Finite Automata with epsilon-

The above NFA can be defined in form of five tuples as-

{ {A, B, C}, {0, 1}, δ, A, {A} }

where-

{A, B, C} refers to the set of states
{0, 1} refers to the set of input alphabets
δ refers to the transition function
A refers to the the initial state
{A} refers to the set of final states

Transition function δ is defined as-

δ (A, 1) = B
δ (A, ∈) = C
δ (B, 0) = A
δ (B, 0) = C
δ (B, 1) = C

Transition Table for the above Non-Deterministic Finite Automata is-

States / Alphabets	0	1	∈
A	–	B	C
B	{A, C}	C	–
C	–	–	–

Dead Configuration or Trap State-

In Non-Deterministic Finite Automata,

The result of a transition function may be empty.
In such a case, automata gets stopped forcefully after entering that configuration.
This type of configuration is known as dead configuration.
The string gets rejected after entering the dead configuration.

Equivalence of DFA and NFA-

Two finite accepters are said to be equal in power if they both accepts the same language.

DFA and NFA are both exactly equal in power.

Example-

Consider a language L(M) = { (10)ⁿ : n >= 0 }

Equivalent NFA for the language L(M) is-

Equivalent DFA for the language L(M) is-

Both the above automata accepts the same language L(M).
Thus, both are equal in power.

Important Points

It is important to note the following points-

Both DFA and NFA are exactly same in power.
For any regular language, both DFA and NFA can be constructed.
There exists an equivalent DFA corresponding to every NFA.
Every NFA can be converted into its equivalent DFA.
There exists no NFA that can not be converted into its equivalent DFA.
Every DFA is a NFA but every NFA is not a DFA.

Acceptance by NFA-

A string ‘w’ is said to be accepted by a NFA if

there exists at least one transition path on which we start at initial state and ends at final state.

δ* (q₀, w) = F

Example-

Consider the following NFA-

For the string w = ab,

There exists two transition paths.
One transition path starts at initial state and ends at final state.
Therefore, string w = ab is accepted by the NFA.

To gain better understanding about Non-Deterministic Finite Automata,

Watch this Video Lecture

Next Article- Converting NFA to DFA

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Mid Point Circle Drawing Algorithm

Computer Graphics

Circle Drawing Algorithms-

In computer graphics, popular algorithms used to generate circle are-

Mid Point Circle Drawing Algorithm
Bresenham’s Circle Drawing Algorithm

In this article, we will discuss about Mid Point Circle Drawing Algorithm.

Mid Point Circle Drawing Algorithm-

Given the centre point and radius of circle,

Mid Point Circle Drawing Algorithm attempts to generate the points of one octant.

The points for other octacts are generated using the eight symmetry property.

Procedure-

Given-

Centre point of Circle = (X₀, Y₀)
Radius of Circle = R

The points generation using Mid Point Circle Drawing Algorithm involves the following steps-

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

Step-03:

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point of the first octant depending on the value of decision parameter P_k.

Follow the below two cases-

Step-04:

If the given centre point (X₀, Y₀) is not (0, 0), then do the following and plot the point-

X_plot = X_c + X₀
Y_plot = Y_c + Y₀

Here, (X_c, Y_c) denotes the current value of X and Y coordinates.

Step-05:

Keep repeating Step-03 and Step-04 until X_plot >= Y_plot.

Step-06:

Step-05 generates all the points for one octant.

To find the points for other seven octants, follow the eight symmetry property of circle.

This is depicted by the following figure-

Also Read- Line Drawing Algorithms

PRACTICE PROBLEMS BASED ON MID POINT CIRCLE DRAWING ALGORITHM-

Problem-01:

Given the centre point coordinates (0, 0) and radius as 10, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (0, 0)
Radius of Circle = 10

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R = 10

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

P₀ = 1 – 10

P₀ = -9

Step-03:

As P_initial < 0, so case-01 is satisfied.

Thus,

X_k+1 = X_k + 1 = 0 + 1 = 1
Y_k+1 = Y_k = 10
P_k+1= P_k + 2 x X_k+1 + 1 = -9 + (2 x 1) + 1 = -6

Step-04:

This step is not applicable here as the given centre point coordinates is (0, 0).

Step-05:

Step-03 is executed similarly until X_k+1 >= Y_k+1 as follows-

P_k	P_k+1	(X_k+1, Y_k+1)
		(0, 10)
-9	-6	(1, 10)
-6	-1	(2, 10)
-1	6	(3, 10)
6	-3	(4, 9)
-3	8	(5, 9)
8	5	(6, 8)
Algorithm Terminates These are all points for Octant-1.

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

Octant-1 Points	Octant-2 Points
(0, 10)	(8, 6)
(1, 10)	(9, 5)
(2, 10)	(9, 4)
(3, 10)	(10, 3)
(4, 9)	(10, 2)
(5, 9)	(10, 1)
(6, 8)	(10, 0)
These are all points for Quadrant-1.

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately.

Here, all the points have been generated with respect to quadrant-1-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(0, 10)	(0, 10)	(0, -10)	(0, -10)
(1, 10)	(-1, 10)	(-1, -10)	(1, -10)
(2, 10)	(-2, 10)	(-2, -10)	(2, -10)
(3, 10)	(-3, 10)	(-3, -10)	(3, -10)
(4, 9)	(-4, 9)	(-4, -9)	(4, -9)
(5, 9)	(-5, 9)	(-5, -9)	(5, -9)
(6, 8)	(-6, 8)	(-6, -8)	(6, -8)
(8, 6)	(-8, 6)	(-8, -6)	(8, -6)
(9, 5)	(-9, 5)	(-9, -5)	(9, -5)
(9, 4)	(-9, 4)	(-9, -4)	(9, -4)
(10, 3)	(-10, 3)	(-10, -3)	(10, -3)
(10, 2)	(-10, 2)	(-10, -2)	(10, -2)
(10, 1)	(-10, 1)	(-10, -1)	(10, -1)
(10, 0)	(-10, 0)	(-10, 0)	(10, 0)
These are all points of the Circle.

Problem-02:

Given the centre point coordinates (4, -4) and radius as 10, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (4, -4)
Radius of Circle = 10

As stated in the algorithm,

We first calculate the points assuming the centre coordinates is (0, 0).
At the end, we translate the circle.

Step-01, Step-02 and Step-03 are already completed in Problem-01.

Now, we find the values of X_plot and Y_plot using the formula given in Step-04 of the main algorithm.

The following table shows the generation of points for Quadrant-1-

X_plot = X_c + X₀= 4 + X₀
Y_plot = Y_c + Y₀ = 4 + Y₀

(X_k+1, Y_k+1)	(X_plot, Y_plot)
(0, 10)	(4, 14)
(1, 10)	(5, 14)
(2, 10)	(6, 14)
(3, 10)	(7, 14)
(4, 9)	(8, 13)
(5, 9)	(9, 13)
(6, 8)	(10, 12)
(8, 6)	(12, 10)
(9, 5)	(13, 9)
(9, 4)	(13, 8)
(10, 3)	(14, 7)
(10, 2)	(14, 6)
(10, 1)	(14, 5)
(10, 0)	(14, 4)
These are all points for Quadrant-1.

The following table shows the points for all the quadrants-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(4, 14)	(4, 14)	(4, -6)	(4, -6)
(5, 14)	(3, 14)	(3, -6)	(5, -6)
(6, 14)	(2, 14)	(2, -6)	(6, -6)
(7, 14)	(1, 14)	(1, -6)	(7, -6)
(8, 13)	(0, 13)	(0, -5)	(8, -5)
(9, 13)	(-1, 13)	(-1, -5)	(9, -5)
(10, 12)	(-2, 12)	(-2, -4)	(10, -4)
(12, 10)	(-4, 10)	(-4, -2)	(12, -2)
(13, 9)	(-5, 9)	(-5, -1)	(13, -1)
(13, 8)	(-5, 8)	(-5, 0)	(13, 0)
(14, 7)	(-6, 7)	(-6, 1)	(14, 1)
(14, 6)	(-6, 6)	(-6, 2)	(14, 2)
(14, 5)	(-6, 5)	(-6, 3)	(14, 3)
(14, 4)	(-6, 4)	(-6, 4)	(14, 4)
These are all points of the Circle.

Advantages of Mid Point Circle Drawing Algorithm-

The advantages of Mid Point Circle Drawing Algorithm are-

It is a powerful and efficient algorithm.
The entire algorithm is based on the simple equation of circle X² + Y² = R².
It is easy to implement from the programmer’s perspective.
This algorithm is used to generate curves on raster displays.

Disadvantages of Mid Point Circle Drawing Algorithm-

The disadvantages of Mid Point Circle Drawing Algorithm are-

Accuracy of the generating points is an issue in this algorithm.
The circle generated by this algorithm is not smooth.
This algorithm is time consuming.

Important Points

Circle drawing algorithms take the advantage of 8 symmetry property of circle.
Every circle has 8 octants and the circle drawing algorithm generates all the points for one octant.
The points for other 7 octants are generated by changing the sign towards X and Y coordinates.
To take the advantage of 8 symmetry property, the circle must be formed assuming that the centre point coordinates is (0, 0).
If the centre coordinates are other than (0, 0), then we add the X and Y coordinate values with each point of circle with the coordinate values generated by assuming (0, 0) as centre point.

To gain better understanding about Mid Point Circle Drawing Algorithm,

Watch this Video Lecture

Next Article- Bresenham Circle Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Insertion Sort Algorithm | Example | Time Complexity

Design & Analysis of Algorithms

Insertion Sort-

Insertion sort is an in-place sorting algorithm.
It uses no auxiliary data structures while sorting.
It is inspired from the way in which we sort playing cards.

How Insertion Sort Works?

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

Insertion sort works as-

Firstly,

It selects the second element (2).
It checks whether it is smaller than any of the elements before it.
Since 2 < 6, so it shifts 6 towards right and places 2 before it.
The resulting list is 2, 6, 11, 7, 5.

Secondly,

It selects the third element (11).
It checks whether it is smaller than any of the elements before it.
Since 11 > (2, 6), so no shifting takes place.
The resulting list remains the same.

Thirdly,

It selects the fourth element (7).
It checks whether it is smaller than any of the elements before it.
Since 7 < 11, so it shifts 11 towards right and places 7 before it.
The resulting list is 2, 6, 7, 11, 5.

Fourthly,

It selects the fifth element (5).
It checks whether it is smaller than any of the elements before it.
Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5 before them.
The resulting list is 2, 5, 6, 7, 11.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

Insertion Sort Algorithm-

Let A be an array with n elements. The insertion sort algorithm used for sorting is as follows-

for (i = 1 ; i < n ; i++)

{

key = A [ i ];

j = i - 1;

while(j > 0 && A [ j ] > key)

{

A [ j+1 ] = A [ j ];

j--;

}

A [ j+1 ] = key;

}

for (i = 1 ; i < n ; i++) { key = A [ i ]; j = i - 1; while(j > 0 && A [ j ] > key) { A [ j+1 ] = A [ j ]; j--; } A [ j+1 ] = key; }

for (i = 1 ; i < n ; i++)

{

   key = A [ i ];

   j = i - 1;

   while(j > 0 && A [ j ] > key)

   {

       A [ j+1 ] = A [ j ];

       j--;

    }

    A [ j+1 ] = key;

}

Here,

i = variable to traverse the array A
key = variable to store the new number to be inserted into the sorted sub-array
j = variable to traverse the sorted sub-array

Insertion Sort Example-

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above insertion sort algorithm works as illustrated below-

Step-01: For i = 1

Step-02: For i = 2

Step-03: For i = 3

2	5	11	7	6	For j = 2; 11 > 7 so A[3] = 11
2	5	11	11	6	For j = 1; 5 < 7 so loop stops and A[2] = 7
2	5	7	11	6	After inner loop ends

Working of inner loop when i = 3

Step-04: For i = 4

Loop gets terminated as ‘i’ becomes 5. The state of array after the loops are finished-

With each loop cycle,

One element is placed at the correct location in the sorted sub-array until array A is completely sorted.

Time Complexity Analysis-

Selection sort algorithm consists of two nested loops.
Owing to the two nested loops, it has O(n²) time complexity.

	Time Complexity
Best Case	n
Average Case	n²
Worst Case	n²

Space Complexity Analysis-

Selection sort is an in-place algorithm.
It performs all computation in the original array and no other array is used.
Hence, the space complexity works out to be O(1).

Important Notes-

Insertion sort is not a very efficient algorithm when data sets are large.
This is indicated by the average and worst case complexities.
Insertion sort is adaptive and number of comparisons are less if array is partially sorted.

To gain better understanding about Insertion Sort Algorithm,

Watch this Video Lecture

Next Article- Merge Sort

Other Popular Sorting Algorithms-

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Selection Sort Algorithm | Example | Time Complexity

Design & Analysis of Algorithms

Selection Sort-

Selection sort is one of the easiest approaches to sorting.
It is inspired from the way in which we sort things out in day to day life.
It is an in-place sorting algorithm because it uses no auxiliary data structures while sorting.

How Selection Sort Works?

Consider the following elements are to be sorted in ascending order using selection sort-

6, 2, 11, 7, 5

Selection sort works as-

It finds the first smallest element (2).
It swaps it with the first element of the unordered list.
It finds the second smallest element (5).
It swaps it with the second element of the unordered list.
Similarly, it continues to sort the given elements.

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

Selection Sort Algorithm-

Let A be an array with n elements. Then, selection sort algorithm used for sorting is as follows-

for (i = 0 ; i < n-1 ; i++)

{

index = i;

for(j = i+1 ; j < n ; j++)

{

if(A[j] < A[index])

index = j;

}

temp = A[i];

A[i] = A[index];

A[index] = temp;

}

for (i = 0 ; i < n-1 ; i++) { index = i; for(j = i+1 ; j < n ; j++) { if(A[j] < A[index]) index = j; } temp = A[i]; A[i] = A[index]; A[index] = temp; }

for (i = 0 ; i < n-1 ; i++)

{

   index = i;

   for(j = i+1 ; j < n ; j++)

   {

      if(A[j] < A[index])

      index = j;

   }

   temp = A[i];

   A[i] = A[index];

   A[index] = temp;

}

Here,

i = variable to traverse the array A
index = variable to store the index of minimum element
j = variable to traverse the unsorted sub-array
temp = temporary variable used for swapping

Selection Sort Example-

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

The above selection sort algorithm works as illustrated below-

Step-01: For i = 0

Step-02: For i = 1

Step-03: For i = 2

Step-04: For i = 3

Step-05: For i = 4

Loop gets terminated as ‘i’ becomes 4.

The state of array after the loops are finished is as shown-

With each loop cycle,

The minimum element in unsorted sub-array is selected.
It is then placed at the correct location in the sorted sub-array until array A is completely sorted.

Time Complexity Analysis-

Selection sort algorithm consists of two nested loops.
Owing to the two nested loops, it has O(n²) time complexity.

	Time Complexity
Best Case	n²
Average Case	n²
Worst Case	n²

Space Complexity Analysis-

Selection sort is an in-place algorithm.
It performs all computation in the original array and no other array is used.
Hence, the space complexity works out to be O(1).

Important Notes-

Selection sort is not a very efficient algorithm when data sets are large.
This is indicated by the average and worst case complexities.
Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms.

To gain better understanding about Selection Sort Algorithm,

Watch this Video Lecture

Next Article- Bubble Sort

Other Popular Sorting Algorithms-

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Category: Subjects

Non-Deterministic Finite Automata-

Converting NFA to DFA-

Step-01:

Step-02:

Step-03:

Step-04:

PRACTICE PROBLEMS BASED ON CONVERTING NFA TO DFA-

Problem-01:

Solution-

Step-01:

Step-02:

Step-03:

Step-04:

Step-05:

Problem-02:

Solution-

Step-01:

Step-02:

Step-03:

Step-04:

Step-05:

Problem-03:

Solution-

Step-01:

Step-02:

Step-03:

Step-04:

Step-05:

Step-06:

Important Points-

Note-01:

Note-02:

Note-03:

Non-Deterministic Finite Automata-

Formal Definition-

Example of Non-Deterministic Finite Automata Without Epsilon-

Example of Non-Deterministic Finite Automata With Epsilon-

Dead Configuration or Trap State-

Equivalence of DFA and NFA-

Example-

Important Points

Acceptance by NFA-

Example-

Circle Drawing Algorithms-

Mid Point Circle Drawing Algorithm-

Procedure-

Step-01:

Step-02:

Step-03:

Step-04:

Step-05:

Step-06:

PRACTICE PROBLEMS BASED ON MID POINT CIRCLE DRAWING ALGORITHM-

Problem-01:

Solution-

Step-01:

Step-02:

Step-03:

Step-04:

Step-05:

Problem-02:

Solution-

Advantages of Mid Point Circle Drawing Algorithm-

Disadvantages of Mid Point Circle Drawing Algorithm-

Important Points

Insertion Sort-

How Insertion Sort Works?

Insertion Sort Algorithm-

Insertion Sort Example-

Step-01: For i = 1

Step-02: For i = 2

Step-03: For i = 3

Step-04: For i = 4

Time Complexity Analysis-

Space Complexity Analysis-

Important Notes-

Other Popular Sorting Algorithms-

Selection Sort-

How Selection Sort Works?