Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
- This program is a C implementation of the Insertion Sort algorithm. It reads integer values from an input file and sorts them in ascending order using the Insertion Sort algorithm. The sorted values are then printed to the console. The purpose of this program is to demonstrate the performance of the Insertion Sort algorithm for varying input sizes.
- The program was writen to implement the Insertion Sort algorithm in C and measure its performance for various input sizes. The program reads input values from a file and sorts them in ascending order using the Insertion Sort algorithm. The sorted values are then printed to the console. The program is designed to measure the running time of the algorithm for various input sizes.
- The program is written in C and consists of several functions. The main function is responsible for calling the other functions and measuring the running time of the algorithm. The other functions are responsible for reading the input values, sorting the values using the Insertion Sort algorithm, and printing the sorted values to the console.
- The readfileintoarray function reads the input values from a file and stores them in an array. The function takes three parameters: the number of command line arguments (argc), an array of command line arguments (argv), and a pointer to an integer array (Arr). The function returns the number of values read from the input file. The function first opens the input file for reading and determines the number of values in the file. It then allocates memory for the integer array based on the number of values in the file. Finally, the function reads the values from the file and stores them in the integer array.
- The insertionSort function implements the Insertion Sort algorithm to sort the input values in ascending order. The function takes two parameters: an integer array (Arr) and the number of elements in the array (Elements). The function iterates over the array and inserts each element in its correct position in the sorted subarray. The function uses a key element to compare with the elements in the sorted subarray and shifts elements to the right to make space for the key element. The function repeats this process until all elements have been inserted into the sorted subarray.
- The PrintArray function prints the elements of an integer array to the console. The function takes two parameters: an integer array (Arr) and the number of elements in the array (SizeAp). The function iterates over the array and prints each element to the console.
- The main function is responsible for calling the other functions and measuring the running time of the algorithm. The function takes two parameters: the number of command line arguments (argc) and an array of command line arguments (argv). The function first calls the readfileintoarray function to read the input values from the input file and store them in an integer array. The function then calls the insertionSort function to sort the values in ascending order. The function measures the running time of the algorithm using the clock function. The sorted values are then printed to the console using the PrintArray function.
- The input file is a text file containing integer values. The program reads these values and sorts them in ascending order using the Insertion Sort algorithm. The input file used for this assignment contains the following values :
844964
291243
276958
214417
204959
811169
66407
821022
390764
817029
- The provided code implements the insertion sort algorithm to sort an array of integers read from an input file. The program reads the input file into an array, sorts the array using insertion sort, and then prints the sorted array to the console.
- The program measures the time taken to sort the array using the clock() function provided by the time.h library. The program then outputs the number of clock tics taken to perform the sort.
- To evaluate the performance of the insertion sort algorithm, the program was executed with input files of varying sizes, ranging from 1,024 integers to 20,00,000 integers. The execution time for each input file was measured and recorded in tics.
- The program outputted the execution time in tics, which were used to calculate the actual runtime using the formula (tics/CLOCKS_PER_SEC). The calculated runtime was then compared against the expected runtime, which is O(n^2) for insertion sort.
- The runtime results indicate that the actual runtime for insertion sort is consistent with the expected runtime of O(n^2). As the input size increases, the execution time also increases at a much faster rate.
- Based on the results, it can be concluded that insertion sort is not an efficient sorting algorithm for large datasets. Other sorting algorithms such as quicksort, mergesort, or heapsort should be used instead for better performance.
Overall, the Insertion Sort algorithm is an efficient algorithm for smaller input sizes, but its performance degrades quickly as the input size increases.
In conclusion, the insertion sort algorithm is a simple yet effective sorting algorithm that can perform well for small to medium-sized datasets. However, as the size of the input increases, the algorithm's performance rapidly degrades due to its O(n^2) time complexity. Therefore, it is not recommended to use insertion sort for large datasets.
From the performance analysis, we can see that as the input size increases, the runtime of the algorithm increases exponentially. The graph clearly depicts that the runtime of insertion sort is proportional to the square of the input size. Therefore, for large datasets, it is better to use more efficient sorting algorithms such as quicksort or mergesort, which have a lower time complexity and can handle large datasets more efficiently.
Overall, the performance analysis and graph demonstrate the importance of choosing the right algorithm for a given task. While insertion sort is a simple and intuitive algorithm, it may not always be the best choice, especially when dealing with large datasets. By considering the size of the input and the time complexity of different algorithms, we can choose the most efficient algorithm for a given task and achieve optimal performance.