Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!