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

Thread: Characters from String in alphabetic order using quicksort

  1. #1
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Characters from String in alphabetic order using quicksort

    Hi,
    I am trying to do a program that takes all of the chars from a string and orders them in alphabetical order. It works fine, but when a is a last letter of a string it isn't being sorted.
    Example: bcba = bbca, omnibus = bimnous (here u is in wrong place)
    Here is my code:
    public class sorty{
    public static void sort(char[] a, int low, int high){
      int i = low;
      int j = high;
      if (j - i < 2) return;
      int m = (j+i)/2;
      char p = a[m];
      a[m] = a[i];
      a[i] = p;
     
      int r = i+1;
      for(int s = r; s!=j; s=s+1)
      {
        if(a[s]<p)
        {
          char tmp = a[s];
          a[s] = a[r];
          a[r] = tmp;
          r = r+1;
        }
      }
      r = r-1;
      a[i] = a[r];
      a[r] = p;
      sort(a,i,r);
      sort(a,r+1,j);
    }
    public Character[] toCharArray( String s )
    {
       int len = s.length();
       Character[] array = new Character[len];
       for (int i = 0; i < len ; i++) {
          array[i] = new Character(s.charAt(i));
       }
       return array;
    }
        public static void main(String[] args)
        {
            String input = "bcba";
            String output = quicksort(input);
            System.out.print(output);
        }
        public static String quicksort(String y)
        {
            int length = y.length();
            int i = 0;
            int j = length-1;
            char[] a = y.toCharArray();
            sort(a,i,j);
            String x=new String(a);
            return x;
     
        }
    }


  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: Characters from String in alphabetic order using quicksort

    How are you debugging the code?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Characters from String in alphabetic order using quicksort

    What do you mean by that?

  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: Characters from String in alphabetic order using quicksort

    When code doesn't do what the programmer wants it to do, he should debug it to see why.
    How are you trying to see what the code is doing so you can fix it?

    omnibus = bimnous (here u is in wrong place)
    That seems strange that the u was treated specially. What other inputs have you tried? What were the results for the other tests.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Characters from String in alphabetic order using quicksort

    When code doesn't work I try to run it through a program called Jeliot, but this time it crashes when it gets to the line char p = a[m]; in sort method so I can't really see what is going on after.

    When my input is : omnibusa (I added extra a at the end) outcome is = bimnosua (letter a has not been sorted, but u has)

    I have also tried this sorting method and it works with short strings, but when String has many characters, for example 2*(english alphabet) Input = abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx yz my output is : aabcdefghijklbcdefghi....wwxxyyzz. It started with aab which is correct, but then it doesn't really sort until the letter w.
    public static void sort(char[] a, int low, int high){
     
        int i = low;
        int j = high;
        char tmp;
     
        int pivot = (low+high)/2;
     
        while (i <= j) {
          while(a[i] < a[pivot]){
            i++;
          }
          while(a[j] > a[pivot]){
            j--;
          }
     
          if(i <= j) {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
          }
        }
     
        if(low < j){
          sort(a, low, j);
        }
        if(i < high){
          sort(a,i,high);
        }
      }

  6. #6
    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: Characters from String in alphabetic order using quicksort

    it works with short strings,
    Do you have some samples for when it worked? It never worked for me.
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Characters from String in alphabetic order using quicksort

    The second sort method that I uploaded works for example with words : omnibus = bimnosu, omnibusa = abimnosu, Norm = Nmor, norm = mnor or even iamtiredofit = adefiiimortt
    You are right about first one. It never fully works. It needs some corrections probably. Let's maybe stick to the second method?

    P.S.: First method works with abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx yz ... but second does not.

  8. #8
    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: Characters from String in alphabetic order using quicksort

    Let's maybe stick to the second method?
    Have you solved it now?

    First method works with ..
    Are you sure? Add a letter less than z to the end of it.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Characters from String in alphabetic order using quicksort

    I created new sort method, but it doesn't work with string that has many letters in it. For example : abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx yz doesn't work, but words such as omnibus, omnibusa etc. fully work.
    So no.. I didn't solve it yet.
    My new code:
    public class sorty{
    public static void sort(char[] a, int low, int high){
     
        int i = low;
        int j = high;
        char tmp;
     
        int pivot = i+(j-i)/2;
     
        while (i <= j) {
          while(a[i] < a[pivot]){
            i++;
          }
          while(a[j] > a[pivot]){
            j--;
          }
     
          if(i <= j) {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
          }
        }
     
        if(low < j){
          sort(a, low, j);
        }
        if(i < high){
          sort(a,i,high);
        }
      }
    public Character[] toCharArray( String s )
    {
       int len = s.length();
       Character[] array = new Character[len];
       for (int i = 0; i < len ; i++) {
          array[i] = new Character(s.charAt(i));
       }
       return array;
    }
        public static void main(String[] args)
        {
            String input = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
            String output = quicksort(input);
            System.out.print(output);
        }
        public static String quicksort(String y)
        {
            int length = y.length();
            int i = 0;
            int j = length-1;
            char[] a = y.toCharArray();
            sort(a,i,j);
            String x=new String(a);
            return x;
     
        }
    }

  10. #10
    Junior Member
    Join Date
    Sep 2014
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Characters from String in alphabetic order using quicksort

    Any solution? I tried to debug in eclipse it, but I am new to java so I don't really know how to use it (I tried to read about debugging and watch some vidoes on youtube).

  11. #11
    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: Characters from String in alphabetic order using quicksort

    The code doesn't have any comments describing the logic it is using.
    Why do you think the code's logic will solve the problem?

    For debugging I use println() statements that print out the values of variables as they are changed and used.
    If you understand what the code is supposed to do, seeing what it actually does should show you where the problems are and help you find solutions to get it to work.
    I can't help you with the IDEs interactive debugging.

    For testing I'd start with a short String so there isn't too much debug output. Gradually change the String until the code fails and then work on why it failed and find a solution.
    If you don't understand my answer, don't ignore it, ask a question.

  12. The Following User Says Thank You to Norm For This Useful Post:

    TheDDestroyer12 (October 5th, 2014)

Similar Threads

  1. How to handle string with characters
    By rkumar in forum What's Wrong With My Code?
    Replies: 7
    Last Post: September 17th, 2014, 02:34 AM
  2. Ignore certain characters in a string.
    By JaAnTr in forum What's Wrong With My Code?
    Replies: 3
    Last Post: April 5th, 2014, 03:18 PM
  3. Eliminating Unicode Characters and Escape Characters from String
    By bilalonjavaforum in forum What's Wrong With My Code?
    Replies: 2
    Last Post: December 19th, 2013, 05:26 AM
  4. Replies: 2
    Last Post: March 28th, 2013, 09:54 AM
  5. How to check whether the string contains only the specified characters ????
    By j_kathiresan in forum Java Theory & Questions
    Replies: 3
    Last Post: April 30th, 2010, 08:49 AM