KTU Online Placement Cell Registration

# Data Structures CS205 Note-Module 5

## Data Structures CS205 Note-Module 5

### DSA Fifth Module Syllabus

Graphs – representation of graphs, BFS and DFS (analysis not required)applications.Sorting techniques – Bubble sort, Selection Sort, Insertion sort,Merge sort, Quick sort, Heaps and Heap sort. Searching algorithms (Performance comparison expected. Detailed analysis not required)

### SORTING TECHNIQUES

Sorting method can be classified into two.
1)Internal Sorting
2)External Sorting
In internal sorting the data to be sorted is placed in main memory. In external sorting the data is placed in external memory such as hard disk, floppy disk etc. The internal sorting can be classified into
1)n^sorting
2)n log n sorting n^2
sorting - it can be classified into
1)Bubble sort
2) Selection sort
3) Insertion sort nlogn sorting - It can be classified into
1) Merge sort
2)Quick sort
3) Heap sort
Bubble sort
Bubblesort(a[],n)
Input- an array a[size], n is the no. of element currently present in array Output- Sorted array
DS- Array
Algorithm
1. Start2. i=03. While i<n-1   1. j=0   2. While j<n-1-i      1. If a[j]>a[j+1]         1. temp=a[j]         2. a[j]=a[j+1]         3. a[j+1]=temp      2. end if      3. j=j+1   3.end while   4.i=i+14. end while5.Stop
Here first element is compared with second element. If first one is greater than second element then swap each other. Then second element is compared with third element . If second element is greater than third element then perform swapping. This process is continued until the comparison of (n-1)th element with nth element. These process continues (n-1) times.
AnalysisHere during the first iteration n-1 comparisons are required. During the second iteration n-2 comparisons are required etc..during last iteration, 1 comparison is required.
Merge
Merge sort follows the strategy divide and conquer method. Here the given base array is divided into two sub lists. These 2 sub listsis again divided into 4 sub lists. The process is continued until subsists contain single element. Then repeatedly merge these two sub lists to a single sub list. So that a sorted array is created from sorted sub lists. The process continues until a sub list contains all the elements that are sorted.