Jump to content
  • Advertisement
  • 09/13/99 06:17 PM
    Sign in to follow this  

    Shell Sort

    General and Gameplay Programming

    Myopic Rhino
    This sorting algorithm is conceived by D. L. Shell (that's where it gets its name), and is inspired by the Insertion Sort's ability to work very fast on an array that is almost in order. It is also called diminishing increment sort.

    Unlike Insertion Sort, Shell Sort does not sort the entire array at once. Instead, it divides the array into non-contiguous segments, which are separately sorted by using Insertion Sort. Once all of the segments are sorted, Shell Sort redivides the array into less segments and repeat the the algorithm until at last that the number of segment equals one, and the segment is sorted.

    There are two advantages of Shell Sort over Insertion Sort.
    1. When the swap occurs in a non-contiguous segment, the swap moves the item over a greater distance within the overall array. Insertion Sort only moves the item one position at a time. This means that in Shell Sort, the items being swapped are more likely to be closer to its final position then Insertion Sort.
    2. Since the items are more likely to be closer to their final position, the array itself becomes partially sorted. Thus when the segment number equals one, and Shell Sort is performing basically the Insertion Sort, it will be able to work very fast, since Insertion Sort is fast when the array is almost in order.
    There are variations of Shell Sort depending on the method of arranging segments. The method that we will be studying here is called "2X". This method determines the number of segments by dividing the number of cells by two (integer division), so that in the first round each segment will have mostly two, and maybe two cells. After the first round, we decrease the number of segments by dividing them by two again. This is to be repeated until there are one segment left (the entire array). Think on what other ways we can divide the segments that can be more efficient.

    Below is Shell Sort's pseudo-code.

    Shell Sort (Sorting the array A[size])

    Determine the number of segments by dividing the number of cells by two.
    While the number of segments are greater than zero
    For each segment, we do an Insertion Sort.
    (think on how to write the loops here efficiently... )
    Divide the number of segments by two.

      Report Article
    Sign in to follow this  

    User Feedback

    There are no comments to display.

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!