Write a method named partition that accepts an array of integers a and an intege
ID: 3909987 • Letter: W
Question
Write a method named partition that accepts an array of integers a and an integer element value v as its parameters, and rearranges ("partitions") the array's elements so that all its elements of a that are less than v occur before all elements that are greater than v. The exact order of the elements is unimportant so long as all elements less than v appear before all elements greater than v. For example, if your method were passed the following array:
int[] a = {15, 1, 6, 12, -3, 4, 8, -7, 21, 2, 30, -1, 9};
partition(a, 5);
One acceptable ordering of the elements after the call would be:
{-1, 1, 2, -7, -3, 4, 8, 12, 21, 6, 30, 15, 9}
Hint: Your method will need to rearrange the elements of the array, which will involve swapping various elements from less desirable indexes to more desirable ones.
You may assume that the array contains no duplicates and does not contain the element value v itself. You may not use Arrays.sort, Collections.sort, or any other pre-defined sorting algorithm from the Java Class Libraries or textbook to solve this problem. You also may not use a String to solve this problem.
Explanation / Answer
class Main {
static void partition(int[] a, int v){
// declaring variables
int first = 0, last = a.length-1;
while(first < last){
// this is to get the left most element which is greater than v
if(a[first] < v){
first++;
continue;
}
// this is to get right most element which is less than v
if(a[last] > v){
last--;
continue;
}
// swapping both
int temp = a[first];
a[first] = a[last];
a[last] = temp;
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
public static void main(String[] args) {
int[] a = {15, 1, 6, 12, -3, 4, 8, -7, 21, 2, 30, -1, 9};
partition(a, 5);
System.out.println("Hello world!");
}
}
// Output: {-1, 1, 2, -7, -3, 4, 8, 12, 21, 6, 30, 15, 9}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.