This is the question I have: Design an algorithm to rearrange elements of a give
ID: 3724794 • Letter: T
Question
This is the question I have:
Design an algorithm to rearrange elements of a given array of n integers so that all its negative elements precede all its positive elements and zeros (if any). Your algorithm must have a computing time no greater than Q(n). Secondly, your algorithm must use only one 1-D array. Hint: Use the partition idea similar to that of Quicksort.
And here is what I have so far in my code (I got it to work but it prints the modified all sorted which is not like his example and I can't get it to print the way he wants):
public static void main(String[] args) {
int x, n;
int arr[];
System.out.printf("Enter the number of elements in the array: ");
Scanner input = new Scanner(System.in);
x = input.nextInt();
arr = new int [x];
for(int i = 0; i < x; i++)
{
System.out.printf("Enter an element: ");
arr[i] = input.nextInt();
}
input.close();
n = arr.length;
System.out.printf("The original array: ");
printArray(arr);
Quicksort(arr, 0, n-1);
System.out.printf("The modified array: ");
printArray(arr);
}
public static void printArray(int arr[])
{
int n = arr.length;
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void Quicksort(int arr[], int low, int high)
{
if(low < high)
{
int s = Partition(arr, low, high);
Quicksort(arr, low, s-1);
Quicksort(arr, s+1, high);
}
}
public static int Partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = low - 1;
int j = high;
while(i >= j)
{
while(arr[i] >= pivot)
{
i++;
}
while(arr[j] <= pivot)
{
j--;
}
Swap(arr, i, j);
}
Swap(arr, i, j);
Swap(arr, high, i);
return i;
}
public static void Swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Enter the number of elements in the array: 10 Enter an element: -32 Enter an element 45 Enter an element -1 Enter an element: 0 Enter an element: 7 Enter an element -5 Enter an element: 46 Enter an element: -3 Enter an element: 0 Enter an element -12 The original array: -32 45 -1 07 -5 46-3 0 -12 The modified array:-32 -12 1 -3 -5 46 7 00 45Explanation / Answer
public static void main(String[] args) {
int x, n;
int arr[];
System.out.printf("Enter the number of elements in the array: ");
Scanner input = new Scanner(System.in);
x = input.nextInt();
arr = new int [x];
for(int i = 0; i < x; i++)
{
System.out.printf("Enter an element: ");
arr[i] = input.nextInt();
}
input.close();
n = arr.length;
System.out.printf("The original array: ");
printArray(arr);
//Quicksort(arr, 0, n-1);// they are asking for O(n)..algorithm.. so quick sort wont work
//i will provide an algorithm which runs in O(n) and only with one array...
set(arr,n);
System.out.printf("The modified array: ");
printArray(arr);
}
public static void set(int a[],int n)
{
//first setting negative numbers...
int i=0,j=0;
for(j=0;j<n;j++)
{
if(a[j]<0)
{
Swap(a,i,j);
i++;
}
}//all negative numbers are placed...
//then.. setting zeros...
for(j=i;j<n;j++)
{
if(a[j]==0)
{
Swap(a,i,j);
i++;
}
}
//the resulting array contains...the desired order...
//it is similar...to partition method in quick sort...
}
public static void printArray(int arr[])
{
int n = arr.length;
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void Swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
output:
run:
Enter the number of elements in the array: 5
Enter an element: 0
Enter an element: 3
Enter an element: 2
Enter an element: -1
Enter an element: -2
The original array: 0 3 2 -1 -2
The modified array: -1 -2 0 2 3
BUILD SUCCESSFUL (total time: 15 seconds)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.