📖
Wiki
Back to my personal website
  • Home
  • Equipment and Devices
    • 3D Printer
    • Laser Cutter
    • Motion Capture System
    • Sensors
      • RGB-D Cameras
      • Velodyne LiDAR
      • Zed Camera
      • RealSense D435i
      • IMU
    • eGPU
    • Nvidia AGX Xavier
    • CPU Benchmark
    • Installation Checklist
  • Development
    • Linux
      • Shell
      • GDB
      • Git
      • Tmux
      • Network
      • Tricks
      • Debug FAQ
    • CMake
      • Catkin Tools
      • CMakeLists
      • CMake Variables
      • CMake Commands
      • CMake: find_package()
    • ROS
      • Gazebo
      • wstool
      • roslaunch
      • rosbag
      • multi-threaded spinner
    • ROS2
      • Convert ROS1 bag to ROS2 bag
    • C++
      • C++ 11
      • C++ Examples
      • C++ Debug
      • Factory Method
      • Timing
    • Google Tools
      • GLog
      • GFlags
      • GTest
      • Style Guide
      • Clang Format
    • PCL
      • Point Type
      • Methods
      • Architecture
      • Code Explained
    • Open3D
      • Python API
      • Registration
      • Visualization
      • Tools
    • OpenCV
      • Documentation
      • Modules
    • Other Libraries
      • Eigen
      • Ceres
      • g2o
      • GTSAM
    • Website
  • Algorithm
    • SLAM
      • K-D Tree
      • Octree
      • Bag of Words
      • Distance Measures
      • Coordinate Systems
      • LOAM
      • Iterative Closest Point
      • Generalized ICP
      • Mahalanobis Distance
    • Computer Science
      • Computational Model
      • Sorting
      • Analysis
      • Complexity Classes (P, NP)
      • Divide and Conquer
      • Greedy Algorithm
      • Dynamic Programming
      • Tree
      • Graph
    • Computer Vision
      • Camera Models
      • Distortion
      • Motion Models
      • Shutter
      • Image Sensors
      • Epipolar Geometry
      • Multiple-View Geometry
    • Datasets
      • RGB-D Datasets
      • Point Cloud Datasets
      • LiDAR SLAM Datasets
  • Math
    • Optimization
      • Convex Optimization
      • Descent Methods
    • Probability
      • Moment
      • Covariance Matrix
      • Stochastic Process
    • Topology
      • References
      • Concepts
      • Topological Spaces
      • Representation of Rotations
      • Representation of 3-sphere
    • Algebra
      • Linear Algebra
      • Matrix Factorization
      • Condition Number
      • Matrix Lie Group
    • Differential Geometry
      • Manifold
      • Submanifold
      • Quotient Manifolds
      • Tangent Space
  • Quadrotor
    • PX4 Development
    • Companion Computer
    • Drone Hardware
    • Propeller Lock
    • Debug
  • Favorites
    • Bookmarks
Powered by GitBook
On this page
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Introsort
  • Timsort
  • Distribution Sort
  • Topological Sort
  • Tree Sort

Was this helpful?

  1. Algorithm
  2. Computer Science

Sorting

Selection Sort

  • О(n^2) comparisons, О(n) swaps

  • naive implementation for sorting

Insertion Sort

  • О(n^2) comparisons and swaps

  • O(1) auxiliary space

  • can run online

  • stable

Merge Sort

  • O(n log(n)) by divide and conquer

  • O(n) auxiliary space

  • stable; deterministic

Quick Sort

  • O(n log(n)) by divide and conquer; worst case O(n) though

  • O(1) auxiliary space; one of exchange sorts (cf. bubble sort)

  • unstable; randomized

Introsort

  • hybrid sorting algorithm

  • derived from quicksort, heapsort, and insertion sort

  • unstable

Timsort

  • hybrid sorting algorithm

  • derived from merge sort and insertion sort

  • stable

Distribution Sort

  • O(n+m) non-comparative sorting algorithms: radix sort, bucket sort, digital sort, pigeonhole sort

  • it avoids comparison by creating and distributing elements into buckets according to their radix

  • the lower bound for comparative sorting algorithm is O(n log(n)); in certain cases, non-comparative sorting can do better, e.g., O(n)

Topological Sort

  • for directed acyclic graph (DAG)

  • output a linear ordering of its vertices

Tree Sort

  • builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.

  • Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.

PreviousComputational ModelNextAnalysis

Last updated 3 years ago

Was this helpful?