Bubble-Sort with 2D Array

Question

Howdy, I do know how to implement a simple bubble-sort for 1dimensional array. But with 2dimensional or multidimensional, that's where I have my problems.

So far I've been using this to sort 1Dimensional Arrays, works like a charm. But mostly with integer numbers, not strings:

boolean sort;

do{
    sort = true;

    for (int i = 0; i < testarray.length - 1; i++){
        if(testarray[i] > testarray[i+1]){
            temp = testarray[i];
            testarray[i] = testarray[i+1];
            testarray[i+1] = temp;           
            sort = false;
        }
    }

}while(!sort);

    // Descending Output
    // for (int k = testarray.length - 1; k >= 0 ; k--){

    // Ascending Output
    for (int k = 0; k < testarray.length ; k++){
        System.out.print(testarray[k] + ", ");
    }

Assuming I have:

Customernumber, Name, Surname, Address

String customers[][] = {{"123", "John", "Doe", "Somewhere"}, {"007", "James", "Bond", "MI5"}, {"1337", "Lolcat", "Izgud", "Saturn"}}

Now, I want to choose to sort what to sort after: customernumber, name, surname or address. And after that I want to output it ascending or descending, depending what I want.

I just have no idea how to implement this with bubble-sort. I want to stay in bubble-sort, , no other sorting algorithm, I want to learn how bubble-sort works in such a situation.

For ascending and descending my idea would be: I could do an if-Loop. For example if (asc == 1) then output ascending, else output descending. The asc would then be asked via Console for example.

Any help is much appreciated.

Answer 1

A 2 dimensional array is basically just a 1 dimensional array consisting of arrays.

Just use the same code you have, only instead of ints, move the inner arrays.

To know if one array is 'bigger' than the next, compare the string values of the correct array member (so the name or surname,..). To do this you can use the String CompareTo method.

Last note: The example you gave is better if the inner array is actually an Object containing the info. This way you can have separate Datatypes for all the fields instead of all making them Strings.

e.g.:

  class Person
  {
       int customerNumber;
       String name;
       String surName;
       String address;
  };

EDIT: to actually answer your question:

change your program as following:

change the temp declaration:

 String [] temp;

and change the line:

 if(testarray[i] > testarray[i+1])

into:

 if(testarray[i][1] > testarray[i+1][1])

than it 'll work and sort on the name

R

Answer 2

In a 2D array, the type of your contained objects changes from int or Integer to String[] (note: that's an array of Strings). This is what you'll need to change the type of temp to.

The biggest change will be to your comparison. You can't just compare two String arrays using < – but you already knew this. What you need to do is build yourself a method that takes two String[] arguments and returns a negative, 0 or positive number depending on whether the first is smaller/equal/larger than the second. You can then do a < / > comparison on the result from that method to establish your sort order.

If you want to be able to use several different sort criteria, you'll either need to make the comparison function more versatile by (e.g.) passing in another parameter to tell it how to work, or you'll need several different comparison functions, and use an if or switch to decide which one to use during the sort.

As for manually comparing two String arrays, the basic method is: Compare the first key strings using String.compareTo(). If the result is not 0, return that. If it is 0, then the first keys are equal and you need to compare the next keys. If you run out of keys and are still at 0, your two elements are equal on their keys and you return the 0.

Answer 3

You can keep the same sorting algorithm. It will still be unaware of the 2D array. You have to come up with a comparison function that takes two 1D arrays and says which one is the greater.

Answer 4

I'm guessing you want "123", "john", "doe" and "somewhere" to be grouped together.

I suggest you use an object, say

public object Person {
    private int id;
    private String name;
    private String surname;
    private String address;
}

adding the usual getters and setters.

you can have an ordinary array of Person objects, sorting them with your bubble sort algorithm. You can create several custom comparators that compare either id, name, surname or address to you bubble sort algo.

The signature of the sort method should be something like

public Person[] bubbleSort(Person[] persons, Comparator comp)