## Data Structures Notes

Data Structures Basic

Stacks

Queues

Linked List

Sorting

Tree

Graphs

Hashing and Searching

# Heading

Q

1

Explain Bubble Sort Algorithm and its complexity?

Ans

In bubble sort algorithm the array of n elements is sorted by comparing the elements one by one.Array can be sorted in either ascending or descending order.

Algorithm:

To sort array of n elements in ascending order first compare the 1st element with the 2nd .

If first element > second one

swap them

else

keep them as it is.

Now compare the 2nd and 3rd elements and check if it is needed to swap them.

Stop this when the greatest element is at the last.

If there are n elements in an array ,unsorted array will be converted into the sorted array by repeating the above process for n-1 times.

Program for bubble sort:

#include<stdio.h>

int main()

{

int n,i,j,val,t;

printf("Enter the no. of elements in array:\t");

scanf("%d",&n);

int arr[n];

printf("Enter the array elemets: \n");

for(j=0;j<n;j++)

{

scanf("%d",&arr[j]);

}

for(i=0;i<n;i++)

{

for(j=0;j<n-i-1;j++)

{

if(arr[j]>arr[j+1])

{

t=arr[j];

arr[j]=arr[j+1];

arr[j+1]=t;

}

}

}

printf("Sorted array list: \n");

for(i=0;i<n;i++)

{

printf("%d\n",arr[i]);

}

}

Pseudo code for bubble sort in c:

procedure bubbleSort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:

swapped = false

for j = 0 to loop-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then

/* swap them */

swap( list[j], list[j+1] )

swapped = true

end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break

end if

end for

end procedure return list

In bubble sort in first pass we need n-1 comparisons,in 2nd pass we need n-2,in 3rd n-3 comparisons,so the total number of comparisons are

(n-1)+(n-2)+(n-3)+……+2+1=n*(n-1)/2

So the time complexity of bubble sort algorithm is O(n**2)

Worst case time complexity:O(n**2)

Average case time complexity:O(n**2)

Best case time complexity:O(n)

So,this is how bubble sort works and above mentioned are the time complexities of it.

Notes : 1> Don’t write as second person or as 3rd person.

2> Try to write pseudo code instead of long paragraph to explain the code

3> Add answers in format as if you are answering a question in your exams.

Q

2

Explain Insertion Sort Algorithm and its complexity?

Ans

In Insertion sort:

Compare the current element with the elements before it i.e. predecessors.

If (current element < its predecessors)

move to it’s appropriate position.

else

Assume current position is correct for it and move to the next element.

In insertion sort as we start sorting we divide array into two parts i.e. sorted and unsorted.We assume that the first element is by default sorted.

Program for insertion sort:

#include<stdio.h>

int main()

{

int n,i,j,c,d,t;

printf("Enter the no. of elements in array: ");

scanf("%d",&n);

int arr[n];

printf("Enter the array elemets: \n");

for(j=0;j<n;j++)

{

scanf("%d",&arr[j]);

}

for(c=1;c<n;c++)

{

d=c;

while(d>0 && arr[d]<arr[d-1])

{

t=arr[d];

arr[d]=arr[d-1];

arr[d-1]=t;

d--;

}

}

printf("Sorted list:\n");

for(i=0;i<n;i++)

printf("%d\n",arr[i]);

}

Pseudo code for insertion sort:

procedure insertionSort( A : array of items )

int holePosition

int valueToInsert

for i = 1 to length(A) inclusive do:

/* select value to be inserted */

valueToInsert = A[i]

holePosition = i

/*locate hole position for the element to be inserted */

while holePosition > 0 and A[holePosition-1] > valueToInsert do:

A[holePosition] = A[holePosition-1]

holePosition = holePosition -1

end while

/* insert the number at hole position */

A[holePosition] = valueToInsert

end for

end procedure

Say an array to be sorted is given as:

2, 5, 1a, 9, 20, 3, 7, 12, 1b

Now insertion sort works as:

Insert element one by one in the correct place. That is:

1. Insert 2. Array=2, 5, 1a, 9, 20, 3, 7, 12, 1b

2. Insert 5. Array=2, 5, 1a, 9, 20, 3, 7, 12, 1b

3. Insert 1. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b

4. Insert 9. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b

5. Insert 20. Array=1a, 2, 5, 9, 20, 3, 7, 12, 1b

6. Insert 3. Array=1a, 2, 3, 5, 9, 20, 7, 12, 1b

7. Insert 7. Array=1a, 2, 3, 5, 7, 9, 20, 12, 1b

8. Insert 12. Array=1a, 2, 3, 5, 7, 9, 12, 20, 1b

9. Insert 1. Array =1a, 1b, 2, 3, 5, 7, 9, 12, 20

Note now the array is sorted.

Insertion sort is inplace and stable sorting technique.

Best case TC=O(1)

Since, at each insertion, max possible compparisons is n, its worst case TC=O(n2).

Average case TC will be same as worst case.

Notes : 1> Don’t write as second person or as 3rd person.

2> Try to write pseudo code for better explanation.

3> Add time complexities.

Q

3

Explain Merge Sort Algorithm and its complexity?

Ans

In merge sort the unsorted array is divided into two subarrays.Keep dividing the arrays until the subarray contains single element in it.After dividing arrays now merge the subarrays with single elements.While merging if elements from two smaller subarrays are not sorted first sort them and then merge. Keep merging until a array contains all elements in sorted order.

Pseudo code for merge sort:

PROCEDURE function mergeSort

FOR each element of the master list indexed by i

if ( i <= 1 ) return a

var left = a[0] to a[i/2]

var right = a[i/2+1] to a[i]

left = mergeSort( left )

right = mergeSort( right )

return merge( left,right )

END FOR

END PROCEDURE

PROCEDURE function mergeSort

WHILE length(left) > 0 and length(right) > 0

if first(left) â‰¤ first(right)

append first(left) to result

left = rest(left)

else

append first(right) to result

right = rest(right)

IF length(left) > 0

append left to result

END IF

IF length(right) > 0

append right to result

END IF

return result

END PROCEDURE

Average case ,best case and worst case time complexity for merge sort are all same i.e.

O(n*log n).This is all about merge sort.

Notes : 1>. Add pseudo code for better explanation.

2> Add answer as if you are answering in your exams.

3> Don't write as 2nd or third person.

Q

4

Explain Selection Sort Algorithm and its complexity?

Ans

In selection sort first find the smallest number in unsorted array and place it in the first place or swap the positions of smallest number and first place. Repeat for second smallest number and continue till the array is sorted.

Following is the example of selection sort that how it works.

Program for selection sort :

#include <stdio.h>

int main()

{

int a[100], n, i, j, position, swap;

printf("Enter number of elementsn");

scanf("%d", &n);

printf("Enter %d Numbersn", n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);

for(i = 0; i < n - 1; i++)

{

position=i;

for(j = i + 1; j < n; j++)

{

if(a[position] > a[j])

position=j;

}

if(position != i)

{

swap=a[i];

a[i]=a[position];

a[position=swap;

}

}

printf("Sorted Array:n");

for(i = 0; i < n; i++)

printf("%dn", a[i]);

return 0;

}

Pseudo code for selection sort:

procedure selection sort

list : array of items

n : size of list

for i = 1 to n - 1

/* set current element as minimum*/

min = i

/* check the element to be minimum */

for j = i+1 to n

if list[j] < list[min] then

min = j;

end if

end for

/* swap the minimum element with the current element*/

if indexMin != i then

swap list[min] and list[i]

end if

end for

end procedure

As in above program there are two for loops which are nested hence the Best,Worst and Average case time complexity for selection sort is O(n**2).Selection sort is the simplest sorting algorithm.So,this is all about selection sort.

Notes : 1>. Add pseudo code for better explanation.

2> Add answer as if you are answering in your exams.

3> Don't write as 2nd or third person.

Q

5

Explain Quick Sort Algorithm and its complexity?

Ans

In quick sort sort a array by taking help of pivot.Here pivot considered as the array element with the highest index.By comparing pivot with the other elements of array divide array into two parts one which have smaller values than pivot and one which have higher values than pivot.Now repeat the same procedure with these two sub arrays .Continue till subarrays contains one element and all are sorted.

Pseudo code for quick sort :

function partitionFunc(left, right, pivot)

leftPointer = left

rightPointer = right - 1

while True do

while A[++leftPointer] < pivot do

//do-nothing

end while

while rightPointer > 0 && A[--rightPointer] > pivot do

//do-nothing

end while

if leftPointer >= rightPointer

break

else

swap leftPointer,rightPointer

end if

end while

swap leftPointer,right

return leftPointer

end function

procedure quickSort(left, right)

if right-left <= 0

return

else

pivot = A[right]

partition = partitionFunc(left, right, pivot)

quickSort(left,partition-1)

quickSort(partition+1,right)

end if

end procedure

Quicksort pivot algorithm:

Step 1 − Choose the highest index value has pivot

Step 2 − Take two variables to point left and right of the list excluding pivot

Step 3 − left points to the low index

Step 4 − right points to the high

Step 5 − while value at left is less than pivot move right

Step 6 − while value at right is greater than pivot move left

Step 7 − if both step 5 and step 6 does not match swap left and right

Step 8 − if left ≥ right, the point where they met is new pivot

Quicksort Algorithm:

Step 1 − Make the right-most index value pivot

Step 2 − partition the array using pivot value

Step 3 − quicksort left partition recursively

Step 4 − quicksort right partition recursively

Program for quick sort:

#include<stdio.h>

void quicksort(int number[25],int first,int last){

int i, j, pivot, temp;

if(first<last){

pivot=first;

i=first;

j=last;

while(i<j){

while(number[i]<=number[pivot]&&i<last)

i++;

while(number[j]>number[pivot])

j--;

if(i<j){

temp=number[i];

number[i]=number[j];

number[j]=temp;

}

}

temp=number[pivot];

number[pivot]=number[j];

number[j]=temp;

quicksort(number,first,j-1);

quicksort(number,j+1,last);

}

}

int main(){

int i, count, number[25];

printf("How many elements are u going to enter?: ");

scanf("%d",&count);

printf("Enter %d elements: ", count);

for(i=0;i<count;i++)

scanf("%d",&number[i]);

quicksort(number,0,count-1);

printf("Order of Sorted elements: ");

for(i=0;i<count;i++)

printf(" %d",number[i]);

return 0;

}

The time complexities for quick sort are as follows:

Worst case:O(n**2)

Average case: O(n log n)

Best case: O(n log n)

So quicksort is divide and conquer algorithm and this how it works.

Notes : 1>. Add code of quick sort.

2> Write only 1 algorithm/ pseudo code.

3>.Add relevant diagrams and flowcharts.

4> Please proofread before submission.

Q

6

Explain Heap Sort Algorithm and its complexity?

Ans

Heap sort is very fast and widely used.In heap sort first build a heap.Heap is a tree structure which have all the levels of tree are balanced or complete and it may be either min heap( parents are smaller) or max heap(parents are greater than children).After creating heap pick first element of heap and keep it in array and recreate the heap with remaining elements.Then pick first element from the newly created heap and again recreate the heap continue this till array is sorted.

Pseudo code for heap sort:

Heapify(A as array, n as int, i as int)

{

max = i

leftchild = 2i + 1

rightchild = 2i + 2

if (leftchild <= n) and (A[i] < A[leftchild])

max = leftchild

else

max = i

if (rightchild <= n) and (A[max] > A[rightchild])

max = rightchild

if (max != i)

swap(A[i], A[max])

Heapify(A, n, max)

}

Heapsort(A as array)

{

n = length(A)

for i = n/2 downto 1

Heapify(A, n ,i)

for i = n downto 2

exchange A[1] with A[i]

A.heapsize = A.heapsize - 1

Heapify(A, i, 0)

}

C program for Heap sort:

#include <stdio.h>

void main()

{

int heap[10], no, i, j, c, root, temp;

printf("\n Enter no of elements :");

scanf("%d", &no);

printf("\n Enter the nos : ");

for (i = 0; i < no; i++)

scanf("%d", &heap[i]);

for (i = 1; i < no; i++)

{

c = i;

do

{

root = (c - 1) / 2;

if (heap[root] < heap[c]) /* to create MAX heap array */

{

temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

c = root;

} while (c != 0);

}

printf("Heap array : ");

for (i = 0; i < no; i++)

printf("%d\t ", heap[i]);

for (j = no - 1; j >= 0; j--)

{

temp = heap[0];

heap[0] = heap[j /* swap max element with rightmost leaf element */

heap[j] = temp;

root = 0;

do

{

c = 2 * root + 1; /* left node of root element */

if ((heap[c] < heap[c + 1]) && c < j-1)

c++;

if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */

{

temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

root = c;

} while (c < j);

}

printf("\n The sorted array is : ");

for (i = 0; i < no; i++)

printf("\t %d", heap[i]);

printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");

}

Time complexities for all cases of heap sort are O(n* logn)

Notes : 1>. Add pseudo code for better explanation.

2> Add relevant diagrams and flowcharts

3> Specify time complexity in the end.

Q

7

Explain radix Sort Algorithm and its complexity?

Ans

In radix sort:

Compare the unit place of each number and sort them according to their unit places.

Compare according to decimal place and sort them.

Repetition of this procedure is based on the highest element. Say if the highest number has 4 digits, we repeat it for 4 times.

Below example will help to know how radix sort works.

Radix sort algorithm :

radixSort(array)

d <- maximum number of digits in the largest element

create d buckets of size 0-9

for i <- 0 to d

sort the elements according to ith place digits using countingSort

countingSort(array, d)

max <- find largest element among dth place elements

initialize count array with all zeros

for j <- 0 to size

find the total count of each unique digit in dth place of elements and

store the count at jth index in count array

for i <- 1 to max

find the cumulative sum and store it in count array itself

for j <- size down to 1

restore the elements to array

decrease count of each element restored by 1

Radix sort program in c:

#include<stdio.h>

int get_max (int a[], int n){

int max = a[0];

for (int i = 1; i < n; i++)

if (a[i] > max)

max = a[i];

return max;

}

void radix_sort (int a[], int n){

int bucket[10][10], bucket_cnt[10];

int i, j, k, r, NOP = 0, divisor = 1, lar, pass;

lar = get_max (a, n);

while (lar > 0){

NOP++;

lar /= 10;

}

for (pass = 0; pass < NOP; pass++){

for (i = 0; i < 10; i++){

bucket_cnt[i] = 0;

}

for (i = 0; i < n; i++){

r = (a[i] / divisor) % 10;

bucket[r][bucket_cnt[r]] = a[i];

bucket_cnt[r] += 1;

}

i = 0;

for (k = 0; k < 10; k++){

for (j = 0; j < bucket_cnt[k]; j++){

a[i] = bucket[k][j];

i++;

}

}

divisor *= 10;

printf ("After pass %d : ", pass + 1);

for (i = 0; i < n; i++)

printf ("%d ", a[i]);

printf ("\n");

}

}

int main (){

int i, n, a[10];

printf ("Enter the number of items to be sorted: ");

scanf ("%d", &n);

printf ("Enter items: ");

for (i = 0; i < n; i++){

scanf ("%d", &a[i]);

}

radix_sort (a, n);

printf ("Sorted items : ");

for (i = 0; i < n; i++)

printf ("%d ", a[i]);

printf ("\n");

return 0;

}

Time complexity for radix sort is O(d(n+k)).

Here, d is the number cycle and O(n+k) is the time complexity of counting sort where n are keys which are integers of word size k.

So,this is all about radix sort.

Notes : 1>.Mention what does n and k means in radix sort time complexity.

2> Add pseudo code if possible.

3> Don't write as 2nd or 3rd person

Q

8

What is Divide and Conquer? Explain with merge sort .

Ans

Divide and Conquer means:

Divide the main problem into two or more subproblems .Continue dividing till the subproblems can not be divided further.

Now solve these subproblems and

merge their solutions to get the solution of its main problem.

Many sorting algorithm follows Divide and Conquer technique and merge sort is one of them:

In merge sort divide the unsorted array into two. Keep dividing the arrays until get the subarray with single element in it.After dividing arrays now merge the subarrays with single elements.While merging if elements from two smaller subarrays are not sorted first sort them and then merge. Keep merging until a array is sorted with all elements.

In following example the array is a unsorted array.First split the array in mid.Then divide subarrays and keep on dividing them until get a subarray with a single element in it.Now dividing array process is complete now its time for merging them..While merging merge the smallest subarrays first and continue merging them and stop when get a sorted array [3,9,10,27,38,43,82]

Pseudo code for divide and conquer using merge sort:

PROCEDURE function mergeSort

FOR each element of the master list indexed by i

if ( i <= 1 ) return a

var left = a[0] to a[i/2]

var right = a[i/2+1] to a[i]

left = mergeSort( left )

right = mergeSort( right )

return merge( left,right )

END FOR

END PROCEDURE

PROCEDURE function mergeSort

WHILE length(left) > 0 and length(right) > 0

if first(left) â‰¤ first(right)

append first(left) to result

left = rest(left)

else

append first(right) to result

right = rest(right)

IF length(left) > 0

append left to result

END IF

IF length(right) > 0

append right to result

END IF

return result

END PROCEDURE

Notes : 1>. Add pseudo code for better explanation.