Sorting Algorithms

Sorting algorithms are a fundamental part of computer science. They are used to sort data in a particular order, whether it be in increasing order, or decreasing order.

Bubble Sort

This is a very simple algorithm, it takes a number and compares it with its adjacent neighbor. Let’s say we are sorting the data structure in increasing order… we will start at the beginning and compare the first element to its neighbor. If the second element is larger in numeric value, a swap will be done.

Bubble sort is good for smaller datasets due to its quadratic time complexity of O(n^2), that is for its average case and worst case. Best case time complexity is if the array is already sorted, then it is O(n) time complexity.

This will be very slow for large datasets. Number of comparisons: N-1 comparisons (N = the size of the array)

Insertion Sort

Insertion Sort

Features Of Insertion Sort

Simple and efficient for small datasets, but slow for large datasets

How Insertion Sort Works

Inserts each element from the unsorted portion into its proper position in the sorted portion

Insertion sort is a simple sorting algorithm that works by iterating through a list of elements one by one, inserting each element into its proper position in the sorted portion of the list. It's a bit like organizing a deck of cards, one card at a time!

Insertion sort performs well on small data sets, and nearly sorted datasets. It is not ideal for large datasets that are completely unsorted.

Here's how it works:

  1. Start with an empty sorted list and an unsorted list.
  2. Take the first element from the unsorted list and insert it into the sorted list at the correct position (i.e., in ascending order).
  3. Take the next element from the unsorted list and insert it into the sorted list at the correct position, shifting existing elements to make room if necessary.
  4. Repeat step 3 until the entire unsorted list has been inserted into the sorted list.

Insertion sort has a time complexity of O(n^2), making it less efficient than more advanced sorting algorithms like quicksort or mergesort. However, it's simple to implement and works well for small lists or lists that are nearly sorted to begin with.