Hello,
I need to perform a binary search on an array of objects but to do so I need to have them sorted.
I've been looking online and no one really has a good explanation of how to conduct a quick sort on an array of objects. If you can direct me to a good tutorial that would be great.

Friends[] = new Friends[10]
is an example of my array.

Pretty much I just want to be able to say myarray.quickSort() and it sorts it. Picking a random piv point.
Therefore I can call it w.e needed. I'm just stuck on how I would write it. I know it's a divide and conqueror algo.

Thanks. (Also, I am not using ArrayList)

5
Contributors
5
Replies
7
Views
7 Years
Discussion Span
Last Post by jon.kiparsky

Have a look at the Arrays class - it has sort methods for arrays (and binary searches). You just need to implement a compareTo method for your Friends class (you'll find docs and examples in all the usual places).

The program uses recursion to divide the array into two and use the pivot to put the bigger numbers in one side, and the smaller in another, then it does that again with each part until your array is sorted.

Attachments
``````public class QuickSortApp
{
public static void main(String[] args)
{
int LEN = 100;
int[] unsorted = new int[LEN];
for (int i = 0; i<LEN; i++)
unsorted[i] = (int)(Math.random() * 100) + 1;
System.out.println("Unsorted array:");
printArray(unsorted);
int[] sorted = sort(unsorted);
System.out.println("\n\nSorted array:");
printArray(sorted);
}

private static void printArray(int[] array)
{
System.out.println();
for (int i = 0; i < array.length; i++)
{
if (array[i] < 10)
System.out.print(" ");
System.out.print(array[i] + " ");
if ((i+1) % 20 == 0)
System.out.println();
}
}

private static int[] a;

public static int[] sort(int[] array)
{
a = array;
sort(0, a.length - 1);       // sort the entire array
return a;
}

public static void sort(int low, int high)
{
if (low >= high)
return;
int p = partition(low, high);
sort (low, p);
sort (p+1, high);
}

public static int partition(int low, int high)
{
int pivot = a[low];

int i = low - 1;
int j = high + 1;

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

public static void swap(int i, int j)
{
//int temp = a[i];
//a[i] = a[j];
//a[j] = temp;
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}``````

Alright I can't use the sort thing. I have to do a quicksort. Implement Comparable on my abstract class.

My program looks like this

Abstract House

Then three leaves red, blue and green. They are all houses.

I need to implement Comparable on abstract house class yet when I do this it says in red,blue,green that I do not override the compareTo() method. So what should I do there.

Back to the quicksort I need to compare the houses by using the compareTo and then they will be sorted to what comes first in the dictionary.

You can have 10 houses on a plot of land, thus I have a land class with an array house[] = new house[10];

This is where I need to put this quicksort method. However, I'm not sure how.

To fix your problem with comparable simply override the parent's compareTo() method by naming a method in the child class the same as the parent's method or call the parents method using the super keyword like this.

``super.compareTo();``

this may not solve your problem I am only guessing at what is wrong because you did not give me any code to work with.

What do you want to sort them by? As in what properties(e.g. color, name, size, . . .) define your object sort(what do you want to sort them by)? Do you want to create a general sort method that you can enter in a number or string and it will sort the objects by that property?

Edited by DarkLightning7: n/a

I'm not sure what it is you're after here, but if you put a compareTo method in the abstract superclass or in each of the derived classes (if they sort differently) then you're good on comparable.

If you need to implement quicksort, it's simple enough in principle, yancouto gave you a very good summary of the basic idea. Break it down to component parts and write and test them before you try to combine the whole thing, that'll save you some headache.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.