basecs
Published in

basecs

Sorting Out The Basics Behind Sorting Algorithms

All of the sorting algorithms, without any of the debilitating fear!

Why sort oneself out?

Sorting is particularly useful for two reasons
  1. From a strictly human-friendly perspective, it makes a single dataset a whole lot easier to read.
  2. It makes it easier to implement search algorithms in order to find or retrieve an item from the entire dataset.
Sorted lists are permutations of their original lists
  • We can sort a collection of items in either increasing or decreasing order by any one property, and that property by can really be anything. By size, lexicographical (alphabetical) order, numerical order, date, time — you name it!
  • We can only sort a dataset where the items are homogeneous, or are of the same type. In other words, we couldn’t sort a dataset with both words and numbers, because that dataset doesn’t have a shared property that we could actually sort by.
Life without sorting?
Life with sorting!

All sorts of classifications

Different ways to classify a sorting algorithm

1. Time complexity

Time complexity

2. Space complexity/memory usage

Space complexity

3. Stability

Stability

4. Internal vs. external

Internal vs. external

5. Recursive or non-recursive

Recursive vs. non-recursive

6. Comparison sort

Comparison sort

Sorting, sorting, everywhere you look!

Sorted data powers (almost) everything!
Common sorting algorithms that we’ll be learning about!

Resources

  1. Non-Comparison Based Sorting Algorithms, Professor Ananda Gunawardena
  2. Data Structure — Sorting Techniques, TutorialsPoint
  3. Sorting Algorithms, Professor Victor S. Adamchik
  4. Sorting Algorithms — Stability, University of Illinois at Chicago, Department of Mathematics, Statistics, and Computer Science
  5. Sorting Applications, Professors Robert Sedgewick & Kevin Wayne
  6. Introduction to sorting algorithms, mycodeschool

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store