Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Shell Sort Comparisons and Exchanges

  1. #1
    Junior Member
    Join Date
    Sep 2019
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation Shell Sort Comparisons and Exchanges

    Im trying to count the comparisons and exchanges it take for Shell sort to sort a array of numbers 1-10. with the comparison counter where is is now (comp) and the exchange counter where it is (exch) im getting 22 comparisons and zero exchanges. i believe the zero exchanges is right because its obviously a sorted array so no exchanges are needed. with a array of 10 elements i dont think 22 comparisons would be correct. can someone show me where these expressions need to be and explain why? i would greatly appreciate it.

    public static void shellSort(int[] array) {
            int interval = array.length / 2;
            int comp = 0, exch = 0;
            while (interval != 0) {
                for (int i = 0; i < interval; i++) {
                    for (int p = i + interval; p < array.length; p += interval) {
                        int key = array[p];
                        int j = p - interval;
                        while (j >= 0) {
                            comp++;         //Comparison here
                            if (key < array[j]) {
                                array[j + interval] = array[j];
                            } else
                                break;
                            exch++;     //Exchange here
                            j -= interval;
                        }
                        array[j + interval] = key;
                    }
                }
                interval /= 2;
            }
    Last edited by briguy; September 26th, 2019 at 07:08 PM.

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,475
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Shell Sort Comparisons and Exchanges

    i dont think 22 comparisons would be correct.
    Why? Add some print statements that print out the values being compared so you can judge if the count is correct.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2019
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Shell Sort Comparisons and Exchanges

    the values being compared are
    int array[] = {1,2,3,4,5,6,7,8,9,10};
    maybe i'm wrong but shouldn't it make 9 comparisons if the array is already sorted?

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,475
    Thanks
    53
    Thanked 2,405 Times in 2,358 Posts

    Default Re: Shell Sort Comparisons and Exchanges

    but shouldn't it make 9 comparisons
    I don't know sorting theory and can't comment on the algorithm you are testing.
    I suspect some very smart people developed the algorithm.

    Did you try adding a print statement to show what was being compared?

    --- Update ---

    Also posted at: https://stackoverflow.com/questions/...l-sort-program

    Please read: The problems with cross-posting
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Datatype comparisons in do while loops
    By SamJava_the_Hut in forum What's Wrong With My Code?
    Replies: 10
    Last Post: January 23rd, 2019, 12:55 AM
  2. [SOLVED] String Comparisons, HashSet, Duplicates
    By marmalade in forum What's Wrong With My Code?
    Replies: 4
    Last Post: April 20th, 2014, 11:50 PM
  3. [SOLVED] displaying every 1000 comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 6
    Last Post: May 27th, 2012, 07:26 PM
  4. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 26th, 2012, 11:54 PM
  5. Hibbard Shell Sort
    By biglandphil in forum Algorithms & Recursion
    Replies: 3
    Last Post: November 12th, 2009, 10:14 PM

Tags for this Thread