Question

Write a program, using any language you want, and any sorting algorithm discussed in this unit to sort the following :

243, 1, 4, 6, 234, 33, 674, 32, 3333

Note: Can you write it in quick sort

Answer 1

Doing the quick sort in C language :

#include<stdio.h>

void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}


int partition (int a[], int l, int h)
{
int pivot = a[h]; // pivot
int ind = (l - 1); // Index of smaller element

for (int j = l; j <= h- 1; j++)
{
// If current element is smaller than the pivot
if (a[j] < pivot)
{
ind++; // increment index of smaller element
swap(&a[ind], &a[j]);
}
}
swap(&a[ind + 1], &a[h]);
return (ind + 1);
}

void quickSort(int a[], int l, int h)
{
if (l < h)
{
// p is the partitioning index, a[p] is now at right place
int p = partition(a, l, h);

quickSort(a, l, p - 1); //sort the elements before the partition
quickSort(a, p + 1, h); ////sort the elements after the partition
}
}

void printArr(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}


int main()
{
int a[] = {243, 1, 4, 6, 234, 33, 674, 32, 3333};
int num = sizeof(a)/sizeof(a[0]);
quickSort(a, 0, num-1);
printf("The Sorted array is : \n");
printArr(a, num);
return 0;
}

Here is the screenshot of the code and it's output: