Data Structures CS205 Note-Module 5

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 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^2 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. Start

2. i=0

3. 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+1

4. end while

5.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.

Analysis

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

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.

Download Full pdf