Creating a QuickSort for an Array of names

Question

So I am working on a project for my class and I am currently stuck on creating a QuickSort class to sort an Array of 1000 names. I have a template I am using from a previous Lab we did in class which we are supposed to base it off of; but in the lab we used an array of Integers and I am struggling with how to convert it so it will work with Strings; names. Thanks for your help or any suggestions, the code is below.

Updated post; So I made my comparison in my Name class

 public int compareTo(Object other) {
        int result;
        if (name.equals(((Name) other).name))
            result = name.compareTo(((Name) other).name);
        else
            result = name.compareTo(((Name) other).name);

        return result;
    }

And I've tried to re-work my QuickSort..I'm struggling with the swap method.

    private ArrayList<Name> data;

public QuickSort(ArrayList<Name> initialValue){

    data=initialValue;
}

public void sort(ArrayList<Name> namelist, int i, int j){

    sort(0, data.size()-1);
}

public void sort(int from, int to){

    if (from >= to)
        return;
    int p = partition(from, to);
    sort(from, p);
    sort( p + 1, to);
}

private int partition(int from, int to){

    Name pivot = data.get(from);
    int i = from - 1;
    int j = to + 1;

    while(i<j){

        i++; while(data.get(i).compareTo(pivot) < 0) i++;
        j--; while(data.get(j).compareTo(pivot) < 0) j--;
        if(i<j) swap(i,j);

    }

    return j;
}

private void swap (int i, int j){

    Name temp = data.get(i);
    data.equals(i) = data.get(j);
    data = temp;

}

particularly the "data.equals(i) = data.get(j) line and the data = temp; I am sure i'm doing something stupid and easy.

update;

private void swap (int i, int j){

    Name temp = data.get(i);
    data.get(j).equals(data.get(i));
    data.get(j).equals(temp);

}

possibly?

Answer 1

You will have to set a String value to compare it to something. So by setting the pivot value to compare it to itself it will return zero. Since it is unlikely that all Strings will equal your pivot value then anything compared to pivot value will be returned as -1 OR 1. By doing this your if statement will determine which way the swap value is sent( Higher OR Lower) then your pivot value.

    ObjectQuickSorter sortStrings = new ObjectQuickSorter();
    sortStrings.sort(arrayHere);

    class ObjectQuickSorter{

    void sort(String[] array){
        doQuickSort(array, 0, array.length -1);
    }

    private static void doQuickSort(String[] array,int start, int end){
        int pivotPoint;

        if(start < end){
            pivotPoint = partition(array, start, end);

            doQuickSort(array, start, pivotPoint -1);

            doQuickSort(array, pivotPoint + 1, end);
        }
    }

    private static int partition(String[] array, int start, int end){
        String pivotValue;
        int endOfLeftList;
        int mid = (start + end)/2;

        swap(array, start, mid);

        pivotValue = array[start];

        endOfLeftList = start;

        for(int scan = start + 1; scan <= end; scan++){
            // trying to compare pivot = string value to array[scan] position value
            // doing this by setting pivot value compare to itself to return 0
            // then also comparing pivot value to array[scan] to return -1, 0, 1
            // if return is 0 or 1 then it ignores it
            if(  array[scan].compareTo(pivotValue) < array[start].compareTo(pivotValue)){
                endOfLeftList++;
                swap(array, endOfLeftList,scan);
            }
        }

        swap(array, start, endOfLeftList);

        return endOfLeftList;
    }

    private static void swap(String[] array, int a, int b){
        String temp;

        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

Answer 2

Posting the code that will solve the problem would be easy but won't help you to learn the meaning of QuickSort (or another sorting algorithm).

The heart of the QuickSort is exchanging the elements here:

while(i<j){
    i++; while(data[i] < pivot) i++;
    j--; while(data[j] > pivot) j--;
    if(i<j) swap(i,j);
}

As you can see, you're comparing the elements of the data array against the pivot variable. Since they're ints, you can easily compare them using <. Now, you have to do something similar but for Strings. Thankfully, Strings can be compared using String#compareTo method. I'll let you this implementation for String (otherwise I will present the homework assignment as mine =P).

For a more generic solution to the problem, you have two options:

• Making your class implement the Comparable interface, so you will have a compareTo method. A basic sample implementation:

  public class Name implements Comparable<Name> {
      @Override
      public int compareTo(Name name) {
          return ... //comparison logic...
      }
  }
  

  Using it in your QuickSort

  pivot.compareTo(...);
  

• Using an instance of Comparator interface. You will use Comparator#compare for this. A basic sample implementation:

  public class NameComparator implements Comparator<Name> {
      @Override
      public int compare(Name name1, Name name2) {
          return ... //comparison logic...
      }
  }
  

  Using it in your QuickSort

  NameComparator nameComparator = new NameComparator();
  nameComparator.compare(..., ...);
  

Answer 3

Note that in string comparison is by equals method:

data.get(j) == pivot => data.get(j).equals(pivot)

Answer 4

You can use a comparator: Comparator.compare(o1, o2) returns -1, 0 or 1 if the objects are less, equal or greater.

Strings in java are actually comparable, some sort of a companion interface:

 int compareTo(T other);

API Do: http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html