Simple Java Sorting Algorithm

[Rheinwasser]

public class ArraySortieren{    public ArraySortieren(double p0, double p1, double p2, double p3, double p4, double pValue)    {             double[] array = new double[] {p0, p1, p2, p3, p4};                              array = arraySortieren(array, pValue);                for(int i = 0; i < array.length; i++)        {            System.out.println(array[i]);        }    }        public double[] arraySortieren(double pArray[], double pValue)    {                for(int i = pArray.length - 1; i > -1 && pArray[i] < pValue; i--)        {            if(i + 1 < pArray.length)            {                pArray[i + 1] = pArray[i];            }                        if(pArray[i - 1] > pValue)            {                pArray[i] = pValue;            }        }                return pArray;    }}

I came up with this in the last 15min, we just started this sorting thing in class today (last lesson before the test and this won't even be in the test but anyways..).

I want to sort pValue into the array.

I get two OutOfBoundsExceptions (5) in line seven and twelve (I've highlighted those).

Could I get some quick help? That'd be awesome since I am quite tired and can't come up with the problem myself.

Thanks a lot!

 

EDIT: Looks like you can't highlight in code, it's this piece:

array = arraySortieren(array, pValue);                for(int i = 0; i < array.length; i++)        {            System.out.println(array[i]);        }

[Nineshadow]

There's lots of methods of sorting vectors, or arrays, whatever.

The easiest one and efficient enough is bubble sort.

 

 

Now back on your problem, you're trying to access an element out of the array's size. Let's say you have one of size 7 and you're trying to access the element with index 15, even 7.

 

Remember, indexes start from 0.

[Ganz]

if(pArray[i - 1] > pValue)

I think it might be in that line.  Since you are going down in your for loop.  And you stop it when i > -1 meaning i can = 0.  Well when i =0, pArray[0-1] would be out of bounds.

[Rheinwasser]

There's lots of methods of sorting vectors, or arrays, whatever.

The easiest one and efficient enough is bubble sort.

 

-  there was a nice picture before i removed it so its easier to read which i guess it's not since you are reading this -

 

Now back on your problem, you're trying to access an element out of the array's size. Let's say you have one of size 7 and you're trying to access the element with index 15, even 7.

 

Remember, indexes start from 0.

thanks, but do you have an idea when I am trying to access an element out of the array's size?

 

if(pArray[i - 1] > pValue)

I think it might be in that line.  Since you are going down in your for loop.  And you stop it when i > -1 meaning i can = 0.  Well when i =0, pArray[0-1] would be out of bounds.

 

thanks a lot!

any idea how to solve that?

[Ganz]

thanks, but do you have an idea when I am trying to access an element out of the array's size?

 

thanks a lot!

any idea how to solve that?

 

Ok, looking at this closer there is a couple issues which have come up.  So what I you are trying to do from my understanding is sort an array of doubles based on size.  You also want to add a custom value that will then get sorted.  In your Sortieren method you are doing something that isn't allowed which is increase the size of an array (add a value you to it). I understand this is for school, so they want to teach you the manual way, but Java has built in methods which allow you to sort an array.  its Arrays.sort();  

 

Check this out this is what you want to do: http://www.tutorialspoint.com/javaexamples/arrays_insert.htm

[Rheinwasser]

 

Ok, looking at this closer there is a couple issues which have come up.  So what I you are trying to do from my understanding is sort an array of doubles based on size.  You also want to add a custom value that will then get sorted.  In your Sortieren method you are doing something that isn't allowed which is increase the size of an array (add a value you to it). I understand this is for school, so they want to teach you the manual way, but Java has built in methods which allow you to sort an array.  its Arrays.sort();  

 

Check this out this is what you want to do: http://www.tutorialspoint.com/javaexamples/arrays_insert.htm

 

ikr? that's what i first thought of but my teacher is like "we can do it better ourselves, the build in functions aren't as good etc."

i know that i am not allowed to increase the size of an array, i dont want to to that. i just dont know how to avoid it..

anyways, i'll take a look at it tomorrow.

thanks!

[madknight3]

my teacher is like "we can do it better ourselves, the build in functions aren't as good etc."

 

Maybe in certain cases but I doubt it in general. It would be interesting to hear your teachers reasoning and algorithm choices and why they are faster though.

[Guest]

my teacher is like "we can do it better ourselves, the build in functions aren't as good etc."

 

Laughably false. I'm all for learning by experimenting, but Java's implementations are based on widely known and perfected algorithms.

 

For fun; here's a simple implementation of Quicksort that I did while taking data structures.

public class Quicksort {  public static void sort(int[] array) {    int p, r;    p = 0;    r = array.length - 1;    sort(array, p, r);  }  private static void sort(int[] array, int p, int r) {    int pivot;    if (p < r) {      pivot = partition(array, p, r);      sort(array, p, pivot - 1);      sort(array, pivot + 1, r);    }  }  private static int partition(int[] array, int p, int r) {    int x, i;    x = array[r];    i = p - 1;    for (int j = p; j < r; ++j) {      if (array[j] <= x) {        ++i;        swap(array, i, j);      }    }    swap(array, i + 1, r);    return i + 1;  }  private static void swap(int[] array, int a, int b) {    int tmp;    tmp = array[a];    array[a] = array[b];    array[b] = tmp;  }}

import java.util.Arrays;public class Sorting {  public static void main(String[] args) {    int[] array = { 2, 8, 7, 1, 0, 3, 5, 6, 4, 9 };    System.out.println(Arrays.toString(array));    Quicksort.sort(array);    System.out.println(Arrays.toString(array));  }}

[Rheinwasser]

Maybe in certain cases but I doubt it in general. It would be interesting to hear your teachers reasoning and algorithm choices and why they are faster though.

 

 

 

Laughably false. I'm all for learning by experimenting, but Java's implementations are based on widely known and perfected algorithms.

 

For fun; here's a simple implementation of Quicksort that I did while taking data structures.

 

ikr?

its not like the people how developed and develop java are total idiots.

but there is not really a way to argue against my teacher when he's like: i am the teacher and i know everything better..

and its probably not even his fault, the goverment here in germany tells us that we have to do multiple sorting algorithms in informatics class.

[madknight3]

ikr?

its not like the people how developed and develop java are total idiots.

but there is not really a way to argue against my teacher when he's like: i am the teacher and i know everything better..

and its probably not even his fault, the goverment here in germany tells us that we have to do multiple sorting algorithms in informatics class.

 

I don't think it's a bad thing to know how sorting algorithms work and how to implement them yourself. It's something everyone who takes computer science will learn and is a good way to discuss certain topics. It's just not likely that you'd cover anything in school that will compete with what the developers who wrote Arrays.sort() will have done.

 

With that said, the Arrays.sort() may do more than you need to account for in your current class. So if given specific constraints, it's certainly possible to beat their implementation which accounts for everything. The Arrays.sort() does the following in the case of a double array (in Java 8):

sort(...) {    // Phase 1: Move NaNs to the end of the array.    ...    // Phase 2: Sort everything except NaNs (which are already in place).    ...    // Phase 3: Place negative zeros before positive zeros.    ...}

So if you know you didn't have to worry about NaNs (not a number) and negative zeros, then you could ignore phase 1 and 3. Therefore you have the potential to do less work and beat it in terms of speed if you provide an equal or better algorithm for phase 2. That is easier said than done. Phase 2 implements a Dual-Pivot Quicksort which is a very efficient sorting algorithm (don't worry about understanding it, I just posted the link for reference).

 

One thing it does though is use an insertion sort on very small arrays which is one sorting algorithm you should learn in class. The link above defines a "very small array" as one with a length < 17 but the Java source code defines it as one with a length < 47. Now in order to get to the insertion sort, it has to make a few (inexpensive) decisions to get there. So if you know your arrays will never be larger than this, you may be able to implement an insertion sort that is equal to or better than theirs because you don't have to make those same decisions.

 

The only criteria left is that your implementation of insertion sort is equal to or better than theirs. So that means you would be left with

sort(...) {    // Phase 1: Not needed    // Phase 2: No decisions needed, just do an insertion sort    ...    // Phase 3: Not needed}

So that's about the only way I can see you having a faster sorting algorithm than Arrays.sort() but it's not really a fair comparison now is it? The more constraints you are given, the more optimized you can make an algorithm.

[Rheinwasser]

I don't think it's a bad thing to know how sorting algorithms work and how to implement them yourself. It's something everyone who takes computer science will learn and is a good way to discuss certain topics. It's just not likely that you'd cover anything in school that will compete with what the developers who wrote Arrays.sort() will have done.

 

With that said, the Arrays.sort() may do more than you need to account for in your current class. So if given specific constraints, it's certainly possible to beat their implementation which accounts for everything. The Arrays.sort() does the following in the case of a double array (in Java 8):

sort(...) {    // Phase 1: Move NaNs to the end of the array.    ...    // Phase 2: Sort everything except NaNs (which are already in place).    ...    // Phase 3: Place negative zeros before positive zeros.    ...}

So if you know you didn't have to worry about NaNs (not a number) and negative zeros, then you could ignore phase 1 and 3. Therefore you have the potential to do less work and beat it in terms of speed if you provide an equal or better algorithm for phase 2. That is easier said than done. Phase 2 implements a Dual-Pivot Quicksort which is a very efficient sorting algorithm (don't worry about understanding it, I just posted the link for reference).

 

One thing it does though is use an insertion sort on very small arrays which is one sorting algorithm you should learn in class. The link above defines a "very small array" as one with a length < 17 but the Java source code defines it as one with a length < 47. Now in order to get to the insertion sort, it has to make a few (inexpensive) decisions to get there. So if you know your arrays will never be larger than this, you may be able to implement an insertion sort that is equal to or better than theirs because you don't have to make those same decisions.

 

The only criteria left is that your implementation of insertion sort is equal to or better than theirs. So that means you would be left with

sort(...) {    // Phase 1: Not needed    // Phase 2: No decisions needed, just do an insertion sort    ...    // Phase 3: Not needed}

So that's about the only way I can see you having a faster sorting algorithm than Arrays.sort() but it's not really a fair comparison now is it? The more constraints you are given, the more optimized you can make an algorithm.

thanks!

that helped a lot.

i dont really criticize that we talk about sorting algorithms but this will basically be the topic for the next year or so. and, i my opinion at least, there are more important things that every programming beginner should be taught. code to learn, not learn to code.

[madknight3]

i dont really criticize that we talk about sorting algorithms but this will basically be the topic for the next year or so. and, i my opinion at least, there are more important things that every programming beginner should be taught.

 

Without knowing your curriculum or the reasoning behind why it's being taught I can't really agree or disagree. It's hard to imagine that much time being dedicated to just sorting algorithms though.

[SteveGrabowski]

There's lots of methods of sorting vectors, or arrays, whatever.

The easiest one and efficient enough is bubble sort.

 

 

Now back on your problem, you're trying to access an element out of the array's size. Let's say you have one of size 7 and you're trying to access the element with index 15, even 7.

 

Remember, indexes start from 0.

 

OMG, I have a friend who actually brought up this garbage algorithm in a job interview. I could have strangled him when he said it.

[Nineshadow]

OMG, I have a friend who actually brought up this garbage algorithm in a job interview. I could have strangled him when he said it.

If you're showing it in a job interview then you're doing it wrong.

 

It's just the simplest sorting algorithm to implement and understand.

[SteveGrabowski]

If you're showing it in a job interview then you're doing it wrong.

 

It's just the simplest sorting algorithm to implement and understand.

 

To me selection sort would be the most intuitive. E.g.,

 

1. Find the smallest element in A[1 .. n] and put it in A[1]

2. Find the smallest remaining element in A[2 .. n] and put it in A[2]

...

n. The smallest remaining element in A[n .. n] is A[n]. Done.

 

Plus this one is actually useful since if you use a heap instead of an array as the data structure you get an N log N algorithm in heapsort.