BÀI TẬP THỰC HÀNH CẤU TRÚC DỮ LIỆU

VÀ GIẢI THUẬT
LAB MANUAL

Academic Year : 2022 - 2023

Semester : I

Prepared by
MSc. KhangVQH

1|Page
S. No. Experiment

1
SEARCHING TECHNIQUES
2
SORTING TECHNIQUES
3
SORTING TECHNIQUES
4 IMPLEMENTATION OF STACK AND QUEUE

5
APPLICATIONS OF STACK
6 IMPLEMENTATION OF SINGLE LINKED LIST

7 IMPLEMENTATION OF DOUBLE LINKED LIST

8 IMPLEMENTATION OF STACK USING LINKED LIST

9 IMPLEMENTATION OF QUEUE USING LINKED LIST

10 IMPLEMENTATION OF BINARY SEARCH TREE

2|Page
 WEEK - 2

SORTING TECHNIQUES

2.1 OBJECTIVE:

1. Write a C program for implementing Bubble sort techniques to arrange a list of integers in ascending
order.
2. Write a C program for implementing insertion sort techniques to arrange a list of integers in ascending
order.

2.2 PROGRAM LOGIC:

 Bubble Sort Algorithm
Algorithm bubblesort ( x[], n)
{ // x[1:n] is an array of n elements
for i := 0 to n do {
for j := 0 to n–i-1 do {
if (x[j] > x[j+1]) {
temp = x[j];
x[j] = x[j+1];
x[j+1] = temp;
}
}
}
}

 Insertion Sort Algorithm

Algorithm insertionsort (a, n)
{//sort the array a[1:n] in ascending order
for j:=2 to n do
{
item:=a[j];
i=j-1;
while((i>1) and (item< a[i])) do
{
a[i+1]:=a[i];
i:=i-1;
}
a[i+1]:=item;
}
}

3|Page
 2.3 IMPLEMENTATION:

 Implementation of Bubble Sort

Output:

 Implementation of Insertion Sort

2. 4 LAB ASSIGNMENT:

1. Formulate a program that implement Bubble sort, to sort a given list of integers in descending order.
2. Compose a program that implement Insertion sort, to sort a given list of integers in descending
order.
3. Formulate a program to sort N names using Bubble sort.
4. Write a program to sort N employee records based on their salary using insertion sort.
5. A class contains 50 students who acquired marks in 10 subjects write a program to display top 10
students roll numbers and marks in sorted order by using bubble sorting technique.

2.5 POST LAB QUESTIONS:

1. Write the time complexity of Bubble Sort?
2. Write the time complexity of Insertion Sort?

4|Page