Problems 1 MUST be solved “in place”, i.e. you cannot use other arrays to copy p

Question

Problems 1 MUST be solved “in place”, i.e. you cannot use other arrays to copy parts of the given array. You can use only a few extra variables

Use comments to explain well your “algorithms” to solve the given problem and an estimate of how many operations (such as comparisons, swaps, additions etc.) your algorithm performs

Program 1: Readjusting an ARRAY You're given an unsorted array of n integers A. You need to readjust the array so that all the even numbers appear first, followed by all the odd numbers. For instance, if A-13,5,4, 6,1,7,8], one possible correct readjustment is [4,6,8,3,5,1,7]. The final order is not important, but all the even numbers must precede all the odd numbers. Do not make any assumption on how many odd or even numbers there are in A. The array A, for instance, might contain just odd numbers or just even numbers Hint: Another way of looking at the problem is the following: given an unsorted array whose elements are all 0 (zeros) or 1 (ones) sort the array so that all the 0's appear first, followed by all the 1's.

Explanation / Answer

Hi, Please find my algorithm.

Please let me knwo in case of any issue.

Algorithm:
readjust(A, n)
   1) Initialize two index variables left and right:
   left = 0, right = n -1
   2) Keep incrementing left index until we see an odd number.
   3) Keep decrementing right index until we see an even number.
   4) If lef < right then swap arr[left] and arr[right]

   Time Complexity: O(n)
  
static void readjust(int arr[])
{
/* Initialize left and right indexes */
int left = 0, right = arr.length - 1;
while (left < right)
{
/* Increment left index while we see 0 at left */
while (arr[left]%2 == 0 && left < right)
left++;

/* Decrement right index while we see 1 at right */
while (arr[right]%2 == 1 && left < right)
right--;

if (left < right)
{
/* Swap arr[left] and arr[right]*/
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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