Bubble sort an array of objects?

Question

Syrne 9 Junior Poster in Training

12 Years Ago

Hi guys (again), I have a new issue.

I am trying to bubble sort my array of objects to display in alphabetical order.

Here's the code:

Subscriber class:

package assignmentone;

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Random;

/**
 *
 * @author Bill
 */
public class Subscriber {
        
        //Field declarations
        private String name;
        private String url;
        private String friendsList;
        
        public int friendIndex = 0;
        
        private int adClicks;
        
        //Default Constructor
        Subscriber()
        {
            
        }
        
        //Set Constructor Fields
        Subscriber(String subName, String subUrl, String subFriends,
                int subClicks)
        {
            name = subName;
            url = subUrl;
            friendsList = subFriends;
            adClicks = subClicks;
        }
        
        //=============Accessor methods=============
        public String getName()
        {
            return name;
        }
        
        public String getUrl()
        {
            return url;
        }
        
        public String getFriends()
        {
            return friendsList;
        }
        
        public int getClicks()
        {
            return adClicks;
        }
        
        //=============Mutator methods=============
        public void setName(String subName)
        {
            name = subName.toUpperCase();
        }
        
        public void setUrl(String subUrl)
        {
            url = subUrl.toLowerCase();
        }
        
        public void setFriends(String subFriends)
        {
            friendsList = subFriends.toUpperCase();
        }
        
        public void setClicks(int subClicks)
        {
            adClicks = subClicks;
        }
        
        //=============ReadIn method=============
        public void readIn()
        {
            String anyMore;
            
            Scanner keyboard = new Scanner(System.in);
            System.out.println("Enter subscriber name: ");
            name = keyboard.nextLine().toUpperCase();
            System.out.println("Enter subscriber URL: ");
            url = keyboard.nextLine().toUpperCase();
            
            do
            {
                String friendName;
                
                System.out.println("Name of friend (last name first!): ");
                friendName = keyboard.nextLine().toUpperCase();
                friendsList = friendsList.concat(friendName);
                
                System.out.println("\nDo you want to enter another name? "
                        + "(Y/N): ");
                anyMore = keyboard.nextLine().toUpperCase();
                friendIndex++;
                
                    if (anyMore.equals("Y"))
                    {
                        friendsList = friendsList.concat(";");
                        System.out.println();
                    }
            }while(anyMore.equals("Y"));
            
        }
        
        //=============Display method=============
        public void display()
        {
            StringTokenizer tokenizedList;
            
            Random generator = new Random();
            adClicks = generator.nextInt(10000);
            
            System.out.println("\nSubscriber: " + name);
            System.out.println("URL: " + url);
            
            tokenizedList = new StringTokenizer(friendsList, ";");
            System.out.println("\n" + adClicks + " users have clicked on your ads.");
            System.out.println("\nYou have " + friendIndex +" friend(s): ");
                    
            while (tokenizedList.hasMoreTokens())
            {
                System.out.println(tokenizedList.nextToken());        
            }
        }
        
        //=============Find Friend method=============
        public boolean isAmongFriends(String aFriend)
        {
            boolean isInList = false;
            StringTokenizer tokenizedStr = new StringTokenizer(friendsList, ";");
            System.out.println("Friend's name: ");
            String extractFriend;
            
           while(tokenizedStr.hasMoreTokens() && !isInList)
           {
               extractFriend = tokenizedStr.nextToken();
               
               if(extractFriend.equals(aFriend))
               {
                   System.out.println(extractFriend +" is among your friends.");
                   isInList = true;           
               }
           }
           
           return true;
        }
        
        //=============Bubble sort method=============
        public static void BubbleSort(String[] input)
        {
            int j;
            boolean flag = true;
            String temp = null;
            
            while(flag)
            {
                flag = false;
                
                for(j = 0; j < input.length - 1; j++)
                {
                    if(input[j].compareTo(input[j+1]) > 0)
                    {
                            temp = input[j];
                            input[j] = input[j+1];
                            input[j+1] = temp;
                            flag = true;
                    }
                }
            }
        }
        

}

Main:

package assignmentone;

import java.util.Scanner;


public class AssignmentOne {

    //Constant declaration
    public static int MAX_NUM = 10;
    
    public static void main(String[] args) {

        Subscriber subList[] = new Subscriber[MAX_NUM];
        
        String anyMoreSub;        
        String menuChoice;
        String askQuit;
        
        int subIndex = 0;
        
        boolean isDone = false;
        
        Scanner keyboard = new Scanner(System.in);
        
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i] = new Subscriber("", "", "", 0);
        }
            
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i].readIn();
            
            System.out.println("\nDo you want to enter another subscriber? "
                    + "(Y/N): ");
            anyMoreSub = keyboard.nextLine().toUpperCase();
            subIndex++;
                
                if (anyMoreSub.equals("N"))
                {
                    break;
                }
        }       
        
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i].BubbleSort();
        }
        
        while(!isDone)
        {
                    System.out.println("\nPlease enter the letter for "
                    + "your selection: " +
                    "\n    A - Display all data" +
                    "\n    B - Display data of specific Subscriber" +
                    "\n    C - Display names of Subscribers with specific "
                    + "friend" +
                    "\n    D - Quit");
                    
                   menuChoice = keyboard.nextLine().toUpperCase();
            
            while(!menuChoice.equals("A") && !menuChoice.equals("B") && 
                    !menuChoice.equals("C") && !menuChoice.equals("D"))
            {
                System.out.println("\nSorry, you must choose"
                        + " one of the valid menu choices. Try again.");
                
                    System.out.println("\nPlease enter the number for "
                    + "your selection: " +
                    "\n    A - Display all data" +
                    "\n    B - Display data of specific Subscriber" +
                    "\n    C - Display names of Subscribers with specific "
                    + "friend" +
                    "\n    D - Quit");
                    
                    menuChoice = keyboard.nextLine().toUpperCase();
            }
                
                if(menuChoice.equals("A"))
                {
                    for(int i = 0; i < subIndex ;i++)
                    {
                        subList[i].display();
                    }
                    
                }
                 if(menuChoice.equals("B"))
                 {
                     
                 }
                 
                 if(menuChoice.equals("C"))
                 {
                 
                 }
                 
                 if(menuChoice.equals("D"))
                 {
                     System.out.println("Are you sure you want to exit? (Y/N): ");
                     askQuit = keyboard.nextLine().toUpperCase();
                     
                     if(askQuit.equals("Y"))
                     {
                     
                     isDone = true;
                     
                     }
                 }
                    
               
            }
        }
    }

As you can see I have the bubble sort method's skeleton in the Subscriber class, but I just can't seem to figure out how to apply it to my object array. Any suggestions would be great!

Thank you!

java

2 Contributors
15 Replies
2K Views
1 Day Discussion Span
Latest Post 12 Years Ago Latest Post by Taywin

All 15 Replies

Taywin 312 Posting Virtuoso

12 Years Ago

What is the natural order for SubScriber class? What I mean is that do you want it to be sorted using only its "name" variable? If so, you may need to implement compareTo() method for your SubScriber class. Then you wouldn't need to modify your current bubble sort(). If not, you need to update the way you compare input[j] with other input[j+1]. The compareTo() method of SubScriber must return an integer value of negative (less than), 0 (equal), or positive (greater than).

Taywin 312 Posting Virtuoso

12 Years Ago

It's not a problem. Yes, you are correct about that.

class SubScriber {
  public int compareTo(SubScriber other) {
    // do the comparison of name string here
    // and return the correct value
  }
}

Taywin 312 Posting Virtuoso

12 Years Ago

Let me look at the algorithm for bubble sort and I will get back to you. :)

Edit:
OK, let's look at your code again here.

package assignmentone;

import java.util.*;

public class AssignmentOne {
    
  //=============Bubble sort method=============
  public static void BubbleSort(Subscriber[] input) {
    int j;
    boolean flag = true;
    String temp = null;
            
    while(flag) {
      flag = false;
      for(j = 0; j < input.length - 1; j++) {
        if(input[j].compareTo(input[j+1]) > 0) {
          temp = input[j];
          input[j] = input[j+1];
          input[j+1] = temp;
          flag = true;
        }
      }
    }
  }  // BubbleSort(SubScriber[])

  //Constant declaration
  public static int MAX_NUM = 10;
    
  public static void main(String[] args) {
    Subscriber subList[] = new Subscriber[MAX_NUM];
    String anyMoreSub;        
    String menuChoice;
    String askQuit;
        
    int subIndex = 0;
    boolean isDone = false;
    Scanner keyboard = new Scanner(System.in);

    for(int i = 0; i < MAX_NUM ;i++) {
      subList[i] = new Subscriber("", "", "", 0);
    }
            
    for(int i = 0; i < MAX_NUM ;i++) {
      subList[i].readIn();
      System.out.println("\nDo you want to enter another subscriber? " + "(Y/N): ");
      anyMoreSub = keyboard.nextLine().toUpperCase();
      subIndex++;

      if (anyMoreSub.equals("N")) {
        break;
      }
    }       

    // check what's going in
    System.out.println("Before sort:");
    for (int i=0; i<subList.length; i++) {
      System.out.println((i+1)+":"+subList[i].name);
    }

    BubbleSort(subList);

    // then display the subList to see if it is changed
    System.out.println("After:");
    for (int i=0; i<subList.length; i++) {
      System.out.println((i+1)+":"+subList[i].name);
    }
  }  // main()
}

/*
Bubble sort pseudo code from Wikipedia
Normal version:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
      swapped = false
      for i = 1 to n-1 inclusive do
         if A[i-1] > A[i] then
            swap(A[i-1], A[i])
            swapped = true
         end if
      end for
      n = n - 1
   until not swapped
end procedure

Optimized version:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
      newn = 0
      for i = 1 to n-1 inclusive do
         if A[i-1] > A[i] then
            swap(A[i-1], A[i])
            newn = i
         end if
      end for
      n = newn
   until n = 0
end procedure

You could replace "A" with "input" in your sort method and use do-while in place of repeat-until. Remember that n-1 inclusive means i<n.
*/

By the way, looking at the way you accept input, you will end up with multiple empty string leading in the sort because empty string has the lowest value in string comparison. Unless you use the "n" value as the real number of data you entered.

Edited 12 Years Ago by Taywin because: n/a

Syrne commented: Great help! +2

Taywin 312 Posting Virtuoso

12 Years Ago

What you can do is to pass in the real number of SubScriber entered into your array to the BubbleSort() method. Then replace the value which is use in the loop as input.length with the argument.

// in main()
...
...
BubbleSort(subList, subIndex);
...


// bubble sort method
public static void BubbleSort(Subscriber[] input, int len) {
  ...
  for (int j=0; j<len; j++) {
    ...
  }
  ...
}

PS: Line 32 where you declare a constant, you may use

public static final int MAX_NUM = 10;

instead. The reason is that the constant should and never be able to changed in the program; especially when you allow "public" accessing. The "final" key word forces the variable to be a real constant.

Edited 12 Years Ago by Taywin because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Taywin 312 Posting Virtuoso · Answer 1 · 2011-09-21T21:36:01+00:00

You cannot simply use subList.BubbleSort(); like that. The class SubScriber does not know how other class is using its definition. The class that implements an array of SubScriber must do the job.

What you may want to do is to create a class or a method to do the sort. A dirty way is to create a static sort method in your AssignmentOne class.

class AssignmentOne {
  public static void sort(SubScriber[] ss) {
    // bubble sort it here
    // you may not need to return anything because the [] is mutable
  }
}

Syrne 9 Junior Poster in Training · Answer 2 · 2011-09-21T21:48:57+00:00

You cannot simply use subList.BubbleSort(); like that. The class SubScriber does not know how other class is using its definition. The class that implements an array of SubScriber must do the job.
What you may want to do is to create a class or a method to do the sort. A dirty way is to create a static sort method in your AssignmentOne class.
class AssignmentOne {
  public static void sort(SubScriber[] ss) {
    // bubble sort it here
    // you may not need to return anything because the [] is mutable
  }
}

I understand what you mean by having the Assignment one class (which contains the object array declaration) do the sorting, but implementing it is an issue.

When I change the parameter in the BubbleSort function to Subscriber[], the string methods don't work. Do I need to edit the entire sort method?

Here's the 'revised' code in main until the BubbleSort method would be called:

package assignmentone;

import java.util.*;


public class AssignmentOne {
    
    //=============Bubble sort method=============
        public static void BubbleSort(Subscriber[] input)
        {
            int j;
            boolean flag = true;
            String temp = null;
            
            while(flag)
            {
                flag = false;
                
                for(j = 0; j < input.length - 1; j++)
                {
                    if(input[j].compareTo(input[j+1]) > 0)
                    {
                            temp = input[j];
                            input[j] = input[j+1];
                            input[j+1] = temp;
                            flag = true;
                    }
                }
            }
        }

    //Constant declaration
    public static int MAX_NUM = 10;
    
    public static void main(String[] args) {

        Subscriber subList[] = new Subscriber[MAX_NUM];
        
        String anyMoreSub;        
        String menuChoice;
        String askQuit;
        
        int subIndex = 0;
        
        boolean isDone = false;
        
        Scanner keyboard = new Scanner(System.in);
       
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i] = new Subscriber("", "", "", 0);
        }
            
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i].readIn();
            
            System.out.println("\nDo you want to enter another subscriber? "
                    + "(Y/N): ");
            anyMoreSub = keyboard.nextLine().toUpperCase();
            subIndex++;
                
                if (anyMoreSub.equals("N"))
                {
                    break;
                }
        }       

        BubbleSort();

Thanks for your help!

Syrne 9 Junior Poster in Training · Answer 3 · 2011-09-21T22:36:13+00:00

What is the natural order for SubScriber class? What I mean is that do you want it to be sorted using only its "name" variable? If so, you may need to implement compareTo() method for your SubScriber class. Then you wouldn't need to modify your current bubble sort(). If not, you need to update the way you compare input[j] with other input[j+1]. The compareTo() method of SubScriber must return an integer value of negative (less than), 0 (equal), or positive (greater than).

I suppose I would only sort using the 'name' string variable because I'm sorting alphabetically by name. I think that would be the only variable that matters.

I don't understand what you mean by "implement compareTo() method for your Subscriber class," do you mean modify the 'compareTo()' method to accept the 'name' variable?

If so, I am unsure how to do this.

Sorry for the ignorance, I'm still very new at this. :@

Thanks again.

Syrne 9 Junior Poster in Training · Answer 4 · 2011-09-22T06:29:55+00:00

I'm sorry, but could you please elaborate on what you mean by "do comparison of ~ string and return a value"?

It's just not sinking in. I don't know why this sorting method has be so frazzled!

Taywin 312 Posting Virtuoso · Answer 5 · 2011-09-22T06:34:59+00:00

OK... Let's try this... :)

class SubScriber {
  public int compareTo(SubScriber other) {
    // do the comparison of name string here
    // and return the correct value
    return name.compareTo(other.name);
  }
}

Oh by the way, assume that your bubble sort is correct. :) But that could be later problem to talk about once you are done with this compareTo().

Syrne 9 Junior Poster in Training · Answer 6 · 2011-09-22T06:45:06+00:00

OK... Let's try this... :)
class SubScriber {
  public int compareTo(SubScriber other) {
    // do the comparison of name string here
    // and return the correct value
    return name.compareTo(other.name);
  }
}
Oh by the way, assume that your bubble sort is correct. :) But that could be later problem to talk about once you are done with this compareTo().

Thank you. It looks like my Bubblesort method is incorrect.

It seems like having an object array makes this incredibly more difficult than say, an array of strings or integers. Is there some sort of universal method in which I can just 'plug in' my object array to be sorted?

Syrne 9 Junior Poster in Training · Answer 7 · 2011-09-22T07:06:35+00:00

Let me look at the algorithm for bubble sort and I will get back to you. :)

Edit:
OK, let's look at your code again here.

package assignmentone;

import java.util.*;

public class AssignmentOne {
    
  //=============Bubble sort method=============
  public static void BubbleSort(Subscriber[] input) {
    int j;
    boolean flag = true;
    String temp = null;
            
    while(flag) {
      flag = false;
      for(j = 0; j < input.length - 1; j++) {
        if(input[j].compareTo(input[j+1]) > 0) {
          temp = input[j];
          input[j] = input[j+1];
          input[j+1] = temp;
          flag = true;
        }
      }
    }
  }  // BubbleSort(SubScriber[])

  //Constant declaration
  public static int MAX_NUM = 10;
    
  public static void main(String[] args) {
    Subscriber subList[] = new Subscriber[MAX_NUM];
    String anyMoreSub;        
    String menuChoice;
    String askQuit;
        
    int subIndex = 0;
    boolean isDone = false;
    Scanner keyboard = new Scanner(System.in);

    for(int i = 0; i < MAX_NUM ;i++) {
      subList[i] = new Subscriber("", "", "", 0);
    }
            
    for(int i = 0; i < MAX_NUM ;i++) {
      subList[i].readIn();
      System.out.println("\nDo you want to enter another subscriber? " + "(Y/N): ");
      anyMoreSub = keyboard.nextLine().toUpperCase();
      subIndex++;

      if (anyMoreSub.equals("N")) {
        break;
      }
    }       

    // check what's going in
    System.out.println("Before sort:");
    for (int i=0; i<subList.length; i++) {
      System.out.println((i+1)+":"+subList[i].name);
    }

    BubbleSort(subList);

    // then display the subList to see if it is changed
    System.out.println("After:");
    for (int i=0; i<subList.length; i++) {
      System.out.println((i+1)+":"+subList[i].name);
    }
  }  // main()
}

/*
Bubble sort pseudo code from Wikipedia
Normal version:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
      swapped = false
      for i = 1 to n-1 inclusive do
         if A[i-1] > A[i] then
            swap(A[i-1], A[i])
            swapped = true
         end if
      end for
      n = n - 1
   until not swapped
end procedure

Optimized version:
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat
      newn = 0
      for i = 1 to n-1 inclusive do
         if A[i-1] > A[i] then
            swap(A[i-1], A[i])
            newn = i
         end if
      end for
      n = newn
   until n = 0
end procedure

You could replace "A" with "input" in your sort method and use do-while in place of repeat-until. Remember that n-1 inclusive means i<n.
*/

By the way, looking at the way you accept input, you will end up with multiple empty string leading in the sort because empty string has the lowest value in string comparison. Unless you use the "n" value as the real number of data you entered.

Thank you for the great help! I will get right to it!

Taywin 312 Posting Virtuoso · Answer 8 · 2011-09-22T07:24:15+00:00

Good luck. If you do not understand any part of the pseudo code, just ask. :)

Syrne 9 Junior Poster in Training · Answer 9 · 2011-09-22T07:38:49+00:00

Good luck. If you do not understand any part of the pseudo code, just ask. :)

Here's the revised code:

package assignmentone;

import java.util.Scanner;

public class AssignmentOne {
    
    //=============Bubble sort method=============
        public static void BubbleSort(Subscriber[] input)
        {
            int j;
            boolean flag = true;
            Subscriber temp = null;
            
            while(flag)
            {
                flag = false;
                
                for(j = 0; j < input.length - 1; j++)
                {
                    if(input[j].compareTo(input[j+1]) > 0)
                    {
                            temp = input[j];
                            input[j] = input[j+1];
                            input[j+1] = temp;
                            flag = true;
                    }
                }
            }
        } 

    //Constant declaration
    public static int MAX_NUM = 10;
    
    public static void main(String[] args) {

        Subscriber subList[] = new Subscriber[MAX_NUM];
        
        String anyMoreSub;        
        int menuChoice;
        String askQuit;
        
        int subIndex = 0;
        
        boolean isDone = false;
        
        Scanner keyboard = new Scanner(System.in);
       
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i] = new Subscriber("", "", "", 0);
        }
            
        for(int i = 0; i < MAX_NUM ;i++)
        {
            subList[i].readIn();
            
            System.out.println("\nDo you want to enter another subscriber? "
                    + "(Y/N): ");
            anyMoreSub = keyboard.nextLine().toUpperCase();
            subIndex++;
                
                if (anyMoreSub.equals("N"))
                {
                    break;
                }
        }       


        BubbleSort(subList);

        while(!isDone)
        {
                    System.out.println("\nPlease enter the letter for "
                    + "your selection: " +
                    "\n    1 - Display all data" +
                    "\n    2 - Display data of specific Subscriber" +
                    "\n    3 - Display names of Subscribers with specific "
                    + "friend" +
                    "\n    4 - Quit");
                    
                   menuChoice = keyboard.nextInt();
            
            while(menuChoice != 1 && menuChoice != 2 && 
                    menuChoice != 3 && menuChoice != 4)
            {
                System.out.println("\nSorry, you must choose"
                        + " one of the valid menu choices. Try again.");
                
                    System.out.println("\nPlease enter the number for "
                    + "your selection: " +
                    "\n    1 - Display all data" +
                    "\n    2 - Display data of specific Subscriber" +
                    "\n    3 - Display names of Subscribers with specific "
                    + "friend" +
                    "\n    4 - Quit");
                    
                    menuChoice = keyboard.nextInt();
                    keyboard.nextLine();
            }
                
                if(menuChoice == 1)
                {
                    for(int i = 0; i < subIndex ;i++)
                    {
                        subList[i].display();
                    }
                    
                }
                 if(menuChoice == 2)
                 {
                     
                 }
                 
                 if(menuChoice == 3)
                 {

                 }
                 
                 if(menuChoice == 4)
                 {
                     keyboard.nextLine();
                     System.out.println("Are you sure you want to exit? "
                             + "(Y/N): ");
                     askQuit = keyboard.nextLine().toUpperCase();
                     
                     if(askQuit.equals("Y"))
                     {
                     
                     isDone = true;
                     
                     }
                 }
                    
               
            }
        }
    }

Somehow I missed that I had String temp = null as opposed to Subscriber temp = null which was causing issues, but now I have another unfortunately.

You were correct about the empty strings. After sorting, if I were to enter, say, 2 subscribers, they would be in members 9 and 10 of the object array and the empty strings will occupy the preceding members.

Since I am still using the original method, I'm unsure where exactly I can tell the method to only sort members containing data.

Syrne 9 Junior Poster in Training · Answer 10 · 2011-09-23T00:49:17+00:00

What you can do is to pass in the real number of SubScriber entered into your array to the BubbleSort() method. Then replace the value which is use in the loop as input.length with the argument.
// in main()
...
...
BubbleSort(subList, subIndex);
...


// bubble sort method
public static void BubbleSort(Subscriber[] input, int len) {
  ...
  for (int j=0; j<len; j++) {
    ...
  }
  ...
}
PS: Line 32 where you declare a constant, you may use
public static final int MAX_NUM = 10;
instead. The reason is that the constant should and never be able to changed in the program; especially when you allow "public" accessing. The "final" key word forces the variable to be a real constant.

Wow, that worked great!

I was thinking of using my subscriber index earlier, but I wasn't sure exactly how to implement it as the main bubblesort function doesn't have access to the subIndex variable. I never thought to pass another parameter in the function!

Thanks so much for all your help, I've learned a lot!

Taywin 312 Posting Virtuoso · Answer 11 · 2011-09-23T00:56:49+00:00

Taywin 312 Posting Virtuoso

12 Years Ago

You are welcome. Please mark it as solved :)

Bubble sort an array of objects?

Recommended Answers Collapse Answers

All 15 Replies

Recommended Answers