Question

In: Computer Science

I need a randomized quicksort function written in c++ or java with dual pivots and a...

I need a randomized quicksort function written in c++ or java with dual pivots and a partition function

Solutions

Expert Solution

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int partition(int* arr, int low, int high, int* lp);
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void Pivot(int* arr, int low, int high)
{
    if (low < high) {
        int lp, rp;
        rp = partition(arr, low, high, &lp);
        Pivot(arr, low, lp - 1);
        Pivot(arr, lp + 1, rp - 1);
        Pivot(arr, rp + 1, high);
    }
}

int partition(int* arr, int low, int high, int* lp)
{
    if (arr[low] > arr[high])
        swap(&arr[low], &arr[high]);

    int j = low + 1;
    int g = high - 1, k = low + 1, p = arr[low], q = arr[high];
    while (k <= g) {

        if (arr[k] < p) {
            swap(&arr[k], &arr[j]);
            j++;
        }

        else if (arr[k] >= q) {
            while (arr[g] > q && k < g)
                g--;
            swap(&arr[k], &arr[g]);
            g--;
            if (arr[k] < p) {
                swap(&arr[k], &arr[j]);
                j++;
            }
        }
        k++;
    }
    j--;
    g++;

    swap(&arr[low], &arr[j]);
    swap(&arr[high], &arr[g]);
    *lp = j;

    return g;
}

int main()
{
    int n;
    cout<<"enter the size of array"<<endl;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    Pivot(arr, 0, n);
    cout << " array after sorting is: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

Related Solutions

I need code written in java for one of my projects the instructions are Write a...
I need code written in java for one of my projects the instructions are Write a program that interacts with the user via the console and lets them choose options from a food menu by using the associated item number. It is expected that your program builds an <orderString> representing the food order to be displayed at the end. (See Sample Run Below). Please note: Each student is required to develop their own custom menus, with unique food categories, items...
I need the JAVA code for a 4 function calculator app on andriod studio - The...
I need the JAVA code for a 4 function calculator app on andriod studio - The requirements are the following : - The only buttons needed are 0-9, *, /, +, -, a clear, and enter button - Implement the onclicklistener on the main activity - The calcuator should use order of operations (PEMDAS) - It should be able to continue from a previous answer (Ex: If you type 2+6 the calculator will display 8. If you then multiple by...
I need this code translated from C++ to Java. Im personally still trying to learn Java,...
I need this code translated from C++ to Java. Im personally still trying to learn Java, so if you can include screenshots of your IDE/output that would be helpful. Much appreciated! #include <iostream> #include <string> using namespace std; class pizza { public:    string ingrediants, address;    pizza *next;    pizza(string ingrediants, string address)    {        this->address = address;        this->ingrediants = ingrediants;        next = NULL;    } }; void enqueue(pizza **head, pizza **tail, pizza...
The equation for a simple consumption function is written as C = a + bY. The...
The equation for a simple consumption function is written as C = a + bY. The letter a represents the ________ part of consumption. The letters bY represent the ________ part of consumption. When graphing a consumption function, the vertical intercept is given by the letter ________ , and the slope of the function is given by the letter ________.
IN JAVA PLEASE ASAP !!! I just need the main and mergesort function Ask the user...
IN JAVA PLEASE ASAP !!! I just need the main and mergesort function Ask the user for the number of elements, not to exceed arraySize = 20 (put appropriate input validation) Ask the user for the type of data they will enter - EnglishGrade or MathGrade objects. Use your EnglishGrade and MathGrade classes Based on the input, create an appropriate array for the data to be entered. Write a helper function called recursionMergeSort such that: It is a standalone function...
I need the following C code converted to java or C++ #include <stdio.h> #include <stdlib.h> typedef...
I need the following C code converted to java or C++ #include <stdio.h> #include <stdlib.h> typedef struct node { struct node *left; struct node *right; long data; long leftSize; } node; void btreeInsert(node *new, node **rootptr) { node *parent = NULL, *cursor; /* Find parent */ cursor = *rootptr; while (cursor != NULL) { parent = cursor; if (new->data < cursor->data) { cursor->leftSize += 1; cursor = cursor->left; } else { cursor = cursor->right; } } /* Insert node below...
implement c++ Quicksort using median of 3 as pivot. this also pass comparator as a function...
implement c++ Quicksort using median of 3 as pivot. this also pass comparator as a function param so it can sort vector in increasing or decreasing order based on the comparator passed. the test code uses std::less comparator. #ifndef QSORT_H #define QSORT_H #include #include using namespace std; template T median_of_three(T& a, T& b, T& c, TComparator comparator) { } template size_t partition(vector& vec, TComparator& comparator, size_t low, size_t high) { // TODO: implement. } template void QuickSort(vector& vec, TComparator comparator,size_t...
JAVA JAVA JAVA Hey i need to find a java code for my homework, this is...
JAVA JAVA JAVA Hey i need to find a java code for my homework, this is my first java homework so for you i don't think it will be hard for you. (basic stuff) the problem: Write a complete Java program The transport Company in which you are the engineer responsible of operations for the optimization of the autonomous transport of liquid bulk goods, got a design contract for an automated intelligent transport management system that are autonomous trucks which...
I need a full java code. And I need it in GUI With the mathematics you...
I need a full java code. And I need it in GUI With the mathematics you have studied so far in your education you have worked with polynomials. Polynomials are used to describe curves of various types; people use them in the real world to graph curves. For example, roller coaster designers may use polynomials to describe the curves in their rides. Polynomials appear in many areas of mathematics and science. Write a program which finds an approximate solution to...
I want this program written in JAVA with the algorithm(The step by step process for the...
I want this program written in JAVA with the algorithm(The step by step process for the problem) . Please help it is due in a couple of hours. I don't want the C++ program, I want it in JAVA please #20 Theater Ticket Sales Create a TicketManager class and a program that uses it to sell tickets for a single performance theater production. Here are the specifications: • The theater's auditorium has 15 rows, with 30 seats in each row....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT