Click here to Skip to main content
15,030,355 members
Articles / General Programming / Performance
Technical Blog
Posted 19 Jul 2021

Stats

4.5K views
6 bookmarked

Comparison of Sorting Algorithms

Rate me:
Please Sign up or sign in to vote.
3.67/5 (7 votes)
19 Jul 2021CPOL7 min read
Welcome to our Comparison on Sorting Algorithms Article. Here, we'll be comparing the various sorting Algorithms out there on the basic of several factors.
  • Time Complexity
  • Space Complexity
  • Stable/Unstable
  • Actual Fields Tests

We’ll top it all of by trying to describe where each Algorithm is best suited, and their strong and weak points. Every Algorithm is unique, and performs best under certain circumstances unique to it.

Comparison of Time Complexity

A table that show’s the time complexities for some of the most commonly used Sorting Algorithms. Time complexity is the first thing that you need to be checking when comparing two sorting algorithms. The lower the time complexity, the better.

Sorting Algorithm Average Case Best Case Worst Case
Bubble Sort O(n2) O(n) O(n2)
Insertion Sort O(n2) O(n) O(n2)
Selection Sort O(n2) O(n2) O(n2)
Quick Sort O(n.log(n)) O(n.log(n)) O(n2)
Merge Sort O(n.log(n)) O(n.log(n)) O(n.log(n))
Heap Sort O(n.log(n)) O(n.log(n)) O(n.log(n))
Counting Sort O(n+k) O(n+k) O(n+k)
Radix Sort O(n*k) O(n*k) O(n*k)
Bucket Sort O(n+k) O(n+k) O(n2)

We’ve used a color scheme in the table above, to help with our Comparison of Sorting Algorithms. Red is the worst, under which the O(n2) Algorithms lie. The O(n.log(n)) Algorithms are next, which are the middle ground. The best time complexity is O(n), which is the fastest Algorithm can be.

Later when we do the actual field tests, you can use this table as reference. You will notice how much of an impact time complexity has on performance.

Comparison of Space Complexity

While speed is important and usually your top priority, sometimes in places with memory constraints, Algorithms with low memory costs are preferred.

The below table shows the Space Complexity for the various Sorting Algorithms. You might notice, that the Algorithms with higher space complexities are those which are “out of place” and the ones with the lowest, are in-place. This is of course, because Out of Place Algorithms create extra arrays to store the data in, while In-place uses the same array.

It goes without saying, that the best Space Complexity is O(1).

Sorting Algorithm Space Complexity
Bubble Sort O(1)
Insertion Sort O(1)
Selection Sort O(1)
Quick Sort O(log(n))
Merge Sort O(n)
Heap Sort O(1)
Counting Sort O(k)
Radix Sort O(n + k)
Bucket Sort O(n)

Stable and Unstable Algorithms

This is a rather niche use, and only makes an actual difference in certain types of data. However, it remains an important requirement that is needed for these certain scenarios.

Sorting Algorithm Stable Sort?
Bubble Sort Yes
Insertion Sort Yes
Selection Sort No
Quick Sort No
Merge Sort Yes
Heap Sort No
Counting Sort Yes
Radix Sort Yes
Bucket Sort Yes

Is it important to note however, that you can usually create stable versions of the above Algorithms. The ones being referred to in the image above, are the “Classic” versions of the Algorithm.

You can also check out our YouTube series on Sorting Algorithms!

Sorting Algorithms – Fields Tests

Finally, we are going to be measuring the main component, performance. We have tested the 9 Algorithms featured here under a variety of circumstances. From 100 numbers to 10,000 as well as tests using already sorted data, these tests will reveal quite a bit.

Testing Method

I’ve used Google Collab for running these tests, to ensure a constant and fair testing environment. To be clear, the code for these Sorting Algorithms was written in Python and written in a fairly standard manner. No heavy optimizations were applied, and only standard (classic) versions of the Algorithms were used.

The Python timeit and random library were used to generate the random data, and perform continuous and repeated tests for each Algorithm. This is again, to ensure fair results. The Random library is used to generate numbers from 1 to 10,000 and the timeit library performs each test 5 times in total, and returns a list of all 5 times. We’ve displayed both the max and min values for the 5 tests, so you can see the displacement of times.

Each one of the 5 tests is actually running the code 10 times, (the number parameter, default value 1,000,000). This increases the accuracy by doing alot of tests and adding together the values to average it out. If you want the individual time for one single sort, divide the min/max value by 10. The number of repetitions is controlled by the repeat parameter (default value 5).

You can see the code for the testing function in the code below. If you follow the links for the timeit and random library, you can learn more about what’s going on here.

Python
import random
import timeit
import sys

def test():
  SETUP_CODE = '''
from __main__ import sort
from random import randint'''
  
  TEST_CODE = '''
array = []
for x in range(1000):
  array.append(x)
sort(array)
  '''
  times = timeit.repeat( setup = SETUP_CODE,
                          stmt = TEST_CODE,  
                          number = 10,
                          repeat = 5) 

  print('Min Time: {}'.format(min(times)))
  print('Max Time: {}'.format(max(times)))

Sorting Algorithms – Performance Comparison

In this section, we are going to conduct three sets of tests. The first will have 100 random numbers, the second will have 1000 and the third will have 10,000. Take a good look at the table, compare the time complexities, and make your own observations. I’ll share my observations right after this.

Sorting Algorithm Test 1 (100) Test 2 (1000) Test 3 (10000)
Bubble Sort Min: 0.01008 seconds
Max: 0.0206 seconds
Min: 1.0242 seconds
Max: 1.0558 seconds
Min: 100.922 seconds
Max: 102.475 seconds
Insertion Sort Min: 0.00306 seconds
Max: 0.00650 seconds
Min: 0.0369 seconds
Max: 0.0562 seconds
Min: 100.422 seconds
Max: 102.344 seconds
Selection Sort Min: 0.00556 seconds
Max: 0.00946 seconds
Min: 0.4740 seconds
Max: 0.4842 seconds
Min: 40.831 seconds
Max: 41.218 seconds
Quick Sort Min: 0.00482 seconds
Max: 0.01141 seconds
Min: 0.0370 seconds
Max: 0.0383 seconds
Min: 0.401 seconds
Max: 0.420 seconds
Merge Sort Min: 0.00444 seconds
Max: 0.00460 seconds
Min: 0.0561 seconds
Max: 0.0578 seconds
Min: 0.707 seconds
Max: 0.726 seconds
Heap Sort Min: 0.00489 seconds
Max: 0.00510 seconds
Min: 0.0704 seconds
Max: 0.0747 seconds
Min: 0.928 seconds
Max: 0.949 seconds
Counting Sort Min: 0.01929 seconds
Max: 0.02052 seconds
Min: 0.0354 seconds
Max: 0.0400 seconds
Min: 0.195 seconds
Max: 0.203 seconds
Radix Sort Min: 0.00315 seconds
Max: 0.00394 seconds
Min: 0.0294 seconds
Max: 0.0309 seconds
Min: 0.313 seconds
Max: 0.338 seconds
Bucket Sort Min: 0.00225 seconds
Max: 0.00241 seconds
Min: 0.0335 seconds
Max: 0.0369 seconds
Min: 1.854 seconds
Max: 1.892 seconds

I wanted to also include tests for 100,000 and 1,000,000 numbers, but the O(n2) Algorithms were taking forever to complete, so I gave up.

Observations

  1. The O(n2) Algorithms (Bubble and Insertion Sort) reacted very poorly as the number of tests went up to 10,000. At 10,000 numbers the other Algorithms were on average, over 100x times faster.
  2. On the test cases with just 100 numbers, the O(n2) Algorithms were faster than the O(n.log(n)) Algorithms.
  3. With every 10x increase in the amount of numbers, the O(n2) Algorithms completion time increased by 100x.
  4. Radix Sort and Counting Sort were on average, the fastest Algorithms.
  5. Heapsort is fastest Algorithm with a space complexity of O(1).

Sorted Data Comparison

Another very interesting case is when Sorted Data is used, instead of random data. This test is mainly to show which Sorting Algorithms perform with sorted/partially sorted data and which perform worse.

Sorting Algorithm Sorted Data (1000)
Bubble Sort Min: 0.542 seconds
Max: 0.556 seconds
Insertion Sort Min: 0.790 seconds
Max: 0.821 seconds
Selection Sort Min: 0.434 seconds
Max: 0.464 seconds
Quick Sort Min: 0.812 seconds
Max: 0.872 seconds
Merge Sort Min: 0.0289 seconds
Max: 0.0364 seconds
Heap Sort Min: 0.0604 seconds
Max: 0.0661 seconds
Counting Sort Min: 0.0055 seconds
Max: 0.0124 seconds
Radix Sort Min: 0.0119 seconds
Max: 0.0145 seconds
Bucket Sort Min: 0.0183 seconds
Max: 0.0247 seconds

Observations

  1. Surprise, Surprise. Quick Sort Algorithm doesn’t live up to it’s name, and is the slowest out of all the above algorithms for a 1000 sorted numbers. This is because Quick Sort doesn’t respond well to degenerate cases like this, and requires special optimizations such as “randomized pivots”.
  2. With the exception of Quick Sort, the time required dropped for all Algorithms.
  3. Counting Sort performs the best, followed by Radix and Bucket Sort.

This marks the end of the Sorting Algorithms Comparison article. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.

The post Comparison of Sorting Algorithms appeared first on CodersLegacy.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

The Sun God
United States United States
No Biography provided

Comments and Discussions

 
QuestionBad testing Pin
Member 1159380820-Jul-21 9:33
MemberMember 1159380820-Jul-21 9:33 
QuestionPlagiarized ? Pin
Patrice T20-Jul-21 8:25
mvePatrice T20-Jul-21 8:25 
AnswerRe: Plagiarized ? Pin
The Sun God20-Jul-21 22:39
MemberThe Sun God20-Jul-21 22:39 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA20-Jul-21 1:17
professionalȘtefan-Mihai MOGA20-Jul-21 1:17 
QuestionThere's also this Pin
Marc Clifton19-Jul-21 7:58
mvaMarc Clifton19-Jul-21 7:58 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.