National Textile University, Faisalabad
Department of Computer Science
Names: Subaina Norab.
Shaham Hijab.
Hadia Alvi.
Sumaiya Shehzadi.
Class: BSAI-5th.
Registration Nos: 22-NTU-CS-1374.
22-NTU-CS-1373.
22-NTU-CS-1343.
22-NTU-CS-1376.
Course Name: Design and Analysis of Algorithms.
Submitted To: Sir Waqar.
Files:
[Link]
[Link]
[Link]
[Link]
Display Folder:
o [Link]
o [Link]
o [Link]
Quicksort:
A divide-and-conquer algorithm that partitions an array around a pivot and recursively sorts the
subarrays.
Time complexity: nlg(n)
Method:
• Taking a pivot (randomly from array)
• Place smaller elements on the left of the pivot.
• Place larger elements on the right of the pivot.
• Recursively apply the process to the left and right subarrays.
• Once all subarrays are sorted, the array is fully sorted.
Heapsort:
A comparison-based sorting algorithm that uses a binary heap data structure to repeatedly extract
the maximum (or minimum) element.
Time complexity: nlg(n)
Method:
• Convert the array into a max-heap (largest element at the root).
• Repeatedly remove the root (maximum element), place it at the end of the array, and
heapify the remaining elements.
• Repeat until the heap size becomes 1.
Insertion Sort:
A simple sorting algorithm that builds the final sorted array one element at a time by inserting
each element into its correct position.
Time complexity: n2
Method:
• Start with the second element in the array.
• Compare it with the elements before it and shift larger elements to the right.
• Insert the current element into its correct position.
• Repeat for all remaining elements until the array is sorted.
Counting Sort:
A non-comparison-based sorting algorithm that counts the occurrences of each element and uses
these counts to place elements in the correct order.
Time complexity: n
Method:
• Count Frequencies: Count the occurrences of each element and store them in a count
array.
• Calculate Positions: Update the count array to store the cumulative positions of elements.
• Place Elements: Place each element in its correct position in the output array based on the
count array.
• Copy Output: Copy the sorted elements back into the original array.
[Link]:
This file contains frontend html involved in creating the display.
[Link]:
This file contains all the styling for the html file.
[Link]:
This file contains js code for buttons and labels, connecting it with other js files. It also contains
the code to generate the array as well as displaying it.
Table:
Time is in milliseconds
Size Quicksort Insertion Counting HeapSort
10 0.20 0.10 0.20 0.40
20 0.10 0 0.10 0.10
25 0.20 0 0.20 0.10
30 0.40 0.20 0.60 0.90
33 0.20 0.20 0.30 0.50
35 0.10 0 0.10 0.30
40 0.10 0.10 0.10 0.30
45 0.30 0.20 0.20 0.50
50 0.10 0.10 0.10 0.20
60 0.10 0.10 0.20 0.50
• Quicksort performs best overall with consistently low execution times across all input
sizes.
• Insertion Sort is efficient for smaller or partially sorted inputs but is not reliable for
larger sizes.
• Counting Sort is efficient but shows a performance spike for size 30.
• Heap Sort is the slowest overall and does not scale as well as Quicksort for larger inputs.
Display:
