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

Dani AI

Generated

Nice project. Two quick fixes will unblock you. First, settle Comparable on the abstract base. Your error about Red/Blue/Green not overriding compareTo() happens when the abstract superclass declares Comparable but does not provide a concrete compareTo. Either implement it in the superclass, or make every concrete subclass implement it. A tidy pattern is to make the superclass finalise compareTo and delegate the key:

abstract class House implements Comparable<House> {
    protected abstract String sortKey(); // e.g., name used for dictionary order
    @Override
    public final int compareTo(House other) {
        if (other == null) throw new NullPointerException("other");
        return this.sortKey().compareToIgnoreCase(other.sortKey());
    }
}

Now subclasses just implement sortKey() and you are Comparable everywhere. (Re : calling super.compareTo(x) only helps if the superclass already implements it, and you must pass the argument.)

Second, here is a compact in-place quicksort for your House[] in your Land class. It picks a random pivot, partitions, and recurses:

class Land {
    private static final java.util.Random RNG = new java.util.Random();

    static void quickSort(House[] a) { quickSort(a, 0, a.length - 1); }

    private static void quickSort(House[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = lo + RNG.nextInt(hi - lo + 1);
        House pivot = a[p];
        swap(a, p, hi);
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (a[j].compareTo(pivot) <= 0) swap(a, i++, j);
        }
        swap(a, i, hi);
        quickSort(a, lo, i - 1);
        quickSort(a, i + 1, hi);
    }

    private static void swap(House[] a, int i, int j) { House t = a[i]; a[i] = a[j]; a[j] = t; }
}

Tips: handle nulls explicitly if they can appear; quicksort is not stable, so add a tiebreaker in compareTo if equal keys matter. After sorting, implement your binary search over the same compareTo contract. As noted, libraries exist, but since you must code it, ’s advice to build and test each piece separately will save time.

Recommended Answers

All 5 Replies

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.