CS205 Data Structures
Fifth Module Full Note
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 method can be classified into two.
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
2)n log n sorting n^2
sorting - it can be classified into
2) Selection sort
3) Insertion sort nlogn sorting - It can be classified into
1) Merge sort
3) Heap sort
Input- an array a[size], n is the no. of element currently present in array Output- Sorted array
3. While i<n-1
2. While j<n-1-i
1. If a[j]>a[j+1]
2. end if
4. end while
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.
Here 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 sort follows the strategy divide and conquer method. Here the given base array is divided into two sub lists. These 2 sub lists is 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.