Important Terminology

1. Sorting:The process gelementsin aspecific order, typically ascending or descending,

accordingtoa defined criterion such as numerical value or alphabetical order.
thatirepeatedly steps through the list, compares
simple sorting algorithmnthat
2 BubbleSSort:A adjacent
elements,andswaps them if they are in the wrong order, until the list is sorted.
.Caloction Sort:A sorting algorithm that divides the input list into two parts: a sorted sublist and an
unsortedisublist. It repeatedly selects the smallest (or largest) element from the unsorted sublist
and moves it to the end of the sorted subljist.
lncertion Sort: Asorting algorithm that builds the final sorted list one element at a time by
#eratively taking an element from the unsorted part of the list and inserting it into its correct
position in the sorted part of the list.
Time Complexity: Ameasure of the amount of time taken by an algorithm to run as a function of
the length ofthe input, typically expressed using big Onotation to describe the upper bound on the
runtime.
6 Best Case Time Complexity :The minimum amount of time required by an algorithm to ru
typically occurringwhen the input is already sorted or in afavorable configuration.
7. Worst Case Time Complexity: The maximum amount of time required by an
typically occurring when the input is in the least favorable configuration. algorithm to run,
&Average Case Time Complexity : The expected amount of time required by an
over all possible inputs, considering their probabilities of occurrence.
algorithm to run
9. BigO Notation :A mathematical notation used to describe the upper
bound or worst-case scenario
of the time complexity of an algorithm in terms of the input size.
10. Stable 5orting Algorithm : Asorting algorithm that preserves the relative order of equal elements
inthe sorted output, ensuring that elements with equal keys remain in the same order as they were
in the original input.
. Unstable Sorting Algorithm:A sorting algorithm that does not
necessarily preserve the relative
order of equal elements in the sorted output, potentially changing the order of equal elements from
the original input.
12. In-place
Sorting Algorithm:Asorting algorithm that sorts the elements of the input list by
earranging them within the list itself, without requiring additional memory space proportional to
the size of the
input.
 116 LAXMI COMPUTER SCIENCE WITH PYTHON (CLASS X) so

13. Out-of-place Sorting Algorithm: Asorting algorithmthat sorts the elements ofthe
additional memory spaceproportional to the size of the input. input ist y
creating a separate copy of the input list and rearrangingthe elements in the
copy.
14 Comparison-based Sorting Algorithm : Asorting algorithmthat sorts elements equiing
them painwise and making decisions based on the outcomes of by
one element is greater than, less than, or equal to another element.
15. Non-comparison-based Sorting Algorithm : Asorting algorithm that
co
these comparisons, suchàs:
mpar
wheti
h
sorts
ng
er
directly comparing them pairwise, often by exploiting specific properties offthe elements
auxiliary data structures. elementssorwiusthouing
16 Merge Sort: Adivide-and-conquer sorting algorithmthat recursively divides the
smaller sublists, sorts the sublists, and then merges them back together to input
produce list into
Output. the sorted
17. Quick Sort:A divide-and-conquer sorting algorithm that recursively partitionss
two sublists based on achosen pivot element, sorts the sublists, and then the input list intg
produce the sorted output. combines
,them to
18. Counting Sort: Anon-comparison-based sorting algorithmthat sorts elements
sby counting the
number of occurrences of each unique element andthen arranging themin order
counts. based ontheir
19. Radix Sort: Anon-comparison-based sorting algorithmthat sorts elementssby first
byindividual digits or other significarnt positions, then sortingthe elements by eachgroupi
digit
ng them
sequentially. posaition
20. Heap Sort:A comparison-based sorting algorithm that builds a binary heap from the
inputlit ana
repeatedly extracts the maximum (or minimum)element from the heap to produce the sorad
output.

Objective Type Questions

Multiple Choice Questions
1. What is the primary goal of sorting algorithms?
(a) To rearrange elements in a random order (b) To arrange elements in a specific order
(c) Todelete elements from a list (d) To create a new list
2. Which of the following sorting algorithms repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order?
(a Bubble sort (b) Selection sort
(c) Insertion sort (d) Merge sort
3. Which sorting algorithm involves repeatedly selecting the minimum element from the
unsorted portion of the array and placing it at the beginning?
(a) Bubble sort: (b) Selection sort
(c) Insertion sort (d) Quick sort
4. What is the time complexity of bubble sort in the worst-case scenario?
(a) On log n) (b) O(n)
(c) O(n)
(d) O(logn)
5.
Which sorting algorithm works by repeatedly selecting the next smallest elementfromthe
unsorted portion of the array and placing it at the correct position?
(a) Bubble sort
(b) Selection sort
(c) Insertion sort
6. (d) Quick sort
What is the time complexity of selection sort in the worst-case scenario
(a) O(n log n)
(c) O(n) (b) O(n)
(d) O(log n)
 COMPUTER SCIENCE WITH PYTHON (CLASS-XII) 117

Which sorting algorithm works by building asorted subarray one element at atime by
7 repeatedly removing elements from the unsorted portion of the array and inserting them
position?
intotheir correct
(a) Bubblesort (b) Selection sort
(c) Insertion sort (d) Merge sort
What isthe time complexity of insertion sort in the worst-case scenario?
8 (b) O(n)
(a) O(n log n) (d) O(log n)
(c) O(n)
Which of the following sorting algorith ms is known for its simplicity and ease of
9 implementation but is inefficient on large lists?
(a) Bubble sort (b) Selection sort
(c) Insertion sort (d) Merge sort
a6 What is the timne complexity of merge sort in the worst-case scenario?
O(n log n) (b) O(n)
(a)
O(n) (d) Ollog n)
(c) complexity in the worst-case scenario among the
4 Which sorting algorithm has the best time
ones mentioned?
(a) Bubble sort (b) Selection sort
(c) Insertion sort
(d Merge sort
compared to other sorting algorithms?
12. What is the primary disadvantage of bubble sort
(b) Itrequires additional memory space
(a) Ithas a higher time complexity
(c) Itis not stable (d) Itis not suitable for large datasets
in the average case as well as
13. Which sorting algorithm exhibits quadratic time complexity
in the worst case?
(b) Selection sort
(a) Bubble sort
(c) Insertion sort (d) Merge sort
sort over bubble sort?
14. What is the primary advantage of selection
(a) Selection sort is more stable
datasets
(b) Selection sort is more efficient for small
(c) Selection sort requires less memory space
(d) Selection sort is easier to implement
complexity of sorting algorithms is true?
15. Which of the following statements about the time
(a) All sorting algorithms have the same time complexity size
solely on the input
(b) The time complexity of sorting algorithms depends always more efficient
(c) Sorting algorithms with higher time complexity arebased on the algorithm used and the nature
(d) The time complexity of sortingalgorithms can vary
of the input data
Answer
4 (c) 5 (c)
1. (b) 2. (a) 3. (b)
8 (c) 9. (a) 10. (a)
6. (c) 7. (c)
11. (d) 13. (c) 14. (b) 15. (d)
12. (a)

Fill in the Blanks

1. Sorting algorithms are used to elements in a specific order.
bubble sort is based on the principle of repeatedly comparing adjacent elements and
2

them if they are in the wrong order.

3 element from the unsorted portion of the array and
Selection sort involves finding the
moving it to the beginning.
 (CLASS-XII)
118 LAXMI COMPUTER SCIENCE WITH PYTHON
Insertion sort builds a sorted subarray by
iteratively elements into their
4.

cor ectpositr
inthe worst-case scenario.
5 The time complexity of bubble sort is in the Worst-case scenario.
Selection sort has a time complexity of worst-caseScenario is
complexity in the
7. In insertion sort, the time
its efficiency, has a time complexity of in the
8.

10.
Merge sort, known
Quicksort,
for
another efficient sorting algorithm, has an average-case time complexity of
In timecomplexity analysis, "n" represents
provides
the
an
of elements in the
estimate of its
input. WOrst-case scenar.
11. The time complexity of an algorithm
expressed using
asthe input size
12. The time complexity of an algorithm is often based on its and the notation. increase
13. The time complexity of an algorithm can vary nature of
14. Understanding the time complexity of algorithms is essential for evaluating thot the input da:
performance.
determine its
15. The time complexity of an algorithm can beanalyzed to
Answer efficiency.
minimum or smallest, 4.
1. arrange or order, 2. swapping or exchanging, 3.
5. O(n²) 6. O(n), 7. O(n?), 8. O(n log n), 9. O(n log n), 10.number, 11. inserting or or placing
performance
12. Big O, 13. implementation, 14. correctness, 15. computational ef i cieng,
True/False
1. Bubble sort is an efficient sorting algorithm suitable for sorting large datasets.
2 Selection sort and insertion sort are examples of comparison-based sorting algorithms
3 The time complexity of bubble sort is O(n log n) in the vworst-case scenario.
4 In selection sort, the element with the maximum value is placed at the beginning of the arra.
5. Insertion sort works by repeatedly swapping adjacent elements until the array is sorted.
6. The time complexity of insertion sort is O(n²) in the worst-case scenario.
7. Merge sort is an example of an in-place sorting algorithm.
8 Quick sort has a time complexity of O(n') in the average case.
9
Time complexity analysis is used to evaluate the efficiency of algorithms in terms of their executin
10. The time complexity of an algorithm remains constant regardless of the input size.
11. Big Onotation is commonly used to express the upper bound of an algorithm's time complexity,
12. The time complexity of an algorithm is unaffected by factors such as the programming languageu
for implementation.
13. Selection sort is more efficient than merge sort for sorting large datasets.
14. Insertionsort isparticularly efficient for nearly sorted or small datasets.
15. The efficiency of sorting algorithms can vary depending|on the characteristics offthe inputdata.

Answer
False
1. False, 2. True, 3. False, 4. True, 5. False 6. True, 7. 11.TTrue, 12.
False, 8. False, 9. True, 10. False,
13. False, 14.True, 15.True

Assertion-Reason reason.Chos
Statement of
Directions:In the following question, astatement of.assertion is followed by a:
the correct choice as: assertio
explanationofthe
oftheasserte
(a) Both assertion and reason are true, and the reason isthe correct
explanation
(b) Both assertion and reasonare true, and the reason
r is the incorrect
(c) Assertion is true, but the reason is false.
(d) Assertion is false, but the reason is true.
(e) Both Assertion and Reason are false.
 COMPUTER SCIENCE WITH PYTHON (CLASS-X) 119
Assertion: Bubble sort is an efficient sorting algorithm suitablefor large datasets.
1
Reason:8Bubble sort has atime complexity of O(n log n) in the worst-case scenario.
Assertion: Selection sort andinsertion sort are both comparison-based sorting
2. Reason: These algorithms sort elements by comparing them with each otheralgorithms.
to determine their
relativeorder.
Assertion: The time complexity of insertion sort is O(n^2) in the worst-case scenario.
involves s nested iterations over the elements of the
3 Reason:1Insertion sort array, leading to quadratic
time complexity.
Assertion: Merge sort is an in-place sorting algorithm.
ASSAMerge sort requires additional memory space proportional to the size of the input array for its
operations.
Assertion: Time complexity analysis provides
insights into the efficiency of algorithms based on their
5.
execution time.
e n Time complexity analysis focuses on determining the worst-case
size. performance of algorithms
in terms of the input
Answer

1. (c) 2. (a) 3. (a) 4. (e) 5. (a)