CSC 326 Group Project

Sorting Algorithms

Sameer Jain , Ahmed Hamza , Alex Putman

Bubble Sort

Time Complexity:

Best:O(n)

Avg : O(n^2)

Worst: O(n^2)

​

Space Complexity: O(1)

​

Insertion Sort

Time Complexity:

Best:O(n)

Avg : O(n^2)

Worst: O(n^2)

​

Space Complexity: O(1)

​

Selection Sort

Time Complexity:

Best:O(n^2)

Avg : O(n^2)

Worst: O(n^2)

​

Space Complexity: O(1)

​

Merge Sort

Time Complexity:

Best:O(nlog(n))

Avg : O(nlog(n))

Worst: O(nlog(n))

​

Space Complexity: O(n)

​

Merge Function

Merge Insertion Sort

Time Complexity:

O(nlog(n)) when greater than switch, O(n^2) for less than switch

​

Space Complexity: O(n)

​

(Same Merge Function)

​

Heap Sort

Time Complexity:

Best:O(nlog(n))

Avg : O(nlog(n))

Worst: O(nlog(n))

​

Space Complexity: O(1)

​

Max Heap

​

Quick Sort

Time Complexity:

Best:O(nlog(n))

Avg : O(nlog(n))

Worst: O(n^2)

​

Space Complexity

(Worst): O(1)

​

Hoarse vs Lamuto

Examples of Reverse Versions (Largest to Smallest)

Counting Steps

Process:

​

1. Generate Random New Array of Size N

​

• Copy it into global vector

​

• Run Function for getting time

​

• Re-Randomize Array using

Global vector

​

• Repeat for finding steps, reverse algorithms and all 8

Data Set Sizes

​

​

​

Running the experiments

Function that takes in other functions as an Argument

Generating Random Arrays

Avg of time and steps

​

In whole project:

Total Functions:61

Lines of Code : ~2,000

Our Headers.cpp

Running the experiments

Replit and excel/word files

https://replit.com/join/fnzdhtbkqd-sameerjain501

​

Data:

(Task 1):

https://docs.google.com/spreadsheets/d/1vWTPmyX2VwndZPcjbfmm-3cxkEMoKYH00fI44v1fscg/edit?usp=sharing

​

(Task 2):

https://docs.google.com/spreadsheets/d/1BKbo1bFIx7Ax6Nh3gNtErdYFnpNI6KYakWHr2gB0T3Y/edit#gid=0

​

Extra Credit:

https://docs.google.com/document/d/17Lij8m9aCdy6pfZsVb2XFLZwU8hHg1_9sIcTJ4ZaOIY/edit

​

​