You need to write a C function to sort a given one-dimensional array of integers

Question

You need to write a C function to sort a given one-dimensional array of integers, using
the “quick sort” algorithm. Quick sort is a divide and conquer algorithm. It first divides a
large array into two smaller sub-arrays and then recursively sort the sub-arrays.
When you define a quick sort function, it should take three inputs (parameters), e.g.,
void quickSort(int A[], int low, int high)

A is the array to be sorted, low and high are two indices that specify a part (sub-array) of
the array. For example, if low is 2 and high is 4, it specifies the part of the array from A[2]
to A[4]. Each call of the quickSort function actually sorts the sub-array in A specified by low
and high. To sort the entire array, we just call the quickSort function like this (suppose the
size of the array A is 7):
quickSort(A, 0, 6);
Quick sort works in this way:

Step 1: Pick an element, called a pivot, from the (sub)array. In our case, we will always pick
the element whose index is
low + (high - low) / 2
as the pivot.

Step 2: Reorder the array so that all elements with values less than the pivot come before
the pivot, while all elements with values greater than the pivot come after it. After this
step, the pivot is already in its final position (of the finally sorted array). This step is called
the partition step, because it partitions the array into two sub-arrays.

Step 3: Recursively apply the above steps to the sub-array of elements with the smaller
values and (separately) to the sub-array of elements with the greater values.
The second step (partition) is the most tricky step. It can be done in different ways. For this
homework, you need to implement this step as described by the following pseudo-code.
Pseudo-code for the partition step of quick sort:
What are given: the array A, the low and high indices, and the pivot index
Procedure:

pivotValue = A[pivotIndex]
// put the chosen pivot at A[high]
swap A[pivotIndex] and A[high]
// Initially, the final position (after sorting) of the pivot is set to the low index
pivotFinalPos = low
// Compare remaining array elements against pivotValue (= A[high])
for i from low to (high - 1):
if A[i] < pivotValue
swap A[i] and A[pivotFinalPos]
pivotFinalPos = pivotFinalPos + 1
end if
end for
// Move pivot to its final place
swap A[pivotFinalPos] and A[high]

2.1 (1 point) As we can see, quick sort uses recursion. Explain what is the recursive pattern,
i.e., what is the smaller problem(s) contained in a big problem?

2.2 (1 points) What should be the termination condition for quick sort, i.e., when should quick
sort stop calling itself?

2.3 (2 points) Write a pseudo-code for the quick sort function at the high level (You do not
need to write the pseudo-code for the “partition” sub-routine since it is already given). You
can write the pseudo-code in your own way and do not need to follow a convention, as long as
the logic is correct and understandable to us.

2.4 (4 points) Implement the quick sort function and test it with a given example array. You
only need to implement the quicksort() function as dfa bellow belows :
Your program should look like this:

#include <stdio.h>
void quickSort(int a[], int low, int high) {
/* Your code goes here */
}
int main() {
int a[7] = {6, 12, 5, 97, 1, 8, 56};

quickSort(a, 0, 6);

printf("The sorted array is: ");
int i;
for(i = 0; i < 7; i++)
printf("%d ", a[i]);
printf(" ");
}

Explanation / Answer

#include<stdio.h>
void swap (int a[], int left, int right)
{
int temp;
temp=a[left];
a[left]=a[right];
a[right]=temp;
}
void quicksort( int a[], int low, int high )
{
int pivot;
if ( high > low )
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
}
int partition( int a[], int low, int high )
{
int left, right;
int pivot_item;
int pivot = left = low;
pivot_item = a[low];
right = high;
while ( left < right )
{
while( a[left] <= pivot_item )
left++;
while( a[right] > pivot_item )
right--;
if ( left < right )
swap(a,left,right);
}
a[low] = a[right];
a[right] = pivot_item;
return right;
}
// void quicksort(int a[], int, int);
void printarray(int a[], int);
int main()
{
int a[50], i, n;
printf(" Enter no. of elements: ");
scanf("%d", &n);
printf(" Enter the elements: ");
for (i=0; i<n; i++)
scanf ("%d", &a[i]);
printf(" Unsorted elements: ");
printarray(a,n);
quicksort(a,0,n-1);
printf(" Sorted elements: ");
printarray(a,n);
}
void printarray(int a[], int n)
{
int i;
for (i=0; i<n; i++)
printf(" %d ", a[i]);
printf(" ");
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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