Question

Use Quicksort algorithm to sort the following sequences:

a.10, 80, 3, 19, 14, 7, 5, 12

b.Choose your sequence with 100different(random)integer numbers

c.Choose your sequence with 1000different(random)integer numbers

Please include your pseudocode, input sequence, and output in the report. Also, you need to analyze the computational time for different partition methods(e.g., best/worst/average cases)for sequences b and c.

Will rate!

design analysis and algorithms

Answer 1

#include<stdio.h> 
#include <stdlib.h>

//  function to swap two elements 

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

/* this function place the pivot element at its correct position in the sorted array, and places all smaller than pivot 
to the left of pivot and all greater elements to right of pivot */


int partition (int arr[], int low, int high) 
{ 
        int j;
        int pivot = arr[high]; // pivot element
        int i = (low - 1); // Index of the smaller element 

        for (j = low; j <= high- 1; j++) 
        { 
                // If current element is smaller than the pivot elemment
                if (arr[j] < pivot) 
                { 
                        i++; // increment index of smaller element 
                        swap(&arr[i], &arr[j]); 
                } 
        } 
        swap(&arr[i + 1], &arr[high]); 
        return (i + 1); 
} 


//arr[] is the Array to be sorted, 
//low is the Starting index, 
//high high Ending index 


void quickSort(int arr[], int low, int high) 
{ 
        if (low < high) 
        { 
                /* pi is the partitioning index of the array and arr[p] is now 
                at right place */
                int pi = partition(arr, low, high); 

                // Separately sort elements before 
                // partition and after partition 
                quickSort(arr, low, pi - 1); 
                quickSort(arr, pi + 1, high); 
        } 
} 

// Print array 

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

// Main program 
int main() 
{ 
    
    int arr[100], c, n;

    printf("Hundred random numbers in [1,1000]\n");   //  first generated 100 random numbers between 1 to 1000 and stored in the array

    for (c = 1; c <= 100; c++) 
    {
        n = rand() % 100 + 1;
        arr[c] = n;
    }
    
    for (c = 1; c <= 100; c++) 
    {
        printf("%d\t", arr[c]);
    }
    printf("\n");

        int arr_size = sizeof(arr)/sizeof(arr[0]); 
        printf("Size of the randomly generated array is %d", arr_size);
        quickSort(arr, 0, arr_size-1); 
        printf("\nSorted array: \n"); 
        printArray(arr, arr_size);  
} 

The above program will randomly generate 100 numbers and will sort them using quick sort. It can be used to sort part b. and c. of the question.

I/P and O/P

Hundred random numbers in [1,1000]
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62
92 96 43 28 37 92 5 3 54 93 83 22 17 19
96 48 27 72 39 70 13 68 100 36 95 4 12 23
34 74 65 42 12 54 69 48 45 63 58 38 60 24
42 30 79 17 36 91 43 89 7 41 43 65 49 47
6 91 30 71 51 7 2 94 49 30 24 85 55 57
41 67 77 32 9 45 40 27 24 38 39 19 83 30
42
Size of the randomly generated array is 100
Sorted array:
1 2 3 4 5 6 6 7 7 9 12 12 13 17 17 19 19 22 23 24 24 24 25 27 27 28 28 30 30 30 30 32 34 35 36 36 37 38 38 39 39 40 41 41 42 42 42 43 43 43 45 45 46 47 48 48 49 49 51 54 54 55 57 58 59 60 62 63 63 65 65 65 67 68 68 69 70 70 71 72 74 77 79 79 82 83 83 85 89 91 91 92 92 93 94 95 96 96 100

---------------------------------------------------------------------------------------------------------------------------------------------------------

/* C implementation QuickSort */
#include<stdio.h> 

// function to swap two elements 
void swap(int* a, int* b) 
{ 
        int t = *a; 
        *a = *b; 
        *b = t; 
} 

/* this function place the pivot element at its correct position in
the sorted array,and places all smaller than pivot to the left of 
pivot and all greater elements to right of pivot */

int partition (int arr[], int low, int high) 
{ 
        int pivot = arr[high]; // pivot 
        int i = (low - 1); // Index of smaller element 

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

//arr[] is the Array to be sorted, 
//low is the Starting index, 
//high high Ending index 

void quickSort(int arr[], int low, int high) 
{ 
        if (low < high) 
        { 
                /* pi is partitioning index, arr[p] is now 
                at right place */
                int pi = partition(arr, low, high); 

                // Separately sort elements before 
                // partition and after partition 
                quickSort(arr, low, pi - 1); 
                quickSort(arr, pi + 1, high); 
        } 
} 

/* Print the array */
void printArray(int arr[], int size) 
{ 
        int i; 
        for (i=0; i < size; i++) 
                printf("%d ", arr[i]); 
        printf("\n"); 
} 

//   Main program 

int main() 
{ 
        int arr[] = {10, 80, 3, 19, 14, 7, 5, 12};    //  given array in question
        int n = sizeof(arr)/sizeof(arr[0]); 
        quickSort(arr, 0, n-1); 
        printf("Sorted array: \n"); 
        printArray(arr, n); 
        return 0; 
} 

The above program will sort part a. of the question.

I/P and O/P

Given array:

10, 80, 3, 19, 14, 7, 5, 12

Sorted array:                                                                                                       

3 5 7 10 12 14 19 80