DEPARTMENT OF

COMPUTER SCIENCE &

ENGINEERING

Subject Name Basic Data Structure

Subject Code 25CSH-103
Semester 1
Mapping With Co’s CO2, CO3

LESSON-4 Introduction to Data Structures

LESSON OBJECTIVES–

 To learn types of Data structure

 To learn application of data Structure

STRUCTURE OF THE LESSON

 Introduction to Sorting
 Types of Sorting Techniques
 References
 FAQs
 Discussion forum

Introduction to Sorting
Sorting is nothing but storage of data in sorted order, it can be in ascending or descending
order. The term Sorting comes into picture with the term Searching. There are so many things
in our real life that we need to search, like a particular record in database, roll numbers in merit
list, a particular telephone number, any particular page in a book etc.
Sorting arranges data in a sequence which makes searching easier. Every record which is going
to be sorted will contain one key. Based on the key the record will be sorted. For example,
suppose we have a record of students, every such record will have the following data:

 Roll No.

 Name

 Age

 Class
Here Student roll no. can be taken as key for sorting the records in ascending or descending
order. Now suppose we have to search a Student with roll no. 15, we don't need to search the
complete record we will simply search between the Students with roll no. 10 to 20.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Sorting Efficiency
There are many techniques for sorting. Implementation of particular sorting technique depends
upon situation. Sorting techniques mainly depends on two parameters. First parameter is the
execution time of program, which means time taken for execution of program. Second is the
space, which means space taken by the program.

Types of Sorting Techniques

There are many types of Sorting techniques, differentiated by their efficiency and space
requirements. Following are some sorting techniques which we will be covering in next
sections.

1. Bubble Sort

2. Insertion Sort

3. Selection Sort

4. Quick Sort

5. Merge Sort

6. Heap Sort

Bubble Sorting
Bubble Sort is an algorithm which is used to sort N elements that are given in a memory for eg:
an Array withN number of elements. Bubble Sort compares all the element one by one and sort
them based on their values.
It is called Bubble sort, because with each iteration the smaller element in the list bubbles up
towards the first place, just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the data items one-by-one in pairs and comparing
adjacent data items and swapping each pair that is out of order.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Sorting using Bubble Sort Algorithm

Let's consider an array with values {5, 1, 6, 2, 4, 3}
int a[6] = {5, 1, 6, 2, 4, 3};
int i, j, temp;
for(i=0; i<6; i++)
{
for(j=0; j<6-i-1; j++)
{
if( a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
//now you can print the sorted array after this
Above is the algorithm, to sort an array using Bubble Sort. Although the above logic will sort
and unsorted array, still the above algorithm isn't efficient and can be enhanced further.
Because as per the above logic, the for loop will keep going for six iterations even if the array
gets sorted after the second iteration.
Hence we can insert a flag and can keep checking whether swapping of elements is taking place
or not. If no swapping is taking place that means the array is sorted and wew can jump out of
the for loop.
int a[6] = {5, 1, 6, 2, 4, 3};
int i, j, temp;
for(i=0; i<6; i++)
{
intflag = 0; //taking a flag variable
for(j=0; j<6-i-1; j++)
{
if( a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = 1; //setting flag as 1, if swapping occurs
}
}
if(!flag) //breaking out of for loop if no swapping takes place
{
break;
}
}
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING
In the above code, if in a complete single cycle of j iteration(inner for loop), no swapping takes
place, and flag remains 0, then we will break out of the for loops, because the array has already
been sorted.

Complexity Analysis of Bubble Sorting

In Bubble Sort, n-1 comparisons will be done in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and
so on. So the total number of comparisons will be
(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n2)
Hence the complexity of Bubble Sort is O(n2).
The main advantage of Bubble Sort is the simplicity of the [Link] complexity for
Bubble Sort is O(1), because only single additional memory space is required for temp variable
Best-case Time Complexity will be O(n), it is when the list is already sorted.

Insertion Sorting
It is a simple Sorting algorithm which sorts the array by shifting elements one by one.
Following are some of the important characteristics of Insertion Sort.

1. It has one of the simplest implementation

2. It is efficient for smaller data sets, but very inefficient for larger lists.

3. Insertion Sort is adaptive, that means it reduces its total number of steps if given a

partially sorted list, hence it increases its efficiency.

4. It is better than Selection Sort and Bubble Sort algorithms.

5. Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single

additional memory space.

6. It is Stable, as it does not change the relative order of elements with equal keys
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

How Insertion Sorting Works

Sorting using Insertion Sort Algorithm

int a[6] = {5, 1, 6, 2, 4, 3};
int i, j, key;
for(i=1; i<6; i++)
{
key = a[i];
j = i-1;
while(j>=0 && key < a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
Now lets, understand the above simple insertion sort algorithm. We took an array with 6
integers. We took a variable key, in which we put each element of the array, in each pass,
starting from the second element, that is a[1].
Then using the while loop, we iterate, until j becomes equal to zero or we find an element
which is greater than key, and then we insert the key at that position.
In the above array, first we pick 1 as key, we compare it with 5(element before 1), 1 is smaller
than 5, we shift 1 before 5. Then we pick 6, and compare it with 5 and 1, no shifting this time.
Then 2 becomes the key and is compared with, 6 and 5, and then 2 is placed after 1. And this
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

goes on, until complete array gets sorted.

Insertion Sorting in C++

#include <cstdlib>
#include <iostream>

using namespace std;

//member functions declaration

voidinsertionSort(int arr[], int length);
voidprintArray(int array[],int size);

intmain() {
int array[5]= {5,4,3,2,1};
insertionSort(array,5);
return 0;
}

voidinsertionSort(int arr[], int length) {

int i, j ,tmp;
for (i = 1; i< length; i++) {
j = i;
while (j > 0 &&arr[j - 1] >arr[j]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
j--;
}
printArray(arr,5);
}
}

voidprintArray(int array[], int size){

cout<< "Sorting tha array using Insertion sort... ";
int j;
for (j=0; j <size;j++)
for (j=0; j <size;j++)
cout<<" "<< array[j];
cout<<endl;
}
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Complexity Analysis of Insertion Sorting

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n)
Average Time Complexity : O(n2)
Space Complexity : O(1)

Selection Sorting
Selection sorting is conceptually the most simplest sorting algorithm. This algorithm first finds
the smallest element in the array and exchanges it with the element in the first position, then
find the second smallest element and exchange it with the element in the second position, and
continues in this way until the entire array is sorted.

How Selection Sorting Works

In the first pass, the smallest element found is 1, so it is placed at the first position, then leaving
first element, smallest element is searched from the rest of the elements, 3 is the smallest, so it
is then placed at the second position. Then we leave 1 nad 3, from the rest of the elements, we
search for the smallest and put it at third position and keep doing this, until array is sorted.

Sorting using Selection Sort Algorithm

void selectionSort(int a[], int size)
{
int i, j, min, temp;
for(i=0; i< size-1; i++ )
{
min = i; //setting min as i
for(j=i+1; j < size; j++)
 DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

{
if(a[j] < a[min]) //if element at j is less than element at min position
{
min = j; //then set min as j
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}

Complexity Analysis of Selection Sorting

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n2)
Average Time Complexity : O(n2)
Space Complexity : O(1)

Quick Sort Algorithm

Quick Sort, as the name suggests, sorts any list very quickly. Quick sort is not stable search, but
it is very fast and requires very less aditional space. It is based on the rule of Divide and
Conquer(also called partition-exchange sort). This algorithm divides the list into three main
parts :

1. Elements less than the Pivot element

2. Pivot element

3. Elements greater than the pivot element

In the list of elements, mentioned in below example, we have taken 25 as pivot. So after the
first pass, the list will be changed like this.
6 8 17 14 25 63 37 52
Hnece after the first pass, pivot will be set at its position, with all the elements smaller to it on
its left and all the elements larger than it on the right. Now 6 8 17 14 and 63 37 52 are
considered as two separate lists, and same logic is applied on them, and we keep doing this
until the complete list is sorted.
 DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

How Quick Sorting Works

Sorting using Quick Sort Algorithm

/* a[] is the array, p is starting index, that is 0,
and r is the last index of array. */

voidquicksort(int a[], int p, int r)

{
if(p < r)
{
int q;
q = partition(a, p, r);
quicksort(a, p, q);
quicksort(a, q+1, r);
}
}
intpartition(int a[], int p, int r)
{
int i, j, pivot, temp;
pivot = a[p];
i = p;
j = r;
while(1)
{
while(a[i] < pivot && a[i] != pivot)
i++;
while(a[j] > pivot && a[j] != pivot)
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

j--;
if(i< j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
else
{
return j;
}
}
}

Complexity Analysis of Quick Sort

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n log n)

 Space required by quick sort is very less, only O(n log n) additional space is required.

 Quick sort is not a stable sorting technique, so it might change the occurence of two

similar elements in the list while sorting.

Merge Sort Algorithm

Merge Sort follows the rule of Divide and Conquer. But it doesn't divides the list into two
halves. In merge sort the unsorted list is divided into N sublists, each having one element,
because a list of one element is considered sorted. Then, it repeatedly merge these sublists, to
produce new sorted sublists, and at lasts one sorted list is produced.
Merge Sort is quite fast, and has a time complexity of O(n log n). It is also a stable sort, which
means the "equal" elements are ordered in the same order in the sorted list.
 DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

How Merge Sort Works

Like we can see in the above example, merge sort first breaks the unsorted list into sorted
sublists, and then keep merging these sublists, to finlly get the complete sorted list.

Sorting using Merge Sort Algorithm

/* a[] is the array, p is starting index, that is 0,
and r is the last index of array. */

Lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.

voidmergesort(int a[], int p, int r)

{
int q;
if(p < r)
{
q = floor( (p+r) / 2);
mergesort(a, p, q);
mergesort(a, q+1, r);
merge(a, p, q, r);
}
}

voidmerge(int a[], int p, int q, int r)

{
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

int b[5]; //same size of a[]

int i, j, k;
k = 0;
i = p;
j = q+1;
while(i<= q && j <= r)
{
if(a[i] < a[j])
{
b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}

while(i<= q)
{
b[k++] = a[i++];
}

while(j <= r)
{
b[k++] = a[j++];
}

for(i=r; i>= p; i--)

{
a[i] = b[--k]; // copying back the sorted list to a[]
}

Complexity Analysis of Merge Sort

Worst Case Time Complexity : O(n log n)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n)

 Time complexity of Merge Sort is O(n Log n) in all 3 cases (worst, average and best) as

merge sort always divides the array in two halves and take linear time to merge two halves.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

 It requires equal amount of additional space as the unsorted list. Hence its not at all

recommended for searching large unsorted lists.

 It is the best Sorting technique for sorting Linked Lists.

Heap Sort Algorithm

Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case
scenarios. Heap sort algorithm is divided into two basic parts :

 Creating a Heap of the unsorted list.

 Then a sorted array is created by repeatedly removing the largest/smallest element from

the heap, and inserting it into the array. The heap is reconstructed after each removal.

What is a Heap ?
Heap is a special tree-based data structure, that satisfies the following special heap properties :

1. Shape Property : Heap data structure is always a Complete Binary Tree, which means

all levels of the tree are fully filled.

2. Heap Property : All nodes are either [greater than or equal to] or [less than or equal

to] each of its children. If the parent nodes are greater than their children, heap is called

a Max-Heap, and if the parent nodes are smalled than their child nodes, heap is called Min-

Heap.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

How Heap Sort Works

Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data
structure(Max-Heap or Min-Heap). Once heap is built, the first element of the Heap is either
largest or smallest(depending upon Max-Heap or Min-Heap), so we put the first element of the
heap in our array. Then we again make heap using the remaining elements, to again pick the
first element of the heap and put it into the array. We keep on doing the same repeatedly untill
we have the complete sorted list in our array.
In the below algorithm, initially heapsort() function is called, which calls buildheap() to build
heap, which inturn uses satisfyheap() to build the heap.

Sorting using Heap Sort Algorithm

/* Below program is written in C++ language */

void heapsort(int[], int);

void buildheap(int [], int);
void satisfyheap(int [], int, int);

void main()
{
int a[10], i, size;
cout<< "Enter size of list"; // less than 10, because max size of array is 10
cin>> size;
cout<< "Enter" << size << "elements";
for( i=0; i< size; i++)
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

{
cin>> a[i];
}
heapsort(a, size);
getch();
}

voidheapsort(int a[], int length)

{
buildheap(a, length);
int heapsize, i, temp;
heapsize = length - 1;
for( i=heapsize; i>= 0; i--)
{
temp = a[0];
a[0] = a[heapsize];
a[heapsize] = temp;
heapsize--;
satisfyheap(a, 0, heapsize);
}
for( i=0; i< length; i++)
{
cout<< "\t" << a[i];
}
}

voidbuildheap(int a[], int length)

{
int i, heapsize;
heapsize = length - 1;
for( i=(length/2); i>= 0; i--)
{
satisfyheap(a, i, heapsize);
}
}
voidsatisfyheap(int a[], int i, int heapsize)
{
int l, r, largest, temp;
l = 2*i;
r = 2*i + 1;
if(l <= heapsize&& a[l] > a[i])
{
largest = l;
}
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

else
{
largest = i;
}
if( r<= heapsize&& a[r] > a[largest])
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
satisfyheap(a, largest, heapsize);
}
}

Complexity Analysis of Heap Sort

Worst Case Time Complexity : O(n log n)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n)

 Heap sort is not a Stable sort, and requires a constant space for sorting a list.

 Heap Sort is very fast and is widely used for sorting.

Searching Algorithms on Array

Before studying searching algorithms on array we should know what is an algorithm?
An algorithm is a step-by-step procedure or method for solving a problem by a computer in a
given number of steps. The steps of an algorithm may include repetition depending upon the
problem for which the algorithm is being developed. The algorithm is written in human
readable and understandable form. To search an element in a given array, it can be done in two
ways Linear search and Binary search.

Linear Search
A linear search is the basic and simple search algorithm. A linear search searches an element or
value from an array till the desired element or value is not found and it searches in a sequence
order. It compares the element with all the other elements given in the list and if the element is
matched it returns the value index else it return -1. Linear Search is applied on the unsorted or
unordered list when there are fewer elements in a list.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Example with Implementation

To search the element 5 it will go step by step in a sequence order.

functionfindIndex(values, target)
{
for(var i = 0; i<[Link]; ++i)
{
if (values[i] == target)
{
return i;
}
}
return -1;
}
//call the function findIndex with array and number to be searched
findIndex([ 8 , 2 , 6 , 3 , 5 ] , 5) ;

Binary Search
Binary Search is applied on the sorted array or list. In binary search, we first compare the value
with the elements in the middle position of the array. If the value is matched, then we return the
value. If the value is less than the middle element, then it must lie in the lower half of the array
and if it's greater than the element then it must lie in the upper half of the array. We repeat this
procedure on the lower (or upper) half of the array. Binary Search is useful when there are large
numbers of elements in an array.

Example with Implementation

To search an element 13 from the sorted array or list.
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

function findIndex(values, target)

{
returnbinarySearch(values, target, 0, [Link] - 1);
};

function binarySearch(values, target, start, end) {

if (start > end) { return -1; } //does not exist

var middle = [Link]((start + end) / 2);

var value = values[middle];

if (value > target) { returnbinarySearch(values, target, start, middle-1); }

if (value < target) { returnbinarySearch(values, target, middle+1, end); }
return middle; //found!
}

findIndex([2, 4, 7, 9, 13, 15], 13);

In the above program logic, we are first comparing the middle number of the list, with the
target, if it matches we return. If it doesn't, we see whether the middle number is greater than or
smaller than the target.
If the Middle number is greater than the Target, we start the binary search again, but this time
on the left half of the list, that is from the start of the list to the middle, not beyond that.
If the Middle number is smaller than the Target, we start the binary search again, but on the
right half of the list, that is from the middle of the list to the end of the list.
 DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Position of Top Status of Stack

-1 Stack is Empty

0 Only one element in Stack

N-1 Stack is Full

N Overflow state of Stack

FAQ

Q1. Why do we study Bubble Sort if it is slow?

→ It teaches the basics of comparison, swapping, loops, optimization.

Q2. When should Bubble Sort be used?

→ For small or almost-sorted datasets.

Q3. Is Bubble Sort stable?

→ Yes, it preserves the order of equal elements.

Q4. Why is sorting important?

→ It reduces complexity of further operations like searching.

Q5. Can Bubble Sort be optimized?

→ Yes, by stopping early if no swaps happen in a pass.

DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING

Coursera Courses

• Data Structures – University of California San Diego

[Link]

• Algorithms & Data Structures – Princeton University

[Link]

• Data Structures in C – Duke University

[Link]
DEPARTMENT OF
COMPUTER SCIENCE &
ENGINEERING