Scribd
Upload
4 views

Sorting Report

Uploaded by

Abdullah Sheikh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

Sorting Report

Uploaded by

Abdullah Sheikh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

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:
 QuickSort.js
 InsertionSort.js
 HeapSort.js
 CountingSort.js
 Display Folder:
o Frontend.html
o Frontend.css
o Frontend.js

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.

Frontend.html:
This file contains frontend html involved in creating the display.

Frontend.css:
This file contains all the styling for the html file.

Frontend.js:
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:

You might also like