Q#1) Traverse array from last to begin.
Source Code:
void traverse(int* arr, int size){
for(int i = size-1; i>=0; i--){
cout<<arr[i]<<" ";
}
}
Q#2) Write a function to insert and delete node from a linked list.
Source Code:
void insertAtHead(node* &head, int data){
node* temp = new node(data);
if(head==NULL){
head = temp;
}
else{
temp->next = head;
head = temp;
}
}
void deleteFromBegin(node* &head){
if(head==NULL){
return;
}
node* temp = head;
head = head->next;
temp->next = NULL;
delete temp;
}
Q#3) Write a program to implement Heap Sort.
Source Code:
#include<iostream>
using namespace std;
void heapify(int* arr, int size, int i){
// We consider the index that heapify algorithm accepts is largest
int largest = i;
//for left child
int left = 2*i;
// for right child
int right = 2*i+1;
if(left<=size && arr[largest]<arr[left]){
// Means it found larger element than itself so it updated with left
largest = left;
}
if(right<=size && arr[largest]<arr[right]){
// Means it found larger element than itself so it updated with right
largest = right;
}
if(largest!=i){ // If largest not equal to i means it found greater element
at left or at right so it changed it's index by it
swap(arr[largest],arr[i]);
// call heapify function for other nodes in the heap
heapify(arr,size,largest);
}
}
void heapSort(int * arr, int size){
int n = size;
while(n>1){
// swap the first element with last element, we take first element as 1 as we
follow 1 based indexing
swap(arr[n], arr[1]);
//reduces the size of last node
n--;
// now call heapify algo for 1st element to the transfer first node to
correct postition
heapify(arr,n,1);
}
}
int main(){
// We ignore -1 as we follow 1 based indexing not zero
int arr[] = {-1,5,4,3,2,1};
int size = 5;
//build heap
for(int i=size/2; i>0; i--){
heapify(arr,size,i);
}
// After Build Heap now calling HeapSort Function
heapSort(arr,size);
// Print Elements of Heap
for(int i=1; i<=size;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Q#4) Write a program to implement Quick Sort.
#include<iostream>
using namespace std;
int partition(int* arr, int s, int e){
//take first element as pivot
int pivot = arr[s];
int count = 0;
//first count how many element are less or equal than pivot
for(int i=s+1; i<=e; i++){
if(arr[i]<=pivot){
count++;
}
}
//After count elements, now put pivot to its correct position
int pivotIndex = s + count;
swap(arr[s],arr[pivotIndex]);
int i = s, j = e;
// Now sort in a way that smaller element than pivot will be on left side and
larger on right
while(i<pivotIndex && j>pivotIndex){
//increment i till less than pivot found
while(arr[i]<arr[pivotIndex]){
i++;
}
//decrement j till greater than pivot found
while(arr[j]>arr[pivotIndex]){
j--;
}
// first check i and j are not cross pivotIndex,
if(i<pivotIndex && j>pivotIndex){
// if anyone of above are not satisfy than swap i and j then
increment i and decrement j
swap(arr[i++], arr[j--]);
}
}
return pivotIndex;
}
void quickSort(int* arr, int s, int e){
//base case
if(s>=e){
return;
}
// First find partition, from where the array is divided into subarrays
int p = partition(arr,s,e);
//After found out partition call quickSort for left and right subarrays
quickSort(arr,s,p-1);
quickSort(arr,p+1,e);
}
int main(){
int arr[] = {5,4,3,2,1};
int size = 5;
quickSort(arr,0,size-1);
for(int i = 0; i<size ; i++){
cout<<arr[i]<<" ";
}
return 0;
}
