Data Structure
SUBJECT CODE-ACIC10
(III SEM)
(IARE- UG20)
By
Ms. N.Venkata Sireesha
MODULE –I
INTRODUCTION TO DATA STRUCTURES, SEARCHING AND
SORTING (09) Basic concepts: Introduction to data structures,
classification of data structures, operations on data structures; Algorithm
Specification, Recursive algorithms, Data Abstraction, Performance
analysis- time complexity and space complexity, Asymptotic Notation-Big
O, Omega, and Theta notations. Introduction to Linear and Non Linear data
structures, Searching techniques: Linear and Binary search; Sorting
techniques: Bubble, Selection, Insertion, Quick and Merge Sort and
comparison of sorting algorithms.
3
Merge Sort
Merge sort is based on Divide and conquer method. It takes the list to
be sorted and divide it in half to create two unsorted lists. The two
unsorted lists are then sorted and merged to get a sorted list. The two
unsorted lists are sorted by continually calling the merge-sort
algorithm; we eventually get a list of size 1 (One) which is already
sorted. The two lists of size 1 (One) are then merged.
Merge Sort Procedure:
1. Divide the input which we have to sort into two parts in the
middle. Call it the left part and right part.
2. Sort each of them separately. Note that here sort does not mean to
sort it using some other method. We use the same function
recursively.
3. Then merge the two sorted parts.
4
Merge Sort
5
Merge Sort
MergeSort() function:
It takes the array, left-most and right-most index of the array to be
sorted as arguments.
Middle index (mid) of the array is calculated as (left + right)/2.
Check if (left<right) cause we have to sort only when left<right
because when left=right it is anyhow sorted.
Sort the left part by calling MergeSort() function again over the left
part MergeSort(array,left,mid) and the right part by recursive call
of MergeSort function as MergeSort(array, mid + 1, right). Lastly
merge the two arrays using the Merge function
6
Merge Sort
Merge() function:
It takes the array, left-most , middle and right-most index of the array to be merged as
arguments.
Finally copy back the sorted array to the original array.
7
Merge Sort Algorithm
MergeSort() function:
It takes the array, left-most and right-most index of the array to be
sorted as arguments.
Middle index (mid) of the array is calculated as (left + right)/2.
Check if (left<right) cause we have to sort only when left<right
because when left=right it is anyhow sorted.
Sort the left part by calling MergeSort() function again over the left
part MergeSort(array,left,mid) and the right part by recursive call of
MergeSort function as MergeSort(array, mid + 1, right). Lastly
merge the two arrays using the Merge function.
8
Merge Sort Algorithm
Merge() function:
It takes the array, left-most , middle and right-most index of the
array to be merged as arguments.
Finally copy back the sorted array to the original array.
9
Merge Sort Algorithm
MergeSort(arr[], l, r)
If l < r:
1. Find the middle point to divide the array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for first half: Call mergeSort(arr, l, m)
3. Call mergeSort for second half: Call mergeSort(arr, m+1,
r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
10
Merge Sort
Worst Case Performance O(n log2 n)
Best Case Performance(nearly) O(n log2 n)
Average Case Performance O(n log2 n)
11
Quick Sort
# Recursive call on the left of pivot
quickSort(array, low, pi - 1)
# Recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
12
Quick Sort
Unsorted Array [1, 7, 4, 1, 10, 9, -2]
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10]
13
