3,4 s. First, here\'s asimple implementation of the partitioning step. does two

Question

3,4 s. First, here's asimple implementation of the partitioning step. does two scans of the amay and uses an additionalanray as temporary storage. template Kelaas T int partition (T all int start int stop, int pivot) Partitions the elements of an array around a pivot PRECONDITION: The indices are valid, start occurs before stop and pivot is within the range tstart, stop). ITION: The elements in Istart, pivot) are smaller than alpivot and the elements in Ipivot 1 stop) are greater or equal to the pivot. Note that the pivot may move during partioning. The argument pivot is updated accordingly. ASSUMPTION ON TEMPLATE ARGUMENT: values of type T can be compared using the operator. std: :swap (alpivot 1, tart]); moves pivot to start T temp new TI stop start J. int k 0; next available position in temp for (int i start 1; i stop ++i) if (ali) atstart)) templk] alij templkl a [start]: pivot pivot start ki final index in a ++k; for (int i start 1: i stop: ++i) if (ali] alstart 1)) templ ali); std: copy (temp, tempo k, a start); delete tempi

Explanation / Answer

Please find the code below:

// Randomized version of Quick Sort that uses Partitioning

#include <stdio.h>
void quickSort( int[], int, int);
int partition( int[], int, int);

void main()
{
   int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
   int i;
  
   printf(" Unsorted array is: ");
  
   for(i = 0; i < 9; ++i)
       printf(" %d ", a[i]);
  
   quickSort( a, 0, 8);
   printf(" Sorted array is: ");
  
   for(i = 0; i < 9; ++i)
       printf(" %d ", a[i]);
}

// quickSort to call partition function.
void quickSort( int a[], int l, int r)
{
   int j;
   if( l < r )
   {
       // divide and conquer
       j = partition( a, l, r);
      
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }
}

// Paritioning happens here.
int partition( int a[], int l, int r) {
   int pivot, i, j, temp;
   pivot = a[l];
   i = l; j = r+1;
   while( 1)
   {
       do ++i; while( a[i] <= pivot && i <= r );
       do --j; while( a[j] > pivot );
       if( i >= j ) break;
       temp = a[i]; a[i] = a[j]); a[j] = temp;
   }
   temp = a[l]; a[l] = a[j]); a[j] = temp;
   return j;
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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