Scribd
Upload
74 views6 pages

CS210 DSA Lab 04

This lab manual document outlines objectives and tasks for a lab on sorting algorithms. The objectives are to implement sorting algorithms. The tasks include writing functions for selection sort and insertion sort that use while loops, and calling the functions to sort arrays of random values. A table is included to record the run times of selection sort and insertion sort for arrays of increasing sizes from 100 to 10,000,000 elements.

Uploaded by

Shehzad Ahmad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
74 views6 pages

CS210 DSA Lab 04

This lab manual document outlines objectives and tasks for a lab on sorting algorithms. The objectives are to implement sorting algorithms. The tasks include writing functions for selection sort and insertion sort that use while loops, and calling the functions to sort arrays of random values. A table is included to record the run times of selection sort and insertion sort for arrays of increasing sizes from 100 to 10,000,000 elements.

Uploaded by

Shehzad Ahmad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

CS 210 – Data Structures and Algorithms Lab Manual

LAB NO. 04
SORTING ALGORITHMS
Following are the lab objectives:
Objectives
Lab

1. Implementation of sorting algorithms

ABDULLAH
Student ID 2636
Student Name
Obtained
Marks Comments
Marks
Task 1 10
Task 2 10
Task 3 10
Total
30
Marks

Lab Instructor

Date: 04-10-2019

1
CS 210 – Data Structures and Algorithms Lab Manual

Lab Objectives and CLOs Mapping

CLOs
Lab Objectives
a b C
1

Instructions
 This is individual Lab work/task.
 Complete this lab work within lab timing.
 Discussion with peers is not allowed.
 You can consult any book, notes & Internet.
 Copy paste from Internet will give you negative marks.
 Lab work is divided into small tasks, complete all tasks sequentially.
 Show solution of each lab task to your Lab Instructor.
 In-Lab Exercises/Tasks
 Write your code at provided space after each question
 You need to upload code for all tasks at Google Class.

2
CS 210 – Data Structures and Algorithms Lab Manual

LAB TASKS
Task 1 (10 mark)

Write a function for Selection Sort, which uses while loop(s) to complete its procedure. Call the
function in main for demonstration. You can initialize array with random values.
#include<iostream>
#include<time.h>
using namespace std;

void swap(int *xp, int *yp)


{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)


{
int i, j, min_idx;
i = 0;
while (i < n - 1)
{
min_idx = i;
j = i + 1;
while (j<n)
{
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
j++;
}
swap(&arr[min_idx], &arr[i]);
i++;
}

/* Function to print an array */


void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

// Driver program to test above functions


int main()
{
srand(time(0));
int arr[1000];
int n;
int st = time(0);
int et;

3
CS 210 – Data Structures and Algorithms Lab Manual

for (int i = 0;i < 1000;i++)


{
arr[i] = rand() % 30 +1 ;
}
selectionSort(arr, 1000);
cout << "Sorted array: \n";
printArray(arr, 1000);
et = time(0);
cout << endl;
cout << "Time" << endl;
cout << et - st << endl;
system("pause");
return 0;

Task 2 (10 mark)


Write a function for Insertion Sort, which uses while loop(s) to complete its procedure. Call the
function in main for demonstration. You can initialize array with random values.
#include<iostream>
#include<conio.h>
#include<time.h>
using namespace std;
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
void insertionSort(int arr[], int size)
{
int step = 1, j;
int key;
while (step < size)
{
key = arr[step];
j = step - 1;
step++;
while (key < arr[j] && j >= 0)
{
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main()
{
int rt = time(0), et;
srand(time(0));

4
CS 210 – Data Structures and Algorithms Lab Manual

int n;
int data[500000];
//cout << "Enter size of Array:";
//cin >> n;
for (int i = 0;i < 500000;i++)
{
data[i] = rand()%30 + 1;
}
insertionSort(data, 500000);
cout << "Sorted array in ascending order:\n";
printArray(data, 500000);

et = time(0);
cout << endl;
cout << "Time:" << endl;
cout << et - rt << endl;

system("pause");
return 0;
}

Task 3 (10 mark)

Use code written in task 1 & 2 and execute it for different number of sizes. Fill the following
table accordingly.

Size (N) Selection Sort (time) Insertion Sort (time)

100 0 0

500 1 0

1,000 0 1

5,000 2 3

10,000 5 5

25,000 12 11

50,000 26 24

1,00,000 67 49

5,00,000 135 100

10,00,000 275 240

5
CS 210 – Data Structures and Algorithms Lab Manual

You might also like