I am trying to partition an array using 2 different methods. Apparently, to part

Question

I am trying to partition an array using 2 different methods. Apparently, to partition an array is to arrange the elemnts of an array around a pivot element such that all the elements to the left of the pivot are less than the pivot, and all the elements to the right are greater.  The elements assume no further order.

In my main method, I want the user to input the number of integers to form the array. Then I want the users to input the elements, in this case integers. Then I need to produce a method that actually partitions the array so that the first elements entered, whatever it may be, is the pivot element. Then I need the partitioned array to print.

My main method looks like this:

import java.util.*;

public class LesserGreaterArray
{
    public static void main (String[]args)
    {
        Scanner input = new Scanner(System.in);
       
        System.out.print ("How many numbers are in this array? ");
        int arraySize = input.nextInt();
        double[] arrayNumbers = new double [arraySize];
        System.out.println();
       
        System.out.println ("Enter the numbers: ");
        for (int i = 0; i < arraySize; i++)
        {
            arrayNumbers[i] = input.nextDouble();
        }
       
        System.out.println ("Array: ");
        for (int i = 0; i >= 0; i++)
        {
            System.out.print (arrayNumbers[i]);
        }
       
        System.out.println();
       
        partition(arrayNumbers);
    }

My second method looks like this:

public static double[] partition(double[] a)
    {
        double[] greaterArray = new double[a.length];
        double[] lesserArray = new double[a.length];
        double[] resultArray = new double[a.length];
        double pivotPoint = a[0];
        int j = 0;
        int k = 0;
        int m = 0;
       
      
       
        for (int i = 1; i < a.length; i++)
        {
            if (a[i] >= pivotPoint)
            {
                a[i] = greaterArray[j];
                j++;
            }
            else
            {
                a[i] = lesserArray[k];
                k++;
            }
           
        }
           
       
        System.out.println (j + " & " + k);
        for (int i = 0; i < k; i++)
            {
                resultArray[m] = greaterArray[i];
                m++;
            }
           
        return resultArray;
    }
}

Any help from this point forward?

Thanks.
   

Explanation / Answer

Quick Sort algorithm has the following complexities –

Worst Case Time Complexity – O(n2)

Average Case Time Complexity – O(n log2 n)

Best Case Time Complexity – O(n log2 n)

Space Complexity – O(n)

The O(n) space complexity of quick sort is due to the O(n) recursion calls that consume the stack. Although the complexities are vivid, the runtime of quick sort depends on a few factors –

Dual Pivot Partitioning – Until now, we did a 2-way partition, or we partitioned the array into 2 parts. Now, we will partition the array into 3 parts and recursively call solve for the partitioned sub-arrays.

First part has all elements < A.

Second part has all elements that is > A, and < B.

Third Part has elements > B.

We can put this technique in a step-by-step procedure –

#include <stdio.h>

void quickSortDualPivot(int arr[], int low, int high)

{

    if (low >= high) {

        return;

    }

    int lt = low + 1, ht = high - 1, i, temp;

    // Swapping 'low' and 'high' elements if neccessary

    if (arr[low] > arr[high]) {

        temp = arr[low];

        arr[low] = arr[high];

        arr[high] = temp;

    }

    // If only two elements are there, by this

    // point they are already sorted

    if (low + 1 == high) {

        return;

    }

    for (i = low + 1; i <= high; ++i) {

        if (i > ht) {

            // Whatever value a[i] holds beyond

            // will have a value > a[high]

            break;

        }

        if (arr[i] < arr[low]) {

            // a[i] < pivot1 so, falls in

            // first sub-array

            temp = arr[lt];

            arr[lt] = arr[i];

            arr[i] = temp;

            ++lt;

        } else if (arr[i] > arr[high]) {

            // a[i] > pivot2 so, falls in

            // third sub-array

            temp = arr[ht];

            arr[ht] = arr[i];

            arr[i] = temp;

            --ht;

            --i;

        }

        // The value of a[i] that does not go to either

        // of the cases falls in second sub-array

    }

    // Swapping the two-pivots to correct places

    ++ht;

    temp = arr[ht];

    arr[ht] = arr[high];

    arr[high] = temp;

    --lt;

    temp = arr[lt];

    arr[lt] = arr[low];

    arr[low] = temp;

    // Recursively applying the algorithm to sub-arrays

    quickSortDualPivot(arr, low, lt - 1);

    quickSortDualPivot(arr, lt + 1, ht - 1);

    quickSortDualPivot(arr, ht + 1, high);

}

int main()

{

    int n, i;

    printf("Enter the size - ");

    scanf("%d", &n);

    printf("Enter %d elements - ", n);

    int arr[n];

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

        scanf("%d", &arr[i]);

    }

    quickSortDualPivot(arr, 0, n - 1);

    printf("The Sorted Array - ");

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

        printf("%d ", arr[i]);

    }

    printf(" ");

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.