Быстрая сортировка чисел (строк)
Для справки я программирую Java в BlueJ,
Я довольно плохо знаком с языком, и у меня проблемы с QuickSort,
Я должен изменить свой код, чтобы он сортировал список по телефонным номерам (в данном случае это строка).
Проблема в том, что я не уверен, что именно нужно изменить, чтобы сортировать по телефонным номерам.
Я думаю, что я должен изменить эту часть, чтобы элемент раздела был 1-ым, а не средним:
partitionelement = data[middle];
Но за этим я не уверен.
В текущем состоянии сортирует список по фамилии.
Это вывод при сортировке по фамилии:
Unsorted List:
Smith, John 610-555-7384
Barnes, Sarah 215-555-3827
Riley, Mark 733-555-2969
Getz, Laura 663-555-3984
Smith, Larry 464-555-3489
Phelps, Frank 322-555-2284
Grant, Marsha 243-555-2837
Sorted via QuickSort:
Barnes, Sarah 215-555-3827
Phelps, Frank 322-555-2284
Grant, Marsha 243-555-2837
Riley, Mark 733-555-2969
Smith, John 610-555-7384
Getz, Laura 663-555-3984
Smith, Larry 464-555-3489
Это мой класс Sorting:
public class Sorting{
/**
* Swaps to elements in an array. Used by various sorting algorithms.
*
* @param data the array in which the elements are swapped
* @param index1 the index of the first element to be swapped
* @param index2 the index of the second element to be swapped
*/
private static <T extends Comparable<? super T>> void swap(T[] data,
int index1, int index2){
T temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}
/**
* Sorts the specified array of objects using the quick sort algorithm.
* @param data the array to be sorted
*/
public static <T extends Comparable<? super T>> void quickSort(T[] data){
quickSort(data, 0, data.length - 1);
}
/**
* Recursively sorts a range of objects in the specified array using the
* quick sort algorithm. The parameters min and max represent the range of
* values on which the sort is performed.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
public static <T extends Comparable<? super T>> void quickSort(T[] data,
int min, int max){
if (min < max){
// create partitions
int indexofpartition = partition(data, min, max);
// sort the left partition (lower values)
quickSort(data, min, indexofpartition - 1);
// sort the right partition (higher values)
quickSort(data, indexofpartition + 1, max);
}
}
/**
* Used by the quick sort algorithm to find the partition.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
private static <T extends Comparable<? super T>> int partition(
T[] data, int min, int max){
T partitionelement;
int left, right;
int middle = (min + max) / 2;
// use the middle data value as the partition element
partitionelement = data[middle];
// move it out of the way for now
swap(data, middle, min);
left = min;
right = max;
while (left < right){
// search for an element that is > the partition element
while (left < right && data[left].compareTo(partitionelement) <= 0)
left++;
// search for an element that is < the partition element
while (data[right].compareTo(partitionelement) > 0)
right--;
// swap the elements
if (left < right)
swap(data, left, right);
}
// move the partition element into place
swap(data, min, right);
return right;
}
}
Для справки, это мой основной класс, который является правильным, SortPhoneListQuickSort:
public class SortPhoneListQuickSort{
/**
* Creates unsorted list and sorts said list with QuickSort.
*/
public static void main (String[] args){
Contact[] friendsArray;
// List Being Sorted via QuickSort
friendsArray = Contacts();
System.out.println("Unsorted List:");
showFriends(friendsArray);
Sorting.quickSort(friendsArray);
System.out.println("Sorted via QuickSort:");
showFriends(friendsArray);
}
/**
* Prints the friends list.
*/
private static void showFriends(Contact[] friends){
for (int i = 0; i < friends.length; i++) {
System.out.println(friends[i]);
}
System.out.println();
}
/**
* Creates unsorted contacts.
*/
private static Contact[] Contacts(){
Contact[] friends = new Contact[7];
friends[0] = new Contact ("John", "Smith", "610-555-7384");
friends[1] = new Contact ("Sarah", "Barnes", "215-555-3827");
friends[2] = new Contact ("Mark", "Riley", "733-555-2969");
friends[3] = new Contact ("Laura", "Getz", "663-555-3984");
friends[4] = new Contact ("Larry", "Smith", "464-555-3489");
friends[5] = new Contact ("Frank", "Phelps", "322-555-2284");
friends[6] = new Contact ("Marsha", "Grant", "243-555-2837");
return friends;
}
}
РЕДАКТИРОВАТЬ: Кажется, мне просто нужно отредактировать contact класс вместо.
contact учебный класс:
public class Contact implements Comparable{
private String firstName, lastName, phone;
/**
* Sets up this contact with the specified information.
*
* @param first a string representation of a first name
* @param last a string representation of a last name
* @param telephone a string representation of a phone number
*/
public Contact (String first, String last, String telephone)
{
firstName = first;
lastName = last;
phone = telephone;
}
/**
* Returns a description of this contact as a string.
*
* @return a string representation of this contact
*/
public String toString ()
{
return lastName + ", " + firstName + "\t" + phone;
}
/**
* Uses both last and first names to determine lexical ordering.
*
* @param other the contact to be compared to this contact
* @return the integer result of the comparison
*/
public int compareTo (Object other)
{
int result;
if (lastName.equals(((Contact)other).lastName))
result = firstName.compareTo(((Contact)other).firstName);
else
result = lastName.compareTo(((Contact)other).lastName);
return result;
}
}
1 ответ
Решение
Было бы ужасной идеей изменить код вашего алгоритма сортировки просто для адаптации к определенному типу данных, в то время как ваш класс сортировки использует обобщенные типы.
Вы уже завернули свои данные в Contact класс, так что все, что вам нужно сделать, это реализовать Comparable<Contact> интерфейс.