Assignment 1: Implementing and Analyzing Sorting Algorithms with Dynamic Input  Size

PART -I

Objective:

The objective of this assignment is to implement and analyze the Bubble Sort algorithm by dynamically handling multiple input sizes through command-line arguments. You will measure the execution time and comparison time for each input size and visualize the results.

Tasks:

1.  Command-Line Input Format:

• • • Modify the program to accept the number of input sizes and their respective values as command-line arguments.
           
      int main(int argc, char *argv[]) { // Code here }
      Key Points:

• Argument 0 (argv[0]) is always the program's name or path.

• Additional arguments are accessible through argv[1], argv[2], and so on.

• Arguments are always strings; conversions (e.g., to integers) must be done explicitly, use atoi()

• • • Example usage:

• • • • ./bubble_sort 5 1000 10000 50000 100000 1000000

Here:

•   5 indicates the number of input sizes.

• 1000, 10000, 50000, 100000, 1000000 are the input sizes (number of elements) for sorting.

2.  Dynamic Memory Allocation:

• For each input size, dynamically allocate memory for the array using malloc().

• Populate the array with random numbers for sorting.

• https://drive.google.com/drive/folders/1BRiUFTbsDyFw05ZoU0gDaxZ729dY6ht_?usp=sharing

3. Implement Bubble Sort:

• Write a Bubble Sort function to sort the dynamically allocated arrays.

4.  Measure Performance:

• For each input size, measure:

o Total computation time: The time taken to complete the sorting process (in microseconds).

Use high-precision timers like gettimeofday() to measure time in microseconds.

                        https://drive.google.com/drive/folders/1BRiUFTbsDyFw05ZoU0gDaxZ729dY6ht_?usp=sharing

o Total comparison time: The time spent during element comparisons.

5.  Store Results in a CSV File:

•  Record the following data in a CSV file for each input size:

o Input size.

o Total computation time (in microseconds).

o Total comparison time (in microseconds).

6.  Visualize the Results:

• Use the CSV data to create graphs in Excel or any other tool:

  • Machine Computation Time vs. Input Size.

  • Comparison Time vs. Input Size in Worse Case

  •  Comparison Time vs. Input Size in Best Case

PART II

Objective:

The objective of this assignment is to implement and analyze the (a) Insertion Sort, (b) Selection Sort (c) Binary Search (d) Two Way Merge Sort by dynamically handling multiple input sizes through command-line arguments. You will measure the machine execution time and Number of comparisons (in Best and worst case) for each input size and visualize the results.