Last modified: September 20, 2024

This article is written in: 🇺🇸

Sorting

In the realm of computer science, 'sorting' refers to the process of arranging a collection of items in a specific, predetermined order. This order is based on certain criteria that are defined beforehand.

For instance:

Sorting isn't limited to just numbers and strings. Virtually any type of object can be sorted, provided there is a clear definition of order for them.

Stability in Sorting

Stability, in the context of sorting, refers to preserving the relative order of equal items in the sorted output. In simple terms, when two items have equal keys:

Sure, let's use an example with characters and their indices to illustrate both stable and unstable sorting.

Example

Consider the following pairs of characters and their indices:

[A0] [C1] [B2] [A3] [B4]

Stable Sort

When we sort these pairs alphabetically by character using a stable sorting method, pairs with the same character retain their original order in terms of indices.

I. Sort the character 'A':

[A0] [A3] [C1] [B2] [B4]

II. Next, sort the character 'B', retaining the original order of indices:

[A0] [A3] [B2] [B4] [C1]

So, the stable sorted sequence is:

[A0] [A3] [B2] [B4] [C1]

Unstable Sort

When we sort these pairs alphabetically by character using an unstable sorting method, pairs with the same character may not retain their original order in terms of indices.

I. Sort the character 'A':

[A3] [A0] [C1] [B2] [B4]

II. Next, sort the character 'B', without retaining the original order of indices:

[A3] [A0] [B4] [B2] [C1]

So, the unstable sorted sequence is:

[A3] [A0] [B4] [B2] [C1]

This characteristic is particularly valuable in scenarios where we might perform multiple rounds of sorting based on different criteria.

Bubble Sort

Bubble sort, one of the simplest sorting algorithms, is often a go-to choice for teaching the foundational concepts of sorting due to its intuitive nature. The name "bubble sort" stems from the way larger elements "bubble up" towards the end of the array, much like how bubbles rise in a liquid.

Conceptual Overview

Imagine a sequence of numbers. Starting from the beginning of the sequence, we compare each pair of adjacent numbers and swap them if they are out of order. As a result, at the end of the first pass, the largest number will have "bubbled up" to the last position. Each subsequent pass ensures that the next largest number finds its correct position, and this continues until the whole array is sorted.

Steps

  1. Start from the first item and compare it with its neighbor to the right.
  2. If the items are out of order (i.e., the left item is greater than the right), swap them.
  3. Move to the next item and repeat the above steps until the end of the array.
  4. After the first pass, the largest item will be at the last position. On the next pass, you can ignore the last item and consider the rest of the array.
  5. Continue this process for n-1 passes to ensure the array is completely sorted.

Optimizations

An important optimization for bubble sort is to keep track of whether any swaps were made during a pass. If a pass completes without any swaps, it means the array is already sorted, and there's no need to continue further iterations.

Stability

Bubble sort is stable. This means that two objects with equal keys will retain their relative order after sorting. Thus, if you had records sorted by name and then sorted them using bubble sort based on age, records with the same age would still maintain the name order.

Time Complexity

Space Complexity

$(O(1))$ - It sorts in place, so it doesn't require any additional memory beyond the input array.

Selection Sort

Selection sort is another intuitive algorithm, widely taught in computer science curricula due to its straightforward mechanism. The crux of selection sort lies in repeatedly selecting the smallest (or largest, depending on the desired order) element from the unsorted section of the array and swapping it with the first unsorted element.

Conceptual Overview

Consider an array of numbers. The algorithm divides the array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted subarray is empty, while the entire array is unsorted. During each pass, the smallest element from the unsorted subarray is identified and then swapped with the first unsorted element. As a result, the sorted subarray grows by one element after each pass.

Steps

  1. Assume the first element is the smallest.
  2. Traverse the unsorted subarray and find the smallest element.
  3. Swap the found smallest element with the first element of the unsorted subarray.
  4. Move the boundary of the sorted and unsorted subarrays one element to the right.
  5. Repeat steps 1-4 until the entire array is sorted.

Stability

Selection sort is inherently unstable. When two elements have equal keys, their relative order might change post-sorting. This can be problematic in scenarios where stability is crucial.

Time Complexity

Space Complexity

$(O(1))$ - The algorithm sorts in-place, meaning it doesn't use any extra space beyond what's needed for the input.

Implementation

Insertion Sort

Insertion sort works much like how one might sort a hand of playing cards. It builds a sorted array (or list) one element at a time by repeatedly taking one element from the input and inserting it into the correct position in the already-sorted section of the array. Its simplicity makes it a common choice for teaching the basics of algorithm design.

Conceptual Overview

Imagine you have a series of numbers. The algorithm begins with the second element (assuming the first element on its own is already sorted) and inserts it into the correct position relative to the first. With each subsequent iteration, the algorithm takes the next unsorted element and scans through the sorted subarray, finding the appropriate position to insert the new element.

Steps

  1. Start at the second element (index 1) assuming the element at index 0 is sorted.
  2. Compare the current element with the previous elements.
  3. If the current element is smaller than the previous element, compare it with the elements before until you reach an element smaller or until you reach the start of the array.
  4. Insert the current element into the correct position so that the elements before are all smaller.
  5. Repeat steps 2-4 for each element in the array.

Stability

Insertion sort is stable. When two elements have equal keys, their relative order remains unchanged post-sorting. This stability is preserved since the algorithm only swaps elements if they are out of order, ensuring that equal elements never overtake each other.

Time Complexity

Space Complexity

$(O(1))$ - This in-place sorting algorithm doesn't need any additional storage beyond the input array.

Implementation

Quick Sort

Quick Sort, often simply referred to as "quicksort", is a divide-and-conquer algorithm that's renowned for its efficiency and is widely used in practice. Its name stems from its ability to sort large datasets quickly. The core idea behind quicksort is selecting a 'pivot' element and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then recursively applied to the sub-arrays.

Conceptual Overview

  1. The first step is to choose a pivot from the array, which is the element used to partition the array. The pivot selection method can vary, such as picking the first element, the middle element, a random element, or using a more advanced approach like the median-of-three.
  2. During partitioning, the elements in the array are rearranged so that all elements less than or equal to the pivot are placed before it, and all elements greater than the pivot are placed after it. At this point, the pivot reaches its final sorted position.
  3. Finally, recursion is applied by repeating the same process for the two sub-arrays: one containing elements less than the pivot and the other containing elements greater than the pivot.

Steps

  1. Choose a 'pivot' from the array.
  2. Partition the array around the pivot, ensuring all elements on the left are less than the pivot and all elements on the right are greater than it.
  3. Recursively apply steps 1 and 2 to the left and right partitions.
  4. Repeat until base case: the partition has only one or zero elements.

Stability

Quick sort is inherently unstable due to the long-distance exchanges of values. However, with specific modifications, it can be made stable, although this is not commonly done.

Time Complexity

Space Complexity

$(O(\log n))$ - Though quicksort sorts in place, it requires stack space for recursion, which in the best case is logarithmic.

Implementation

Heap sort

Heap Sort is a comparison-based sorting technique performed on a binary heap data structure. It leverages the properties of a heap to efficiently sort a dataset. The essential idea is to build a heap from the input data, then continuously extract the maximum element from the heap and reconstruct the heap until it's empty. The result is a sorted list.

Conceptual Overview

  1. The first step is to build a max heap, which involves transforming the list into a max heap (a complete binary tree where each node is greater than or equal to its children). This is typically achieved using a bottom-up approach to ensure the heap property is satisfied.
  2. During sorting, the maximum element (the root of the heap) is swapped with the last element of the unsorted portion of the array, placing the largest element in its final position. The heap size is then reduced by one, and the unsorted portion is restructured into a max heap. This process continues until the heap size is reduced to one, completing the sort.

Steps

  1. Construct a max heap from the given data. This will place the largest element at the root.
  2. Swap the root (maximum value) with the last element of the heap. This element is now considered sorted.
  3. Decrease the heap size by one (to exclude the sorted elements).
  4. "Heapify" the root of the tree, i.e., ensure the heap property is maintained.
  5. Repeat steps 2-4 until the size of the heap is one.

Stability

Heap sort is inherently unstable. Similar to quicksort, the relative order of equal items is not preserved because of the long-distance exchanges.

Time Complexity

Space Complexity

$(O(1))$ - The sorting is done in-place, requiring only a constant amount of space for variables, regardless of the input size.

Implementation

Table of Contents

    Sorting
    1. Stability in Sorting
      1. Example
      2. Stable Sort
      3. Unstable Sort
    2. Bubble Sort
      1. Conceptual Overview
      2. Steps
      3. Optimizations
      4. Stability
      5. Time Complexity
      6. Space Complexity
    3. Selection Sort
      1. Conceptual Overview
      2. Steps
      3. Stability
      4. Time Complexity
      5. Space Complexity
      6. Implementation
    4. Insertion Sort
      1. Conceptual Overview
      2. Steps
      3. Stability
      4. Time Complexity
      5. Space Complexity
      6. Implementation
    5. Quick Sort
      1. Conceptual Overview
      2. Steps
      3. Stability
      4. Time Complexity
      5. Space Complexity
      6. Implementation
    6. Heap sort
      1. Conceptual Overview
      2. Steps
      3. Stability
      4. Time Complexity
      5. Space Complexity
      6. Implementation