Tag: sorting-algorithm

tag for sorting algorithm

Radix Sort

Imagine sorting a pile of coins. Instead of comparing values directly, Radix Sort separates them based on the value of their least significant digit (like separating pennies from nickels). Then, it refines further by the next digit, like sorting nickels by their second digit. This intuitive, digit-by-digit approach leads to a beautifully sorted pile.

Process

Radix Sort, as the name suggests, takes inspiration from how we read numbers: digit by digit. Instead of complex comparisons, it sorts data by analyzing individual digits, making it particularly efficient for numbers or strings with fixed lengths. Let’s embark on this digit-by-digit sorting journey:

1. Digit Dive: Imagine a bucket brigade, where each bucket represents a possible value for a specific digit (0-9 in most cases). Radix Sort starts by analyzing the least significant digit (LSD) of each element. It then iterates through the data, throwing each element into the bucket corresponding to its LSD value.

2. Bucket Brigade: Now, each bucket holds elements with the same LSD. Radix Sort processes each bucket independently, potentially using another sorting technique like counting sort within each bucket. This ensures all elements within a bucket share the same LSD and are partially sorted.

3. Refining Order: Once all buckets are processed, it’s time for the next digit! Radix Sort shifts its focus to the second least significant digit (SLSD) and repeats the bucket brigade process. Now, elements are further sorted based on their SLSD within each bucket, refining the overall order.

4. Digit March: This digit-by-digit sorting continues, working its way up to the most significant digit (MSD). With each pass, the buckets contain increasingly refined groups of elements, and the overall order becomes clearer.

5. Final Assembly: After processing the MSD, all elements are finally in their correct positions within the main array. Radix Sort gathers them back from the buckets, resulting in a beautifully sorted list!

Pseudo Code

Code
function radixSort(array, d):
  # d is the maximum number of digits (adjust based on your data)
  # Create an empty array of buckets (0-9 in each bucket)
  buckets = [[None] * 10 for _ in range(d)]

  # Perform passes for each digit from LSD to MSD
  for digit in range(d):
    # Distribute elements into buckets based on their digit at the current position
    for num in array:
      digitValue = (num // 10**digit) % 10  # Extract the current digit
      buckets[digitValue].append(num)

    # Gather elements back from buckets in order
    arrayIndex = 0
    for bucket in buckets:
      for num in bucket:
        array[arrayIndex] = num
        arrayIndex += 1

      # Clear the bucket for the next iteration
      bucket[:] = []

  # Return the sorted array
  return array
Explanation
  1. radixSort: This function takes the array to be sorted and the maximum number of digits (d) as input.
  2. buckets: This array stores 10 sub-arrays, representing buckets for each possible digit (0-9).
  3. digit loop: This loop iterates through each digit position, from least significant (LSD) to most significant (MSD).
  4. Distributing elements: For each element in the array, its digit at the current digit position is extracted, and the element is placed in the corresponding bucket.
  5. Gathering elements: After processing all elements for the current digit, the function iterates through each bucket and gathers the elements back into the main array in the order they appear in the buckets.
  6. Clearing buckets: The buckets are cleared after each iteration to prepare for the next digit.
  7. Return: The sorted array is returned.

Implementation

Kotlin

Golang

Counting Sort

Imagine having a box of mixed socks. Instead of painstakingly comparing each pair, Counting Sort counts the number of socks of each color, allowing you to instantly identify the most frequent (or least frequent) colors, creating order from chaos.

Process

Imagine a messy room overflowing with toys. While other sorting algorithms might meticulously compare each toy, Counting Sort takes a different approach: it counts! Yes, that’s right, it leverages the power of counting to bring order to chaos. Let’s delve into the steps:

1. Counting the Crew: First, Counting Sort creates a temporary array, one slot for each unique value (color, size, type) your toys might have. Then, it iterates through your room (data), patiently counting how many toys belong to each category (value). So, all the red cars get a tally in the “red car” slot, and so on.

2. Calculating Positions: With the popularity (count) of each value known, Counting Sort does some clever math. It calculates the starting position in the final sorted array for each value based on its count and the counts of previous values. Think of it as figuring out how much space each toy category deserves in the organized closet (final array).

3. Placing the Toys (Data): Finally, it’s time to put things away! Counting Sort goes back to your messy room (data) and visits each toy (element) one by one. Based on the toy’s value, it uses the calculated position from step 2 to place it in the correct spot in the final sorted array. It’s like having a map that tells you exactly where each toy belongs!

Pseudo Code

Code
function countingSort(array):
  # Find the maximum element in the array
  max_value = findMax(array)

  # Create a count array to store the frequency of each element
  count_array = [0] * (max_value + 1)

  # Count the occurrences of each element
  for i in range(len(array)):
    count_array[array[i]] += 1

  # Calculate the cumulative sum of the count array
  for i in range(1, len(count_array)):
    count_array[i] += count_array[i - 1]

  # Create the output array
  output_array = [0] * len(array)

  # Place elements in the output array based on their counts
  for i in range(len(array) - 1, -1, -1):
    output_array[count_array[array[i]] - 1] = array[i]
    count_array[array[i]] -= 1

  # Return the sorted array
  return output_array

# Function to find the maximum element
function findMax(array):
  max_value = array[0]
  for i in range(1, len(array)):
    if array[i] > max_value:
      max_value = array[i]
  return max_value
Explanation
  1. findMax: This function finds the maximum element in the array, which determines the size of the count_array.
  2. count_array: This array stores the count of each element. Each index represents a possible value, and the value at that index represents how many times that value appears in the original array.
  3. Counting occurrences: The loop iterates through the original array, incrementing the corresponding element in the count_array for each occurrence.
  4. Cumulative sum: This loop calculates the cumulative sum of the count_array. This means that each element at index i in the count_array now represents the starting position for elements with that value in the final sorted array.
  5. output_array: This is where the sorted elements will be placed.
  6. Placing elements: The loop iterates through the original array in reverse order. For each element, it uses its value to find its corresponding count in the count_array. This count indicates the correct position in the output_array, and the element is placed there. After placing, the count for that element is decremented to ensure correct placement of subsequent occurrences.
  7. Return: The sorted array is returned.

Implementation

Kotlin

Golang

Heap Sort

Think of building a sandcastle and carefully placing each handful of sand to get the highest, perfect cone. Heap Sort works similarly, arranging data like a pyramid, ensuring the “biggest” (or “smallest”, depending on sorting order) element is always on top.

Process

Heap Sort, as the name suggests, involves creating and manipulating a special data structure called a heap to achieve sorted results. But don’t worry, you don’t need actual shovels and sandcastles for this! Let’s delve into the steps:

1. Heapify the Data: Imagine your data as a pile of pebbles. Heap Sort starts by transforming this pile into a “heap,” which resembles a pyramid-like structure. In this pyramid, the element at the top (the “root”) is always the “biggest” (or “smallest,” depending on the sorting order). Elements are carefully arranged based on their values to maintain this property.

2. Extract the “Biggest” Pebble: Just like picking the biggest pebble for your sandcastle, Heap Sort removes the element at the root (the “biggest” in this case) and places it aside. Remember, the heap property ensures this is indeed the largest element!

3. Maintain the Heap: But removing the top pebble disrupts the heap’s structure. Fear not! Heap Sort employs a clever technique called sifting. It replaces the empty root position with another element from the heap and “sifts” it down until the heap property is restored, ensuring the new root is indeed the “biggest.”

4. Repeat and Conquer: This process of extracting the “biggest” element, sifting, and restoring the heap continues until all elements are processed. By the end, the extracted elements, placed in the order they were removed, form the sorted list!

Pseudo Code

Code
function heapSort(array):
  # Build a max-heap from the input array
  buildMaxHeap(array)

  # Repeatedly extract the root (largest element) and swap it with the last element
  for i in range(len(array) - 1, 0, -1):
    swap(array[0], array[i])
    # Maintain the heap property for the remaining elements
    maxHeapify(array, 0, i)

# Functions for building and maintaining the max-heap

function buildMaxHeap(array):
  # Start from the last non-leaf node and sift downwards
  for i in range(len(array) // 2 - 1, -1, -1):
    maxHeapify(array, i, len(array))

function maxHeapify(array, root, heapSize):
  # Compare the root with its children and swap if necessary
  largest = root
  leftChild = 2 * root + 1
  rightChild = 2 * root + 2

  # Find the largest element among root, left child, and right child
  if leftChild < heapSize and array[leftChild] > array[largest]:
    largest = leftChild
  if rightChild < heapSize and array[rightChild] > array[largest]:
    largest = rightChild

  # Swap the root with the largest element if necessary
  if largest != root:
    swap(array[largest], array[root])
    # Recursively heapify the affected sub-tree
    maxHeapify(array, largest, heapSize)

# Swapping function
function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation
  • The heapSort function takes an array as input.
  • The buildMaxHeap function builds a max-heap from the array, ensuring the element at the root is always the largest.
  • The maxHeapify function maintains the heap property by comparing the root element with its children and swapping if necessary.
  • The main loop of heapSort repeatedly extracts the root (largest element) and swaps it with the last element, reducing the heap size by 1 in each iteration.
  • The maxHeapify function is called again after each swap to maintain the heap property for the remaining elements.
  • The swap function simply exchanges the values of two elements.

Implementation

Kotlin

Golang

Quick Sort: The Speed Demon

Imagine sorting a room full of toys by color. Instead of meticulously comparing each toy, Quick Sort picks one (the “pivot”) and throws it like a ball, creating partitions based on colors “faster than light.” That’s the essence of Quick Sort, partitioning and conquering data with speed and a hint of playful chaos.

Process

Quick Sort, true to its name, lives up to its reputation for speed. But unlike a chaotic mess, its efficiency lies in a well-defined strategy: partitioning and conquering. Let’s delve into the steps of this whirlwind sorting dance:

1. Choose a Pivot: Imagine the data as a group of people waiting in line. Quick Sort picks one person (the pivot) and positions them somewhere in the line. This pivot isn’t random; it can be the first, last, or even a median element.

2. Partition the Line: Now comes the magic! Quick Sort iterates through the line, comparing each person to the pivot. Those shorter than the pivot move to one side, and those taller move to the other. Essentially, the line gets divided into two sections based on the pivot’s height.

3. Conquer and Repeat: But wait, the line isn’t sorted yet! Both the shorter and taller groups, though smaller now, might still be unsorted. So, Quick Sort recursively applies the same “choose-pivot-partition” strategy to each group, further dividing and conquering until each group has only one person (sorted!).

4. Merge and Conquer: Finally, when all groups have just one person (sorted!), Quick Sort meticulously merges them back together in the correct order, ensuring the entire line is now sorted from shortest to tallest (or vice versa, depending on how you define “shorter”).

Pseudo Code

Code
function quickSort(array, start, end):
  # Base case: sub-array with 0 or 1 element is already sorted
  if start >= end:
    return

  # Choose a pivot element (e.g., last element)
  pivot = array[end]

  # Partition the array around the pivot
  partitionIndex = partition(array, start, end, pivot)

  # Recursively sort the sub-arrays before and after the partition
  quickSort(array, start, partitionIndex - 1)
  quickSort(array, partitionIndex + 1, end)

function partition(array, start, end, pivot):
  # Initialize index variables
  i = start - 1
  for j in range(start, end):
    if array[j] <= pivot:
      i += 1
      # Swap elements at i and j
      swap(array[i], array[j])
  # Swap pivot element with element at i + 1 (now the partition index)
  swap(array[i + 1], array[end])
  return i + 1

function swap(a, b):
  # Swap the values of elements a and b
  temp = a
  a = b
  b = temp
Explanation
  1. quickSort(array, start, end): This function takes a sub-array (defined by start and end indices) and sorts it using Quick Sort.
  2. Base case: If the sub-array has 0 or 1 element, it’s already sorted and the function returns.
  3. Choose a pivot: The function selects a pivot element (e.g., the last element).
  4. Partition: The partition function rearranges the array elements:
    • Elements less than or equal to the pivot are moved to the left side.
    • Elements greater than the pivot are moved to the right side.
    • The pivot element is placed at the partition index.
  5. Recursive calls: The function recursively calls itself to sort the sub-arrays before and after the partition, excluding the pivot.
  6. swap(a, b): This function swaps the values of two elements.

Implementation

Kotlin

Golang

Merge Sort

Imagine chopping a messy pile of vegetables into smaller pieces, sorting each pile individually, and then merging them back into a perfectly organized whole. That’s the essence of Merge Sort, dividing, sorting, and conquering data to achieve order.

Process

Merge Sort, unlike its comparison-based counterparts, takes a divide-and-conquer approach, resembling how a ruler conquers territories! Let’s dive into the steps:

1. Divide: Imagine the data as a kingdom waiting to be organized. The king (Merge Sort) divides the kingdom (data) into smaller provinces (sub-lists) of roughly equal size.

2. Conquer: Each province undergoes its own mini-conquest. If a province has only one element (citizen), it’s already sorted! Otherwise, the algorithm recursively divides and conquers each province further, breaking them down into even smaller units until each has only one element.

3. Merge and Rule: Once all provinces are single-element kingdoms, the real merging magic begins. The algorithm starts from the smallest conquered provinces and strategically combines them. Imagine two conquered provinces (sorted sub-lists) merging like neighboring kingdoms, carefully comparing and placing citizens (elements) in their rightful order to form a larger, sorted province.

4. Repeat and Expand: This merging continues, combining two sorted provinces at a time, creating larger and larger sorted territories. It’s like the conquered provinces forming alliances, growing in size and order until the entire kingdom (data) is united under the banner of a single, perfectly sorted list.

Pseudo Code

Code
function mergeSort(array):
  if length(array) <= 1:
    return array

  mid = floor(length(array) / 2)
  left = mergeSort(subarray(array, 0, mid))
  right = mergeSort(subarray(array, mid + 1, length(array)))

  return merge(left, right)

function merge(left, right):
  merged = []
  while length(left) > 0 and length(right) > 0:
    if first element of left <= first element of right:
      append first element of left to merged
      remove first element from left
    else:
      append first element of right to merged
      remove first element from right
  append remaining elements of left to merged
  append remaining elements of right to merged
  return merged

function subarray(array, start, end):
  # Creates a new subarray from the original array with specified start and end indices
  new_array = []
  for i in range(start, end):
    append element at index i of array to new_array
  return new_array
Explanation

mergeSort(array):

  • if length(array) <= 1: If the array has only one element or less, it’s already considered sorted and returned as-is.
  • mid = floor(length(array) / 2): Calculates the middle index of the array for dividing it into approximately equal halves.
  • left = mergeSort(subarray(array, 0, mid)): Recursively calls mergeSort on the left half of the array (from index 0 to mid-1).
  • right = mergeSort(subarray(array, mid + 1, length(array))): Recursively calls mergeSort on the right half of the array (from index mid+1 to the end).
  • return merge(left, right): Calls the merge function to combine the two sorted halves (left and right) into a single sorted array and returns it.

merge(left, right):

  • merged = []: Creates an empty array to store the merged result.
  • while length(left) > 0 and length(right) > 0: Continues the loop as long as both halves have elements left.
    • if first element of left <= first element of right:
      • append first element of left to merged: Adds the smaller element from the left half to the merged array.
      • remove first element from left: Removes the added element from the left half.
    • else:
      • append first element of right to merged: Adds the smaller element from the right half to the merged array.
      • remove first element from right: Removes the added element from the right half.
  • append remaining elements of left to merged: Appends any remaining elements in the left half to the merged array.
  • append remaining elements of right to merged: Appends any remaining elements in the right half to the merged array.
  • return merged: Returns the final sorted array after merging both halves.

subarray(array, start, end):

  • new_array = []: Creates a new empty array.
  • for i in range(start, end): Iterates through the elements from the specified start index to (but not including) the end index.
    • append element at index i of array to new_array: Adds the element at the current index (i) from the original array to the new_array.
  • return new_array: Returns the newly created subarray containing the specified elements.

Implementations

Kotlin

Golang

Selection Sort

Ever played “musical chairs” but with data elements? Selection Sort takes on this playful premise, ensuring each element finds its correct “chair” by repeatedly selecting the smallest and swapping it into place.

Process

Think of your data as a jumbled classroom. Selection Sort helps put everyone in their perfect seat, one by one. Here’s how:

  1. Pick a seat: Choose the first element as the “smallest” (or “largest”). It’s temporarily in its spot.
  2. Look around: Check everyone else (except the teacher’s pet in the front row, they’re already sorted!).
  3. Find the misplaced soul: If someone’s smaller (or larger) than the current “smallest,” remember their name! They’re the true contender.
  4. Switch desks: Swap the current “smallest” with the true contender. Now they’re both in the right place (sort of)!
  5. Repeat the process: Ignore the front row (sorted!), and start again from the next seat. Keep finding the truly smallest (or largest) and swapping them in.
  6. Class dismissed! Once everyone has switched seats the right number of times, the classroom (data) is perfectly sorted!

Pseudo Code

Code
function selectionSort(array):
  for i in range(len(array) - 1):
    min_index = i
    for j in range(i + 1, len(array)):
      if array[j] < array[min_index]:
        min_index = j
    swap(array[i], array[min_index])
  return array

function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation
  1. The selectionSort function takes an array as input.
  2. A for loop iterates through the array (except the last element, as it’s already in its final position).
  3. Inside the loop, a min_index variable is initialized to the current index (i). This assumes the element at this index is the smallest (or largest) so far.
  4. Another for loop iterates from the next element (i + 1) to the end of the array.
  5. If an element encountered in the inner loop is smaller (or larger) than the current min_index element, its index is stored in min_index. This new element becomes the candidate for the smallest (or largest).
  6. After the inner loop, the element at min_index is swapped with the element at the current index (i) using the swap function. This effectively places the smallest (or largest) element found so far in its correct position.
  7. The swap function takes two elements and exchanges their values.
  8. After all passes, the loop terminates, leaving the array sorted.

Implementations

Kotlin

Golang

Insertion Sort

Imagine organizing a messy bookshelf, placing each book where it belongs one by one. That’s the essence of Insertion Sort, inserting each data element into its correct position like finding the perfect spot for your favourite novel.

Process

Imagine you have a messy pile of playing cards and want to sort them in your hand, one by one. That’s the essence of Insertion Sort! Here’s how it works:

1. Start with one card: Consider the first element in your data as the sorted “hand.” It’s already in its rightful place.

2. Draw a new card: Look at the next element in the unsorted data (like drawing a new card).

3. Find the right spot: Compare the new card to each card in your sorted hand, starting from the “back” (highest/lowest depending on sorting order).

4. Make space: If you find a card bigger (or smaller) than the new one, shift all cards after it one position to the right (or left) to create a gap.

5. Insert the new card: Slide the new card into the empty space you just created, ensuring it’s now in its correct order within the sorted hand.

6. Repeat: Keep drawing new cards, comparing, shifting,

Pseudo Code

Code
function insertionSort(array):
  for i in range(1, len(array)):
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
      array[j + 1] = array[j]  # Shift elements to create space
      j -= 1
    array[j + 1] = key  # Insert key in its correct position
  return array
Explanation
  1. The insertionSort function takes an array as input.
  2. A for loop iterates through the array, starting from the second element (index 1), assuming the first element is already sorted.
  3. Inside the loop, the current element (key) is stored for comparison and potential insertion.
  4. Another while loop iterates backwards from the element before the key (j = i - 1), comparing elements with the key.
  5. If an element encountered in the inner loop is greater than the key, it’s shifted one position to the right to create space for the key.
  6. The inner loop continues shifting elements until a smaller element is found or the beginning of the array is reached.
  7. After the inner loop, the key is inserted into its correct position, ensuring sorted order up to that point.
  8. After all iterations, the array is sorted.

Implementations

Kotlin

Golang

Bubble Sort

Imagine sorting a messy pile of clothes, one swap at a time. That’s Bubble Sort in a nutshell! This simple algorithm might not be the speed king, but it’s a great way to understand sorting basics.

Process

Imagine you have a messy pile of toys and want to organize them by size. Bubble Sort does this by repeatedly comparing neighbouring toys:

  1. Start at the beginning: Compare the first two toys. If the second is bigger, swap their positions. This “bubbles” the larger toy towards the right.
  2. Repeat the comparison: Move one position to the right and compare the new pair. Swap if needed, again pushing the larger element further right.
  3. Keep going: Continue comparing and swapping pairs until you reach the end of the list. This completes one “pass.”
  4. Did we miss anything?: Repeat steps 1-3 from the beginning. With each pass, the largest element “bubbles” further right, leaving smaller ones sorted on the left.
  5. Are we done yet?: After a pass where no swaps occur, it means the list is sorted! You can celebrate with neatly organized toys (or data)!

Pseudo Code

Code
function bubbleSort(array):
  swapped = True
  while swapped:
    swapped = False
    for i in range(len(array) - 1):
      if array[i] > array[i + 1]:
        swap(array[i], array[i + 1])
        swapped = True
  return array

function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation of code
  1. The bubbleSort function takes an array as input.
  2. A swapped flag is initialized to True. This flag will be used to track if any swaps occurred during a pass.
  3. A while loop continues as long as swapped is True. This means at least one swap occurred in the previous pass, and the list might not be fully sorted.
  4. Inside the loop, swapped is set to False at the beginning of each pass, assuming no swaps will occur.
  5. Another for loop iterates through the array (except the last element, as it’s already in its final position).
  6. If the current element is greater than the next element, they are swapped using the swap function. This “bubbles” the larger element towards the end of the list.
  7. If a swap occurs, the swapped flag is set to True to indicate that the list is not yet fully sorted.
  8. The swap function takes two elements and exchanges their values.
  9. After all passes, the loop terminates when swapped remains False, indicating the list is sorted.

Implementations

Kotlin

Golang