Data Structure Assignment

Assignment:
Data Structure
Submitted By:
Ahmad Sultan
Submitted To:
Sir Umair saab
Roll No:
21-UON-0906
Semester:
BSCS 3rd Evening Old Campus
Assignment Topics:
Q no:1 Write program using functions to implement Merge sort.

Q no:2 Implement the following programs in C++ using functions
a) Insertion Sort
b) Bubble Sort
c) Selection Sort
d) Linear Search
e) Binary Search
Q no:3 write a program to perform following operations on Link List
a) Insertion
b) at the beginning
c) at the end
d) at the given location in the sorted list
b) Deletion of first node of last node of given item of node of given item from
sorted list
Q no:1 Write program using functions to implement Merge sort.
#include <iostream>
using namespace std;
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {

arr[k] = M[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: ";
printArray(arr, size);
return 0;
}
OutPut
Q no:2 Implement the following programs in C++ using functions

a) Insertion Sort
b) Bubble Sort
c) Selection Sort
d) Linear Search
e) Binary Search
a) Insertion Sort
#include<iostream>
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key;
}
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int main() {
int n;
cout << "Enter the size of array: ";
cin >> n;
int arr[n];
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
OutPut
b) Bubble Sort
#include <bits/stdc++.h>
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = { 5, 1, 4, 2, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: \n";
printArray(arr, N);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}
OutPut
c) Selection Sort
#include<bits/stdc++.h>
void selectionSort(int arr[], int n)
{
int i,j,min_in;
for(i=0;i<n;i++)
{
min_in = i;
for(j=i+1;j<n;j++)
if (arr[j] < arr[min_in])
min_in = j;
swap(arr[i],arr[min_in]);
}
}
void print(int arr[], int n)
{
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main(int argv, char* argc[])
{
int arr[] = {5,4,10,1,6,2};
int i,j,n,temp;
n = sizeof(arr)/sizeof(int);
cout<<"Unsorted Array :";
print(arr,n);
selectionSort(arr,n);
cout<<"Sorted Array :";
print(arr,n);
return(0);
}
OutPut
d) Linear Search
#include<bits/stdc++.h>
int linearSearch(int arr[], int n, int key)

{
for(int i=0; i<n; i++)
{
if(key == arr[i])
return i;
}
return -1;
}
int main()
{
int array[] = {50, 90, 30, 70, 60};
int key = 0;
cout << "Enter Search Element: ";
cin >> key;
int size = sizeof(array)/sizeof(array[0]);
int index = linearSearch(array, size, key);
if(index == -1)
cout << key << " Not Found" << endl;
else
cout << key << " Found at Index = " << index << endl;
return 0;
}
OutPut
e) Binary Search
int BinarySearch(int sorted_array[], int left, int right, int element)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (sorted_array[middle] == element)
return middle;
if (sorted_array[middle] < element)
left = middle + 1;
else
right = middle - 1;
}
return -1;
}
int main()
{
int a[] = { 10, 12, 20, 32, 50, 55, 65, 80, 99 };
int element;
cout<<"Enter element to search"<<endl;
cin>>element;
int size = sizeof(a) / sizeof(a[0]);
sort(a, a + size);
int result = BinarySearch(a, 0, size - 1, element);
if(result == -1)
cout<<"Element is not present in array";
else
cout<<"Element is present at index = "<< result;
return 0;
}
OutPut
Q no:3 write a program to perform following operations on Link List

A)Insertion:
a) at the beginning
b) at the end
c) at the given location in the sorted list
class node {
public:
int data;
node* next;
node(int value)
{
data = value;
next = NULL;
}
};
void insertAt_beginning(node*& head, int val)
{
node* n = new node(val);
n->next = head;
head = n;
}
void insertAt_given_Location(node* head, int key, int val)
{
if (key == head->data) {
n->next = head->next;
head->next = n;
return;
}
node* temp = head;

while (temp->data != key) {
temp = temp->next;
if (temp == NULL) {
return;
}
}
n->next = temp->next;
temp->next = n;
}
void insertAtthe_End(node*& head, int val)
{
if (head == NULL) {
head = n;
return;
}
node* temp = head;

while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
}
void print(node*& head)
{
node* temp = head;
while (temp != NULL) {

cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main()
{
node* head = NULL;
insertAt_beginning(head, 1);
insertAt_beginning(head, 2);
cout << "At the beginning : ";
print(head);
cout<<endl;
insertAtthe_End(head, 4);
insertAtthe_End(head, 5);
cout << "At the end ";
print(head);
cout << endl;
insertAt_given_Location(head, 1, 2);
insertAt_given_Location(head, 5, 6);
cout << "At the given location in the sorted list ";
print(head);
cout << endl;
return 0;
}
OutPut
b) Deletion of first node of last node of given item of node of given item from
sorted list
class Node {
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void deleteNode(Node** head_ref, int key)
{
Node* temp = *head_ref;
Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
delete temp;
return;
}
else {
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
delete temp;
}
}
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
cout<<"Created Linked List "<<endl;

printList(head);
deleteNode(&head, 1);
cout<<"\nLinked List after Deletion of 1:"<<endl;
printList(head);
return 0;
}
OutPut
The End

Data Structure Assignment

Uploaded by

Copyright:

Available Formats

Data Structure Assignment

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure Assignment

Uploaded by

Copyright:

Available Formats

Assignment:

Q no:1 Write program using functions to implement Merge sort.

while (j < n2) {

Q no:2 Implement the following programs in C++ using functions

int linearSearch(int arr[], int n, int key)

Q no:3 write a program to perform following operations on Link List

node* temp = head;

node* temp = head;

while (temp != NULL) {

cout<<"Created Linked List "<<endl;

You might also like