[N.B: Please post individual questions seperately. Only one question can be solved at a time as these are all seperate questions and not subparts.and also can not be solved all together within 2 hours. Solution of question 1 is given below.]
question 1:
C++ program for quick sort using 3- way partition algorithm
#include <bits/stdc++.h>
using namespace std;
/* The following function partitions the array[] in three
parts
1) array[l..i] contains elements smaller than pivot
2) array[i+1..j-1] contains all occurrences of pivot
3) array[j..r] contains elements that are greater than pivot
*/
void createpartition(char array[], int l, int r, int &i, int
&j)
{
i = l-1, j = r;
int lp = l-1, rq = r;
char value = array[r];
while (true)
{
// From left, find the first element >=value
while (array[++i] < value);
// From right, find the first element <= value
while (value < array[--j])
if (j == l)
break;
// when i and j cross, then we are done
if (i >= j) break;
// Swap, so that smaller goes to left and greater goes to
right
swap(array[i], array[j]);
// Move all same left occurrence of pivot to beginning of
// array and keep count using lp
if (array[i] == value)
{
lp++;
swap(array[lp], array[i]);
}
// Move all same right occurrence of pivot to end of array
// and keep count using rq
if (array[j] == value)
{
rq--;
swap(array[j], array[rq]);
}
}
// Move pivot element to its correct index
swap(array[i], array[r]);
// Move all left same occurrences from beginning to adjacent to
array[i]
j = i-1;
for (int k = l; k < lp; k++, j--)
swap(array[k], array[j]);
// Move all right same occurrences from end to adjacent to
array[i]
i = i+1;
for (int k = r-1; k > rq; k--, i++)
swap(array[i], array[k]);
}
// 3-way partition based quick sort
void quicksort(char array[], int l, int r)
{
if (r <= l) return;
int i, j;
createpartition(array, l, r, i, j);
// Recursive function call
quicksort(array, l, j);
quicksort(array, i, r);
}
// print the array
void printarr(char array[], int n)
{
for (int i = 0; i < n; ++i)
cout<<array[i]<<" ";
cout<<endl;
}
// Driver code
int main()
{
char array[] =
{'Z','A','H','R','L','I','S','M','E','T','J','D','B','U','N','K'};
int size = strlen(array)-1;//sizeof(array) / sizeof(int)
cout<<"The given array is ";
printarr(array, size);
cout<<endl;
quicksort(array, 0, size - 1);
cout<<"The Sorted array is ";
printarr(array, size);
return 0;
}
Output:
Please I need Solution in an hour show the steps for each algorthim C++ 1-Sort by...
need solution plz
Question 1 (CLO-4, PLo-3) Figure 1 show an input tree T. 1. Analyze the tree and mention weather the tree is a heap or not by checking heap's property. If yes, justify your answer. If no, make it a heap by adjusting the node's location 2. Alter the value of T[l1] to 100 using alter-heap algorithm. Analyze the tree again and state whether i. The tree is still a heap or not? ii. If not, which one...
need full solution of this question plz help me
Question 1 (CLO-4, PLo-3) Figure 1 show an input tree T. 1. Analyze the tree and mention weather the tree is a heap or not by checking heap's property. If yes, justify your answer. If no, make it a heap by adjusting the node's location 2. Alter the value of T[l1] to 100 using alter-heap algorithm. Analyze the tree again and state whether i. The tree is still a heap or...
please I need it urgent thanks algorithms
2.1 Searching and Sorting- 5 points each 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Give pseudocode for an algorithm that will solve the following problem. Given an array AlL..n) that contains every number between 1 and n +1 in...
C. 7. True/False Questions. (2 points each) a. Applying Horner's Rule, an n-degree polynomial can be evaluated at a given point using only n multiplications and n additions. b. Quick Sort and Merge Sort are comparison-based sorting algorithms. Heap Sort and Distribution Counting Sort are not comparison-based sorting algorithms. An AVL tree applies four types of rotations: RIGHT, LEFT, RIGHT-LEFT, and LEFT-RIGHT. d. When an AVL tree's left sub-tree is left-heavy, a LEFT rotation is needed. e. When an AVL...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
I need help with this code,
I'm stuck on it, please remember step 4, I'm very much stuck on
that part. It says something about putting how many times it
appears
Assignment #1: Sorting with Binary Search Tree Through this programming assignment, the students will learn to do the following: Know how to process command line arguments. 1 Perform basic file I/O. 2. Use structs, pointers, and strings. Use dynamic memory. 3. 4. This assignment asks you to sort the...
Need this in C++ Goals: Your task is to implement a binary search tree of linked lists of movies. Tree nodes will contain a letter of the alphabet and a linked list. The linked list will be an alphabetically sorted list of movies which start with that letter. MovieTree() ➔ Constructor: Initialize any member variables of the class to default ~MovieTree() ➔ Destructor: Free all memory that was allocated void printMovieInventory() ➔ Print every movie in the data structure in...
must be coded in c++ without any STL libraries sadly :( so im struggling on this problem, any help would be greatly appreciated, thanks in advance! :) assignment is due tomorrow and im really struggling on this last question :( a. Begin by implementing a BST for integers. The underlying structure is a linked list. You need these methods: i. BST(); -- Constructor ii. void put (int) – Inserts a value into the BST. iii. Void put(int[] a) – Inserts...
NEED HELP IN C!! Answer in C programming language.
Question:
Functions and .h file:
Test function:
part 1:
part 2:
For the assignment use the following structs for Binary Trees and Binary Search Trees. struct Binode { int value; struct Binode* left; struct BTnode* right; struct BTnode* parent; }; typedef struct Binode BTnode_t; typedef struct BST { BTnode_t* root; BST_t; Question 2 [10 points] Write a function that gets a binary tree and returns the sum of its elements. //...
Need this in C
The starter code is long, if you know how to do it in other way
please do.
Do the best you can please.
Here's
the starter code:
//
-----------------------------------------------------------------------
// monsterdb.c
//
-----------------------------------------------------------------------
#include
#include
#include
//
-----------------------------------------------------------------------
// Some defines
#define NAME_MAX 64
#define BUFFER_MAX 256
//
-----------------------------------------------------------------------
// Structs
typedef struct
{
char name[NAME_MAX];
int hp;
int attackPower;
int armor;
} Character;
typedef struct
{
int size;
Character *list;
} CharacterContainer;
//
-----------------------------------------------------------------------
//...