Results 1 to 2 of 2

Thread: shell sorting?

  1. #1
    greeneyes is offline Senior Member+
    Last Online
    10th January 2008 @ 07:35 PM
    Join Date
    18 Feb 2006
    Location
    Pakistan
    Age
    37
    Posts
    62
    Threads
    43
    Credits
    1,060
    Thanked
    0

    Default shell sorting?

    AOA;
    sir koyee mujhe shelll sorting kay baray mai bataye ga in c++?
    S.Hamza.

  2. #2
    Love_bird's Avatar
    Love_bird is offline Senior Member
    Last Online
    13th May 2019 @ 08:49 AM
    Join Date
    21 Nov 2006
    Location
    Europ K Khawaboon Mein
    Posts
    999
    Threads
    23
    Credits
    1,249
    Thanked
    0

    Default

    the Shell sort, named after its creator D.L. Shell. It is the first algorithm that we will look at that swaps non-adjacent elements, and takes a "divide and conquer" approach. The list is divided into many sublists, which are sorted, and are then merged together. The shell sort takes advantage of the insertion sort, which is very efficient in a best case scenario (that is, the list being sorted is already 'near sorted').

    The shell sort divides the list into n/2 sublists, each being n/2 apart. For instance, in a list of ten elements, the first iteration would consist of five lists, two elements each. The first list would be list[0] and list[5], the second would be list[1] and list[6], and so on. Each of these lists is then sorted using an insertion sort. During the next iteration, we divide the list into bigger sublists, with the elements being closer together. In the second iteration, there are n/4 lists, each element being n/4 apart. These lists are then sorted using insertion sort, and so on. The process continues with twice the amount of lists each iteration as in the one before. Each iteration, the list becomes closer to being sorted. The last sort is done on the entire list, using a standard insertion sort. Since the list should be 'near sorted', the algorithm is very efficient.

    Note, during some iterations, sublists will contain unequal amount of elements, since the amount of sublists does not evenly divide into the total number of elements. Remember, in integer division, the decimal in the answer is dropped, e.g. 5/2 = 2. Therefore, if we have seven elements, there are three lists during the first iteration. One contains three elements, and the other two each contain two elements.

    {6,3,1,5,2,4,9} -> {6,3,1,5,2,4,9}

    In the example, list one starts at list[0] (6) and includes every item two apart. The next list starts at list[1] (3) and also includes every item two apart from its position. Since there is no item that is two locations after the '4', the list has only two items.

    The code for shell sort is very simple and straightforward. A slightly modified version of the insertion sort is used however. Since the elements of the sublists to be sorted are not adjacent, an increment parameter is added, which specifies how far apart the elements of the sublists are. The value '1' is then replaced by the increment in the original insertion sort code, since it now compares values that are increment apart.

    void InSortShell(int *nums,int n, int incr) //array called nums with n elements to be sorted, incr apart
    {
    for(int i=incr; i<n; i+=incr)
    for(int j=i; (j>=incr) && (nums[j] < nums[j-incr]); j-=incr)
    swap(nums[j],nums[j-incr]);
    }

    void ShellSort(int *nums, int n)
    {
    for(int i=n/2; i>2; i/=2) //each iteration there are twice as many sublists. Divide the distance between each element by 2.
    for(int j=0; j<i; j++) //sort each sublist
    InSortShell(&nums[j],n-j,i); //the first element of each sublist begins at j, and therefore the entire list is j items shorter (n-j). The elements of the sublist are i apart.
    InSortShell(nums,n,1); //do a standard insertion sort on the now nearly sorted list.
    }
    MFA site not allowed, ITDunya team

Similar Threads

  1. Alphanumeric sorting problem need help
    By general in forum Ask an Expert
    Replies: 3
    Last Post: 5th January 2015, 02:25 PM
  2. Data Sorting in MS word or MS excel?
    By thecute in forum Ask an Expert
    Replies: 3
    Last Post: 12th July 2013, 10:36 AM
  3. shell sorting?
    By greeneyes in forum Ask an Expert
    Replies: 2
    Last Post: 22nd September 2007, 09:37 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •