Problem 1: Partitioning (Phase I) To parition an array, first choose one integer
ID: 3739683 • Letter: P
Question
Problem 1: Partitioning (Phase I) To parition an array, first choose one integer from the array and call it the pivot. Next manipulate the array so that all integers less than the pivot are in the left part of the array and all numbers greater than or equal to the pivot are in the right part of the array. Finally, place the pivot in-between the two parts Here's an example. We choose the first integ er as the pivot. Ornginal array: 15 19 42 317 5 88 16 11 3019 3345 2 66 13 8 12 18 The pivot is 15. Partitioned aray: 9 7 5 11 3 0 2 13 8 12 15 18 66 45 33 19 16 88 31 42 (Side note: Observe that, if we sort the array, the pivot will not move. It's in the night place!) Wite a method that partitions a given array of integers. It retuns the index ot the pivot public static int partition(int[] a) Hint #1: Use the merge method as an example. You can create a second array to hold the partitioned numbers and then copy the numbers from the second array back into the first d i. Use i to traverse the given array. Use left and night ond array to place the numbers from the given aray. The left index Hint #2: Maintain 3 ndices left, right an to determine where in the sec identifies where to place integers smaller than the pivot. The right index iden tifies where to place integers th at are greater than or equal to the pivot. Hint #3: Don't forget to place the pivot element in the second array! Hint #4: Always choose the first integer in the array as the pivot. Hint #5: This is not a recursive method. Test your metho d before continuing! Problem 2: Partitioning (Phase II) Rnd All Match CaseNavigate by 416 words, 2.201 characters Default Style English (USA) (eExplanation / Answer
#include <stdio.h>
void quick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int a[50],n,i;
printf("How many elements?");
scanf("%d",&n);
printf(" Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf(" Array after sorting:");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
void quick_sort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(int a[],int l,int u)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}