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 8 of 8

Thread: Quicksort

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    96
    Thanks
    15
    Thanked 1 Time in 1 Post

    Question Quicksort

    PHP Code:
    int partition(int arr[], int leftint right)

    {

          
    int i leftright;

          
    int tmp;

          
    int pivot arr[(left right) / 2];

         

          while (
    <= j) {

                while (
    arr[i] < pivot)

                      
    i++;

                while (
    arr[j] > pivot)

                      
    j--;

                if (
    <= j) {

                      
    tmp arr[i];

                      
    arr[i] = arr[j];

                      
    arr[j] = tmp;

                      
    i++;

                      
    j--;

                }

          };

         

          return 
    i;

    }

     

    void quickSort(int arr[], int leftint right) {

          
    int index partition(arrleftright);

          if (
    left index 1)

                
    quickSort(arrleftindex 1);

          if (
    index right)

                
    quickSort(arrindexright);


    The reason why the range of the array decreases in size, is it because of the line of code "return i;"? Moreover, does "index - 1" make it so that the left range of the array decreases in size faster than the right one? Last question: Why won't the program work if I write "index" instead of "index - 1"? I know that there would be a conflict in the algorithm, but I don't know exactly why it wouldn't work.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Quicksort

    Why won't the program work if I write "index" instead of "index - 1"
    What happens when you try that? Do you get errors or is the output wrong?

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    96
    Thanks
    15
    Thanked 1 Time in 1 Post

    Default Re: Quicksort

    Quote Originally Posted by Norm View Post
    What happens when you try that? Do you get errors or is the output wrong?
    I get errors.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Quicksort

    If you want help with the errors, you need to post the full text of the error messages.

  5. #5
    Forum Squatter newbie's Avatar
    Join Date
    Nov 2010
    Location
    North Wales
    Posts
    661
    My Mood
    Stressed
    Thanks
    28
    Thanked 115 Times in 106 Posts
    Blog Entries
    1

    Default Re: Quicksort

    Quote Originally Posted by wholegrain View Post
    I get errors.
    That cracked me up :3
    Please use [highlight=Java]//code goes here...[/highlight] tags when posting your code

  6. #6
    Member
    Join Date
    Feb 2012
    Posts
    96
    Thanks
    15
    Thanked 1 Time in 1 Post

    Default Re: Quicksort

    It's just a theoretical question. I am not trying to make a program or anything.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Quicksort

    It looked like You were asking a specific programming question. If you change how large the index is for an array, you get an exception. No theory, very practical.

  8. #8
    Member
    Join Date
    Feb 2012
    Posts
    96
    Thanks
    15
    Thanked 1 Time in 1 Post

    Default Re: Quicksort

    What?

    I am trying to fully understand the Quicksort algorithm, but since I can only simulate the first turn mentally I have a hard time understanding why it doesn't work if I replace "index - 1" with "index".

Similar Threads

  1. QuickSort method
    By D3158 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 15th, 2011, 09:17 PM
  2. StackOverflowError when using quicksort
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 3
    Last Post: April 22nd, 2011, 05:24 PM
  3. Quicksort algorithm displaying strange behaviour
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 0
    Last Post: April 19th, 2011, 12:56 PM