Giter VIP home page Giter VIP logo

volsort's Introduction

Volsort

CS302 - Project 2

Jonathan Ting

Professor Emrich

COSC 302

Due 6 February 2019

Project 2

Overview: Sorts input either by string or numerically using either stl::sort, qsort, custom merge sort, or custom quick sort.

Github: https://github.com/jonting/Volsort

  1. Range of integers is 0 to (number of integers * 2)
Numerical Mode Size Elapsed Time (ms)
No STL 10 2
No STL 100 2
No STL 1000 4
No STL 10000 28
No STL 100000 385
No STL 1000000 8940
No STL 10000000 93207
Yes STL 10 2
Yes STL 100 2
Yes STL 1000 4
Yes STL 10000 27
Yes STL 100000 292
Yes STL 1000000 7376
Yes STL 10000000 84914
No QSORT 10 2
No QSORT 100 2
No QSORT 1000 4
No QSORT 10000 27
No QSORT 100000 288
No QSORT 1000000 6497
No QSORT 10000000 89242
Yes QSORT 10 2
Yes QSORT 100 2
Yes QSORT 1000 4
Yes QSORT 10000 25
Yes QSORT 100000 257
Yes QSORT 1000000 6285
Yes QSORT 10000000 73828
No MERGE 10 2
No MERGE 100 2
No MERGE 1000 4
No MERGE 10000 26
No MERGE 100000 280
No MERGE 1000000 6138
No MERGE 10000000 79639
Yes MERGE 10 2
Yes MERGE 100 2
Yes MERGE 1000 4
Yes MERGE 10000 25
Yes MERGE 100000 262
Yes MERGE 1000000 5044
Yes MERGE 10000000 76138
No QUICK 10 2
No QUICK 100 2
No QUICK 1000 4
No QUICK 10000 28
No QUICK 100000 320
No QUICK 1000000 6176
No QUICK 10000000 96193
Yes QUICK 10 2
Yes QUICK 100 2
Yes QUICK 1000 4
Yes QUICK 10000 26
Yes QUICK 100000 295
Yes QUICK 1000000 5760
Yes QUICK 10000000 90532
a. Each sort is around the same for 10-10000 entries. For most cases past 10000 entries, quick sort is fastest with qsort as second fastest.
   Quicksort is closer to merge sort in the 1000000 entries range and stl is slowest in the 10000-1000000 entries range, however quicksort is also slowest in the 10000000 entries range.
   Merge sort is generally fastest due to the efficiency of the algorithm, along with qsort.
   Quicksort is fairly fast due to the algoritm but is slower in the very large entry amounts possibly due to my different implementation, where it may still rotate old pivots.
   STL sort is generally the slowest, probably because of more overhead as it needs to be applicable to more usages.
   Numerical sort is always faster than non-numerical sort.

b. Actual performance is very reliant on the implementation and also the amount of entries. For example, quick sort is fast in the middle size entries but worst in the very large entries.
   The average case vs. worst case complexities actually reflect that reality in quicksort, where the very large entries is arguably a worst case complexity.

c. Merge sort is the best. It has the fastest time in all the size categories. It appears to have no trade offs, but that might be due to an imperfect quicksort implementation.
   Normally, quick sort would be faster in the mid-range entries.
  1. Since I was the only member of my team, I performed all the planning, coding, testing, and commenting.

volsort's People

Contributors

j-thy avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.