Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.

com

Chapter 9- Data Structure - 1

Data Structure – Searching & Sorting

In this tutorial we will discuss the following topics
S. No. Topics
1 What is data structure?

2 Data type vs data structure

3 Different data structures

4 Linear list

5 Linear search

6 Binary search

7 Bubble sort

8 Insertion sort

Page 1 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

WHAT IS DATA STRUCTURE?

 In computer science data structures is a way of organizing and storing
the data in a computer so that it can be accessed and modified
efficiently.
 The main idea is to reduce the space and time complexities of different
tasks.
 A data structure has well-defined operations, behaviour and properties.

DATA TYPE VS DATA STRUCTURE

 All data structures are data types, but not all data types are data
structures.
 Data type is used so that compiler can understand the type of data
that will be stored in a variable and accordingly allocate memory block
for variable for example: int, float and string etc.
 Data Structures are efficient ways to store data, so that we can access
and manipulate data accordingly for example: list, stack and queue etc.

Page 2 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Different Data Structures:

DATA STUCTURE

SIMPLE DATA STRUCTIURE COMPOUND DATA STRUCTUERE

Array or Linear List Linear Non - Linear

Stack Tree

Queue Graph

Linked List

Linear List:
 A list is a data structure in Python that is a mutable, or changeable,
ordered sequence of elements.
 Lists are used to store data of different data types in a sequential
manner.
 Index of first item is 0 and the last item is n-1.Here n is number of
elements in a list.
Positive Index 0 1 2 3 4 5 6 7 8 9 10
Value 10 20 25 39 40 45 89 90 95 98 99
Negative Index -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1

Page 3 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

 Array can be Single Dimensional or Multidimensional. In Python arrays
are implemented through List data types as Linear List or through
NumPy arrays.
Creating a list

Its syntax is:

Variable name [index] (variable name is name of the list).
For Example:
To create an empty list, use a statement like
L1 = [ ]
To create a list that contains a sequence of values, separate the values
by commas inside square brackets ([ ])
L2 = [ 1, 2, 3 ]
To create a list that contains 3 string elements.
L3 = [“Delhi”, “Chennai”, “Mumbai”]
To create a list that contains different types of elements
L4 = [“abc”, 10, 20]
Adding Elements

Adding the elements in the list can be achieved using the append(),
extend() and insert() functions.
 The append() function adds all the elements passed to it as a single
element.
Page 4 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

 The extend() function adds the elements one-by-one into the list.
 The insert() function adds the element passed to the index value and
increase the size of the list too.
my_list = [1, 2, 3]
print(my_list)

#add a list [555, 12] as a single element

my_list.append([555, 12])
print(my_list)

#add a list ([234, 'more_example'])as different elements

my_list.extend([234, 'more_example'])
print(my_list)

#add element ‘insert_example’ at specified position 1

my_list.insert(1, 'insert_example')
print(my_list)

Output :
[1, 2, 3]
[1, 2, 3, [555, 12]]
[1, 2, 3, [555, 12], 234, ‘more_example’]
[1, ‘insert_example’, 2, 3, [555, 12], 234, ‘more_example’]

Page 5 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Deleting Elements
 To delete elements, use the del keyword which is built-in into Python
but this does not return anything back to us.
 If you want the element back, you use the pop() function which takes
the index value.
 To remove an element by its value, you use the remove() function.
my_lst = [10, 20, 30, 'example', 31.132, 1, 3]
# delete element at index 5

del my_lst[5]

print(my_lst)

# remove element with value

my_lst.remove('example')

print(my_lst)

# pop element from list

x = my_lst.pop(1)

print('Popped Element: ', x, ' List remaining: ', my_lst)

# empty the list

my_lst.clear()

print(my_lst)
Output:
[10, 20, 30, ‘example’, 31.132, 3]
[10, 20, 30, 31.132, 3]
Popped Element: 2 List remaining: [10, 30, 31.132, 3]
[]
Page 6 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Accessing Elements

Accessing elements is the same as accessing Strings in Python. You pass

the index values and hence can obtain the values as needed. Example:
my_lst = [10, 20, 30, 'example', 31.132, 1, 3]
#access elements one by one
for element in my_lst:
print(element)
#access all elements
print(my_lst)
#access index 3 element
print(my_lst[3])
#access elements from 0 to 1 and exclude 2
print(my_lst[0:2])
#access elements in reverse
print(my_lst[::-1])
Output:
10
20
30
example
31.132
1
3
[10, 20, 30, 'example', 31.132, 1, 3]
example
[10, 20]
[3, 1, 31.132, 'example', 30, 20, 10]

Page 7 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

SEARCHING: LINEAR AND BINARY SEARCHING
Linear Searching: each element of linear list is compared with the
given item to be searched one by one. This method traverse the linear list
sequentially to located the given item.
For Linear Searching item need not be in any order, it can be performed
on random list.

Benefits and Drawbacks

Linear Searching is suitable for small list only.
Best Case: when item to be search is at first position
Worst Case: when item to be search is at last position or not present
Average Case: when item is somewhere in list other than first or last
position.
Coding a Linear Search
Let's first develop an algorithm for performing a linear search. We will
then convert this into a Python script.
 Let's start with a list of numbers, say 10 of them
 First, we will ask for a number we think may be in the list. We will call
this variable ''srchItem''
 Also, we will set a flag variable called ''flag'' to false
 Now loop thru the entire list from start to end
- Compare the item at the current position in the list with ''srchItem''
Page 8 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

- If it matches then set ''flag'' to true and exit the loop, else move on
to the next position
 Otherwise, if we have searched the entire list, ''srchItem'' was not
found, so ''flag'' remains false

Page 9 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Binary Search
 The binary search algorithm can be used with only a sorted list of
elements.
 Binary search follows a divide and conquer methodology.
 It is faster than linear search but requires that the array be sorted
before the algorithm is executed.
 Assuming that we're searching for a value val in a sorted array, the
algorithm compares val to the value of the middle element of the
array, which we'll call mid.

-- The search process initiates by locating the middle element of the

sorted array of data.

-- After that, the key val is compared with the element.

-- If the key val is smaller than the middle element, then searches
analyses the upper values to the middle element for comparison and
matching.

-- In case the key val is greater than the middle element then searches
analyses the lower values to the middle element for comparison and
matching.

Page 10 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

A. You have a List of sorted values ranging from 3 to 30 and need to

locate 18.
B. The average of the lower and upper limits is (L + R) / 2 = 4. The value
being searched is greater than the mid which is 4.
C. The List values less than the mid are dropped from search and values
greater than the mid-value 4 are searched.
D. This is a recurrent dividing process until the actual item to be
searched is found.
Page 11 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Coding a Binary Search

Page 12 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Sorting
Sorting is the process of arranging a list of elements in a particular order
(Ascending or Descending).

Bubble Sort:
 The bubble sort makes multiple passes through a list.
 It compares adjacent items and exchanges those that are out of order.
 Each pass through the list places the next largest value in its proper
place.
 In essence, each item “bubbles” up to the location where it belongs.
Complexity :
The complexity of bubble sort is O(n2) in both worst and average cases,
because the entire array needs to be iterated for every element.

Page 13 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Coding a Bubble Sort

Page 14 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Insertion Sort:
In insertion sort algorithm, every iteration moves an element from
unsorted portion to sorted portion until all the elements are sorted in the
list.
Insertion sort is a simple sorting algorithm that works the way we sort
playing cards in our hands.
Step by Step Process
The insertion sort algorithm is performed using the following steps...

Step 1 − If it is the first element, it is

already sorted return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in
the sorted sub-list
Step 4 − Shift all the elements in the
sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted.

Page 15 of 16
Unit I: Computational Thinking and Programming - 2 Visit to website: learnpython4cbse.com

Chapter 9- Data Structure - 1

Page 16 of 16