Scribd
Upload
3 views8 pages

Aad Lab Assignment

The document is an assignment from Jahangirnagar University's Institute of Information Technology for the course 'Algorithm Analysis and Design Lab'. It includes implementations of two sorting algorithms: Binary Search Tree Sort and Heap Sort, along with the necessary code and instructions for user input. The assignment is submitted by Tasnim Binta Hai to Assistant Professor Mehrin Anannya.

Uploaded by

shoilysiddiqi03
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
3 views8 pages

Aad Lab Assignment

The document is an assignment from Jahangirnagar University's Institute of Information Technology for the course 'Algorithm Analysis and Design Lab'. It includes implementations of two sorting algorithms: Binary Search Tree Sort and Heap Sort, along with the necessary code and instructions for user input. The assignment is submitted by Tasnim Binta Hai to Assistant Professor Mehrin Anannya.

Uploaded by

shoilysiddiqi03
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

Jahangirnagar University

Institute Of Information Technology


Assignment No-01

Course code:ICT-2202

Course Name:Algorithm Analysis and Design Lab

Submitted To:

Mehrin Anannya

Assistant Professor

Institute of Information Technology,Jahangirnagar University

Submitted By:

Tasnim Binta Hai

ID:2068

Institute of Information Technology,Jahangirnagar University


[Link] Search Tree Sort

Code:

#include <iostream>

#include <vector>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

Node(int value) {

data = value;

left = right = nullptr;

};

Node* insert(Node* root, int value) {

if (root == nullptr)

return new Node(value);


if (value < root->data)

root->left = insert(root->left, value);

else

root->right = insert(root->right, value);

return root;

void inorder(Node* root, vector<int>& sorted) {

if (root != nullptr) {

inorder(root->left, sorted);

sorted.push_back(root->data);

inorder(root->right, sorted);

vector<int> treeSort(const vector<int>& arr) {

Node* root = nullptr;

for (int num : arr)

root = insert(root, num);


vector<int> sorted;

inorder(root, sorted);

return sorted;

int main() {

int n;

cout << "Enter the number of elements: ";

cin >> n;

vector<int> arr(n);

cout << "Enter " << n << " elements:\n";

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

cin >> arr[i];

vector<int> sorted = treeSort(arr);

cout << "Sorted array: ";

for (int num : sorted)

cout << num << " ";


cout << endl;

return 0;

Output:

[Link] Sort
Code:
#include <iostream>

#include <vector>

using namespace std;


void heapify(vector<int>& arr, int n, int i) {

int largest = i; // Initialize largest as root

int left = 2 * i + 1; // left child

int right = 2 * i + 2; // right child

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

void heapSort(vector<int>& arr) {

int n = [Link]();

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {


// Move current root to end

swap(arr[0], arr[i]);

heapify(arr, i, 0);

int main() {

int n;

cout << "Enter number of elements: ";

cin >> n;

vector<int> arr(n);

cout << "Enter " << n << " elements:\n";

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

cin >> arr[i];

heapSort(arr);

cout << "Sorted array: ";

for (int num : arr)

cout << num << " ";

cout << endl;


return 0;

Output:

You might also like