[Wolfy200222]

Hey,

I'm experimenting with sorts and I've coded a quicksort algorithm taking an array of integers read in by file. My file generator generates numbers by random so the length of the array is not known.
My question is I want to be able to create an array with every value below the pivot value and likewise with the values higher than the pivot.

How would I be able to do this? It seems so simple that I've mind blocked.

Regards and thanks

Dan

[macosxnerd101]

Since I'm not sure what language you are working in, I'll move this to Computer Science.

A lot of languages have dynamic arrays or resizable Lists of some sort that you can use. In Java, there is the ArrayList class, which you will probably want to use.

[Wolfy200222]

Ahh sorry I should have specified the language - The language in question is Java

I considered using an ArrayList but at the moment experimenting with different takes on the problem.

Regards and thanks

Dan

[Dogstopper]

Moved back to Java.

Take a look at the ArrayList methods to see if you can find the methods you need:
http://download.orac.../ArrayList.html

[Wolfy200222]

Thanks for another quick reply - A final problem I have (a bit off topic but maybe you could help), while sorting I have to stop the sort to execute another sort that could handle smaller numbers more efficiently. The number entered will be entered at runtime so a simple input reader should handle this if I am right?
I'm also thinking that when sorting the higher and lower partitions that before running the method, to try a check if (index0 - (pivot -1)) <= input, then run other searching method, however - I do not know how I would return to the loop afterwards to carry on the sort of the rest of the data.

I'm not asking for help per se with the above, just a friendly nudge in the right direction and if my method of thinking is correct.

Regards and thanks

Edit: I know that the check would be before the loop, but skipping a partition would be troublesome

This post has been edited by Wolfy200222: 16 April 2011 - 09:43 AM

[macosxnerd101]

Quote

to execute another sort that could handle smaller numbers more efficientl

Do you mean arrays or Collections holding fewer elements? Insertion sort is a good algorithm for elements with less than 10 or 15 elements. It doesn't have a lot of overhead for small Collections or arrays. Just check if the array length or Collection size() is < 15 or so, and execute insertion sort. Otherwise, partition and recurse for Quicksort.

Quote

I'm also thinking that when sorting the higher and lower partitions that before running the method, to try a check if (index0 - (pivot -1)) <= input, then run other searching method

I'm not sure I understand the purpose of a searching algorithm in your sorting code. What is your reasoning for this?

[Wolfy200222]

The amount of data that has to be sorted ranges from 10,000 ints to 5 million, I figured that a quicksort will be handy dealing with the larger numbers but how my code works, it works out the pivot then sorts the left side calling the method then right side of the pivot and carries on via recursion(sp?). Anyway I wanted to set it so when the partition size reaches a smaller/certain number, to have another sort handle it more efficiently, (which I am researching now).

My assumption was, for example, when the lower partition met the size stated by a check, that it would break the loop leaving three quarters or the majority unsorted.

So I was wondering if anyone knew of a built in feature of Java or something to google; rather than ask for code exactly, on how I would make sure that the entire array was sorted.

Edit: Nevermind you answered my question, thanks

This post has been edited by Wolfy200222: 16 April 2011 - 11:56 AM

[macosxnerd101]

Glad I could help!