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

Written in C++. I need to create function printShort exactly like this description: "printShort ( )...
Written in C++. I need to create function printShort exactly like this description: "printShort ( ) - prints the Date in the format m/d/yy (no leading zeros for month and day, and two last digits for year with leading zeros (use fill digit ‘0’) if necessary). Use the accessors to get the values of the data members. " Right now it is showing the correct output for month and day, but still printing a 4 digit year. How would I...
I need this written in Java, it is a Linked List and each of it's Methods....
I need this written in Java, it is a Linked List and each of it's Methods. I am having trouble and would appreciate code written to specifications and shown how to check if each method is working with an example of one method being checked. Thank you. public interface Sequence <T> { /** * Inserts the given element at the specified index position within the sequence. The element currently at that * index position (and all subsequent elements) are shifted...
How would I add a quickSort function to the below C++ code to sort the randomly...
How would I add a quickSort function to the below C++ code to sort the randomly generated numbers? #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int i; int array[10]; int odd; int Max; int counter = 0; int main() { cout << "The 10 random elements are: "; cout << endl; srand ( time(0) ); for (int j = 0; j < 99; j++) { i = rand() % 100; if (i != i - 1) array[j] =...
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 this written in C # ASAP Write a C# console program that continually asks...
I need this written in C # ASAP Write a C# console program that continually asks the user "Do you want to enter a name (Y/N)? ". Use a "while" loop to accomplish this. As long as the user enters either an upper or lowercase 'Y', then prompt to the screen "Enter First and Last Name: " and then get keyboard input of the name. After entering the name, display the name to the screen.
Hello I need this written in C# with a few comments thanks Modify the Patient class...
Hello I need this written in C# with a few comments thanks Modify the Patient class to reference a demographic object that contains the patient phone number, email and next of kin. Create a demographic class to store this information. Make sure to create a constructor in the class for this information. Modify the Patient constructor to pass in this additional information at the time of instantiation. Modify the display method to display all the data HERE IS THE CODE...
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...
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 ________.
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...
I need convert this java code to C language. There is no string can be used...
I need convert this java code to C language. There is no string can be used in C. Thank you! import java.util.Scanner; public class Nthword { public static void main( String args[] ) { String line; int word; Scanner stdin = new Scanner(System.in); while ( stdin.hasNextLine() ) { line = stdin.nextLine(); word = stdin.nextInt(); stdin.nextLine(); // get rid of the newline after the int System.out.println( "Read line: \"" + line + "\", extracting word [" + word + "]" );...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT