Member Avatar for Newskin01

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
  • 2K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by jon.kiparsky
Member Avatar for JamesCherrill

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).

Member Avatar for yancouto

I think the attachment will help you. I read a book about Java and it talked about this, so this is the code to do it.
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.

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];
	}
}
Member Avatar for Newskin01

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.

Member Avatar for DarkLightning7

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 because: n/a
Member Avatar for jon.kiparsky

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.

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.