Question

Data Structures and Algorithms

Help please :)

POLJOPP 3. Consider QuickSort on the array Aſlanand assume that the pivot element x (used to split the array Allo:hil into two portions such that all elements in the left portion Allom) are sx and all elements in the right portion Aſm:hi) are >x) is the last element of the array to be split (i. e., A[hi]). For a specific value of n at least 11 (your choice), construct an assignment of the numbers ...n to the n array elements that causes QuickSort, with the stated choice of pivot, to (a) execute optimally (that is Allo:m) and A[m:hi) are always of equal size) (h) execute in the slowest possible way.

Answer 1

The answer of the above question can be given as below:

/* C implementation of QuickSort,
Considering last Element as pivot */
#include <stdio.h>
#include <stdlib.h>

/*Swap Function */
void swap(int* firstVariable, int* secondvariable)
{
   int tempVariable = *firstVariable;
   *firstVariable = *secondvariable;
   *secondvariable = tempVariable;
}

/*Partitioning of Array into two Sub-Array
around Pivot Element */
int partition (int Array[], int left, int right)
{
/*Pivot Element - Array[right]*/
   int pivot = Array[right];
   int i = (left - 1);

   for (int j = left; j <= right- 1; j++)
   {
       if (Array[j] < pivot)
       {
       /*Increment the numbers Smaller than Pivot */
           i++;
           swap(&Array[i], &Array[j]);
       }
   }
   swap(&Array[i + 1], &Array[right]);
   return (i + 1);
}

void quickSort(int Array[], int left, int right)
{
   if (left < right)
   {
       /* Array[pivotIndex] is at it's right position */
       int pivotIndex = partition(Array, left, right);

       /*Independently Sort Elements before
       & after pivotIndex */
       quickSort(Array, left, pivotIndex - 1);
       printArray(Array,left,pivotIndex);

       quickSort(Array, pivotIndex + 1, right);
       printArray(Array,pivotIndex,right);
   }
}

void printArray(int Array[],int left,int right)
{
   int i;
   for (i=left; i < right; i++)
       printf("%d ", Array[i]);
   printf("\n");
}

int main()
{
   int Array[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
   int sizeOfArray = sizeof(Array)/sizeof(Array[0]);
   quickSort(Array, 0, sizeOfArray-1);
   printf("\nSorted array: \n");
   printArray(Array, 0,sizeOfArray);
   return 0;
}
/*Screen Shot */

main.c X WNH F/* c implementation of Quicksort, Considering last Element as pivot */ #include <stdio.h> #include <stdlib.h> /* Swap Function */ void swap (int* firstVariable, int* secondvariable) int tempVariable = *firstVariable; *firstVariable = *secondvariable; *secondvariable = tempVariable; co van WNHOO co van WNHO CO O P/*Partitioning of Array into two Sub-Array L around Pivot Element */ int partition (int Array[], int left, int right) { /*Pivot Element - Array[right] */ int pivot = Array[right]; int i = (left - 1); for (int j = left; j <= right- 1; j++) if (Array[j] < pivot) /*Increment the numbers Smaller than Pivot */ i++;

swap (Array[i], Array[j]); swap (&Array[i + 1), «Array[right]); return (i + 1); void quicksort(int Array[], int left, int right) wwwwwwwww WNHO COO. w if (left < right) /* Array (pivotIndex] is at it's right position */ int pivotIndex = partition (Array, left, right); /*Independently Sort Elements before & after pivotIndex */ quicksort (Array, left, pivotIndex - 1); printArray (Array, left,pivotIndex); quicksort (Array, pivotIndex + 1, right); printArray (Array, pivotIndex, right); WHO LOCO O in un un nu 1 void printArray (int Array[], int left, int right) int i; for (i=left; i < right; i++)

printf("%d", Array[i]); printf("\n"); int main() int Array[] = {1,2,3,4,5,6,7,8, 9, 10, 11, 12, 13, 14}; int sizeofArray = sizeof(Array) / sizeof(Array[0]); quickSort (Array, 0, sizeofArray-1); printf("\nSorted array: \n"); printArray (Array, 0, sizeofArray); return 0;

Question 3)

(b) When Array[1:N] will be in sorted order then Execution will be slowest .

Assignment of Numbers:

[1,2,3,4,5,6,7,8,9,10,11,12,13,14]

Number Of Comparison = O($n^{2}$)

C:\Users\Amit Shawlcode_blocks quick_sort\bin\Debug quick_sort.exe 12 123 1234 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 Sorted array: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 execution time: 0.169 S Process returned © (@xe) Press any key to continue.

Question 3: a)

When Elements Are Stored in post Order Traversal of a Binary Tree optimal Execution.

Assignment of Numbers:

[1,3,2,5,4,7,9,8,11,13,12,6]

Number of Comparison = O(
n log n
)

11 2 3 1 2 3 4 5 12 11 12 9 11 12 7 9 11 12 6 7 9 11 12 Sorted array: 1 2 3 4 5 6 7 9 11 12 13 execution time: 0.132 s Process returned © (@xo)_ Press any key to continue.

Please like the post and comment for any query related to the above problem

Thanks for liking the post !