Shellsort

Definition

Definition

Shellsort is an efficient sorting algorithm that improves upon the insertion sort algorithm by sorting sublists of the data and then eventually sorting the entire list. It belongs to the family of comparison-based sorting algorithms and operates by moving elements closer to their sorted position through a series of diminishing increment gaps

Explanation

Start by sorting elements that are far apart from each other and then progressively reduces the gap between elements to be compared. It involves dividing the list into smaller sublists and sorting them using the insertion sort algorithm. These sublists are created by selecting elements that are a certain distance apart from each other, called the gap or increment sequence. The algorithm continues to decrease the gap until it becomes 1, at which point the list is sorted

Guidance

• Define an increment sequence to determine the gap between elements to be compared
• Start with the largest gap and perform an insertion sort on sublists created by this gap
• Reduce the gap and repeat the insertion sort process until the gap becomes 1
• Finally, perform a standard insertion sort with a gap of 1 to sort the entire list

Tips

• experiment with different increment sequences to find the most efficient one for your dataset
• avoid using large gaps at the beginning, as this might result in inefficient sorting
• consider using the Knuth sequence (3x + 1) for determining the increment sequence, as it often yields good result

Practice

Practice

shellSort(arr):
  # Define increment sequence
  gaps = [701, 301, 132, 57, 23, 10, 4, 1]

  # Iterate over each gap
  for gap in gaps:
    # Perform insertion sort with current gap
    for i = gap to length(arr):
      temp = arr[i]
      j = i
      # Move elements of arr[0..i-gap] that are greater than temp to their positions ahead of current position
      while j >= gap and arr[j - gap] > temp:
        arr[j] = arr[j - gap]
        j = j - gap
      arr[j] = temp

Solution

package main

func shellSort(arr []int) {
    n := len(arr)
    gap := n / 2
    for gap > 0 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap /= 2
    }
}

public class ShellSort {

  public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < n; i++) {
        int temp = arr[i];
        int j = i;
        while (j >= gap && arr[j - gap] > temp) {
          arr[j] = arr[j - gap];
          j -= gap;
        }
        arr[j] = temp;
      }
    }
  }
}

function shellSort(arr) {
  let n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
}

fun shellSort(arr: IntArray) {
    val n = arr.size
    var gap = n / 2
    while (gap > 0) {
        for (i in gap until n) {
            val temp = arr[i]
            var j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap /= 2
    }
}

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

fn shell_sort(arr: &mut [i32]) {
    let n = arr.len();
    let mut gap = n / 2;
    while gap > 0 {
        for i in gap..n {
            let mut j = i;
            let temp = arr[i];
            while j >= gap && arr[j - gap] > temp {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

function shellSort(arr: number[]): void {
  const n: number = arr.length;
  for (
    let gap: number = Math.floor(n / 2);
    gap > 0;
    gap = Math.floor(gap / 2)
  ) {
    for (let i: number = gap; i < n; i++) {
      let temp: number = arr[i];
      let j: number = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
}