Friends,

Here is the textbook notes for Radix sort and Hashing (sorting techniques).

Thank You

Skip to content
# CSE 205: Radix sort and Hashing

# CSE 205: Complexity of various sorting techniques

# Stack

# Linked list Algorithm 2

# Algorithms in Linked List

# Chapter: Linked List

__INTRODUCTION__

## What is need of Linked list?

__DEFINITION__

__Memory representation of linked list__

## Is linked list a linear data structure or non linear?

## Operations on linked list

# Deleting element from an array

# Inserting element into an Array

# Traversing in a Linear Array

# Complexity

Makes education easy and simple – kids labs

Category: Data Structure and Algorithm

Friends,

Here is the textbook notes for Radix sort and Hashing (sorting techniques).

Thank You

Advertisements

Friends,

Here is the * complexity* details for the

Thank you.

The stack was first proposed in 1946, in the computer design of Alan M. Turing (who used the terms “bury” and “unbury”) as a means of calling and returning from subroutines.

A stack is a list of elements in which an element may be inserted or deleted only at one end called the ** TOP** of the stack. It is

**Examples**: Stack of Dishes, Stack of Books, A packet of biscuits, etc.

**AVAIL LIST** (List of free memory spaces) is also implemented using *Stack.*

__Algorithm: (Array representation)__

**– Inserting elements into the stack –
**

__PUSH (STACK, TOP, MAXSTK, DATA)__

- If TOP = MAXSTK, then, write: overflow and exit.
*//checking the stack is full or not* - Set TOP = TOP+1.
*//Increasing TOP by 1* - Set STACK [TOP] = DATA.
*//Inserting DATA into the TOP* - Exit.

//**STACK**: Name of the stack

//**TOP**: Pointer that points to the topmost element of the stack

//**DATA**: information/data to be inserted.

//**MAXSTK**: Maximum index of the stack (maximum size)

**– Deleting elements from the stack –
**

__POP (STACK, TOP, DATA)__

- If TOP = 0, then, write: underflow and Exit.
*//checking for underflow* - Set DATA = STACK [TOP]
*//DATA is the TOP element* - Set TOP = TOP-1
*//decreasing the size of the STACK* - Exit

Author: Sonia Behal

__Header Linked List:__

It has two types: ** Circular header linked list** and

In *circular*, the last node is linked to the header node and in *grounded*, the last node is linked to the NULL.

__Traversing in a circular header linked list__

- Set PTR = LINK [START]
*//initializing a pointer* - Repeat step 3 and 4, while PTR ≠ START
*//PTR ≠ NULL for grounded list* - Apply PROCESS to INFO [PTR]
- Set PTR = LINK [PTR]
*//PTR points to the next node*

[End of while loop]

- Exit

__Two way linked list__

__Insertion (INFO, NEXT, PREV, AVAIL, LOCA, LOCB, ITEM)__

- If AVAIL = NULL, then write: Overflow and Exit
*//checking for overflow* - Set NEW = AVAIL, AVAIL = NEXT [AVAIL], INFO [NEW] = ITEM.

* //removing node from AVAIL list and copy the ITEM into it*

- Set NEXT [LOCA] = NEW, NEXT [NEW] = LOCB,

PREV [LOCB] = NEW, PREV [NEW] = LOCA *//inserting node into the list*

- Exit.

//**INFO**: Data part of the node

//**NEXT**: Next pointer of the node

//**PREV:** Previous pointer of the node

//**AVAIL**: First node of the AVAIL list

//**LOCA** and **LOCB**: Locations in which the new node is to be inserted.

__Deletion (INFO, NEXT, PREV, AVAIL, LOC)__

- Set NEXT [PREV [LOC]] = NEXT [LOC] and PREV [NEXT [LOC]] = PREV [LOC]

*//deleting node*

- Set NEXT [LOC] = AVAIL and AVAIL = LOC
*//inserting node to the AVAIL list* - Exit.

Author: Indrajeet Gupta

__Algorithms in Linked List__

__Traversing:__

- Initialize the Current pointer with the beginning of the List.
- Move the Current pointer to point to the next node in the list and go to step-1, till the list is not over or else quit.

__Searching:__

- Initialize the Current pointer with the beginning of the List.
- Compare the KEY value with the Current node value; if they match then quit here. else go to step-3.
- Move the Current pointer to point to the next node in the list and go to step-2, till the list is not over or else quit.

__Insertion :__

- Get the value for NEW node to be added to the list and its position.
- Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say “Memory shortage”.
- Insert the data value inside the NEW node’s data field.
- Add this NEW node at the desired position (pointed by the “location”) in the LIST.
- Go to step-1 till you have more values to be added to the LIST.

__At Beginning:__

__Insert_At_Beg (INFO, START, NEXT)__

- Create a new node and assign the address to any node say PTR.
- Overflow, If(PTR = NULL)
- write: Overflow and EXIT.

- Assign INFO[PTR] = ITEM
*//assigning the data* *I*f(START = NULL)- Assign NEXT[PTR] = NULL
- Else
- Assign NEXT[PTR] = START

- Assign START = PTR
*//inserting in the beginning* - Exit.

Generally the daily life term **“list”** refers to the linear collection of data,whether the list may be shopping list,a daily routine, invitation list,a schedule,a meeting plan,a grocer’s list.If you want to insert any item in the list simply what you do is:delete that and insert any new item wherever n whenever you want.You can extend,add,remove,modify any item at any time with no constraints in your list.

One such way we know is we can implement list with arrays but why list lets know.

Well we know how arrays work and the representation of arrays in contiguous memory locations.You have also considered the problems

associated with arrays:-

- If there is not enough memory available for allocation??
- If you have to insert the data in sorted order??
- If you want to insert the item at any location??
- If you want to create your list dynamically??
- If you want to delete any item at any location??
- If you want to insert the data of different data types??

Well the above problems are not every time associated with your programming but the Linked list is the smartest way to solve above problems.With arrays we have to make a “for loop” taking the time equal to the size of the arrays. Even if there enough memory spaces available for allocation but not in contiguous manner, your program crashes but with Link list it won’t happen.That’s why Linked list comes into picture and is of great use.

A linked list is a linear collection of data items called nodes and each node is connected to another node with the help of pointers,a node is divided into two subparts first for storing the data item and another for storing the address of the next node.The pointer stores the address and forms a link between two nodes thus this representation to store the data is called Linked list.

Linked list is not stored in the contiguous memory locations.Each node contains the link of next node,so the nodes can be created in the memory irrespective of the order of the data items.

This is the best question asked by the interviewer whether a Linked list is a linear data structure or not because there is controversy and usually student’s get confused.

Yes, the Linked list is a linear data structure.We have seen the memory representation of linked list it is not stored in contiguous memory allocation but while accessing each item in a linked list we move in a linear way.That’s why it is called a Linear data structure.

**Traversal**- Accessing each element in the list is called traversal . A particular process is applied to the data whether addition,division, subtraction,or even just printing the data elements.
**Insertion**- Adding a data element into the list is called insertion.Insertion can be dynamic, in the middle, at end, at beginning.
**Deletion**- Removing a data element from the list is called deletion. Deletion can be at end,after some element, at beginning.
**Searching**- Finding a particular element in the list is called searching.

__Deleting element in an array__

#include<iostream>

#include<conio.h>

using namespace std;

main()

{

int n; //*initialising the size of an array*

cout<<“Enter the size of the array: “;

cin>>n; //*Taking the size from the user*

int arr[n],i=1,loc;

cout<<“Enter the elements of the array: “;

while(i<=n) //*While loop*

{

cin>>arr[i]; //*Taking the elements form the user*

i++; //*Increment the iteration variable*

}

cout<<“Enter the location to be deleted: “;

cin>>loc; //*Taking the value of location from the user*

i=loc; //*Initialise the iteration variable*

while(i<=n) //*while loop*

{

arr[i]=arr[i+1]; //*shifting the elements upward*

i++;

}

i=1;

while(i<n)

{

cout<<arr[i]<<“\t”; //*Displaying the elements*

i++;

}

getch();

}

** Algorithm of the above program:*

__Delete (ARR, LOC, N)__

- Set I=LOC //
*Initialise counter/iteration variable* - Repeat steps 3 and 4 while I<=N
- Set ARR[I] = ARR[I+1] //
*shifting the elements upwards* - Set I = I+1; //
*Increment the counter*

[End of loop]

- Set N=N-1; //
*Reset the size of the array* - Exit

*** Complexity = O(n)**

__Note:__

**For deleting element from an array, the elements are needed to be shifted upwards starting from the location that we want to delete. Then the size of the array should be reduced.**

__Inserting elements into an array__

#include<iostream>

#include<conio.h>

using namespace std;

main()

{

int n; *//intitialising the size of the array*

cout<<“Enter the size of the array: “;

cin>>n; * //taking the size from the user*

int arr[n],i,loc,item; *//initialising array, iteration variable, location, item*

cout<<“Enter the elements of the array: “;

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

{

cin>>arr[i]; *//taking the elements of the array from user*

}

cout<<“Enter the location to be inserted: “;

cin>>loc; *//taking the location from the user*

cout<<“Enter the item to be inserted: “;

cin>>item; *//taking the item from the user*

for(i=n;i>=loc;i- – )

{

arr[i+1]=arr[i]; *//shifting operation*

}

arr[loc]=item; *//inserting the item in that location*

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

{

cout<<arr[i]<<“\t”; * //displaying the elements*

}

getch();

}

** Algorithm of the above program:*

__Insert (ARR,LOC,ITEM,N)__

1. Repeat for I=N to LOC

2. Set ARR[I+1] = ARR[I] * //Shift the elements downwards*

[End of loop]

3. Set ARR[LOC] = ITEM. *//insert the item in that location*

4. N = N+1 * //Reset size of the array*

5. Exit

*** Complexity: O(n)**

__Note:__

**1. For inserting an element in an array, we have to shift the last element to the next location till the location of the new item to be inserted reach. Then we can insert the new element to the location.**

Author: Udipto Goswami

__Traversing in a Linear Array__

Line 1: #include<iostream>

Line 2: #include<conio.h>

Line 3: using namespace std;

Line 4: main()

{

Line 5: int arr[5]={1,2,3,4,5}; // initialising the elements in an array

Line 6: int i; // initialising an iteration variable

Line 7: for(i=0;i<5;i++) // a loop that goes to repeat the process till the end of the array

{

Line 8: cout<<arr[i]; // printing the elements on the screen

}

Line 9: getch();

}

__Algorithm for the above program__

[Note: **LB** = Lower Bound: starting value for the iteration,

**UB** = Upper Bound: ending value for the iteration,

**A** = name of the array]

** Traverse (LB, UB, A)** // Name of the algorithm and the variable that used in the algorithm

- Repeat for K = LB to UB // This statement is similar to
**line 7**

Apply PROCESS to A[K] // This statement is similar to **line 8**

[End of Loop]

- Exit // we have to write
**exit**at last as this shows the algorithm have finished.

**Complexity: O(n)**

**PROBLEM 1: Find the number of elements in an array which are greater than 25.**

**SOLUTION: **__Traverse (A, LB, UB, count)__

- Set count = 0, K = LB //Setting the value of count and iteration variable
- While K<=UB //Repeating the operation till it reached UB
- if A[K] > 25, then: //Checking condition for the elements >25
- count = count+1. //counting the elements >25
- Set K = K+1 //Incrementing the iteration variable

[End of while loop]

- Exit

**Complexity: O(n)**

**PROBLEM 2: Find out the sum of all the two digit numbers in an array.**

**SOLUTION:** __Traverse (A, N, sum)__

- Set sum=0 //Setting the value of sum
- Repeat K = 0 to N //Repeating the operation
- if A[K]>=10 and A[K]<=99, then: //Checking for two digit number
- sum = sum+A[K] //Taking sum of all the two digit numbers

[End of for loop]

- Exit

**Complexity: O(n)**

**NOTE:**

**We can give any name of the algorithm of our wish.****We can use any loop of our own wish; whether***for loop*of*while loop*.**Loop can go from LB to UB or 0 to N. There is no difference between these two statements. And N denotes the size of the array.****We have to write all the major variables that used in the algorithm inside the parenthesis just besides the name of the algorithm**

__Complexity:__

The term complexity is defined as the** time or space requirement** of an algorithm to be executed completely in terms of the input size.

**TIME** and **SPACE **are two major requirements of efficiency of an algorithm.

TIME: Measured by counting the number of **key operations**.

SPACE: Measured by counting the **maximum of memory** needed by the algorithm.

__TIME-SPACE TRADEOFF:__

By increasing the amount of space for storing the data, one may be able to reduce the time needed for processing the data, or vice versa.

__Cases of Complexity:__

**Worst Case:**The maximum value of a function (consider algorithm) for any possible input.**Average Case:**The expected or average value of a function.**Best Case:**Minimum possible value of a function.

Standard Functions of Complexity:

- log
_{2}n - n
- nlogn
- n
^{2} - n
^{3} - 2
^{n}

(Arranged in increasing order)

__Asymptotic Notations:__

These are languages that **allow us to analyse an algorithm’s running time** by identifying its behaviour as the input size for the algorithm increases. This is **also known as an algorithm’s growth rate.**

__BIG-OH (O) Notation:__

Big-oh defines the **upper bound** of a particular function (here specifically algorithm).

**FORMULA: **f(n)**=O(**g(n)**) if **f(n)**<=C **g(n) for n>=n_{0} ; C and n_{0 }are constants.

ALSO CALLED THE **WORST CASE** OF AN ALGORITHM

__Big-Omega (Ω) Notation:__

Big-omega defines the **lower bound** of a particular function (here specifically algorithm).

** FORMULA: **f(n)**=** Ω** (**g(n)**) if **f(n)**>=C **g(n) for n>=n_{0} ; C and n_{0 }are constants.

ALSO CALLED THE **BEST CASE** OF AN ALGORITHM

__Big-Theta (Ө) Notation:__

Big-theta defines the **tight bound** of a particular function (here specifically algorithm).

** FORMULA: **f(n)**=** Ө** (**g(n)**) if ****C _{1}**(n) <= f(n) <=

f(n) = Ө (g(n)), iff f(n) = O(g(n)) and f(n) = Ω (g(n))

ALSO CALLED THE **AVERAGE CASE** OF AN ALGORITHM

__Little-Oh (o) Notation:__

Big-theta defines the **non-tight analogue** of **Big-oh**.

** FORMULA: **f(n) = o (g(n)), if for every c, there exists n_{0 }such that, f(n) <= c g(n) for n >= n_{0}

Used for comparisons of running times.

**PROBLEM FOR FINDING COMPLEXITY:**

**Problem1:**

function ()

{

if (condition)

{

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

{ // simple statements}

}

else

{

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

for (k=n; k>0; k–)

{// simple statement}

}

}

**Complexity:**

- Check the
**for**If for statement is increasing serially i.e i=0,1,2,3… then write**n**for that loop. - Check again the other for. It is also increasing serially so
**n**. - The third loop is also making
, but it is inside the second loop so it will contribute*n***n**.^{2}

**THEREFORE COMPLEXITY:**

**n+n ^{2 } (considering only the highest power of n).**

**ANSWER: n ^{2}**

Author: Udipto Goswami