How to get my array to sort properly? Recursive Sorting

Question

After many times to try to solve this issue, I can't seem to solve my dilemma. When trying to run my program, the unsorted array will not sort when printing "Sorted Array". Is there something that I'm doing wrong?

public class RecursiveSorter {

    private int[] sortedArray;
    private int[] array;

    public RecursiveSorter() {
        array = new int[1];
    }

public RecursiveSorter(int[] a) {
    array = a;
}

public void setArray(int[] a) {
    array = a;
}

public int[] getSortedArray() {
    return sortedArray;
}

public int[] getOriginalArray() {
    return array;
}

public int[] sort() {
    sortedArray = array;
    recursiveSort(sortedArray.length - 1);
    return sortedArray;
}

public int[] recursiveSort(int endIndex) {
    if (endIndex > 0) {
        int m = getMaxIndex(endIndex, sortedArray);
        swap(m, endIndex, sortedArray);
        recursiveSort(endIndex-1);
    }
    return sortedArray;
}

public int getMaxIndex(int endIndex, int[] a) {
    int max = a[0];
    int maxIndex = 0;
    for (int i = 1; i < endIndex; i++) {
        if (a[i] < max) {
            max = a[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}
//Changed it to make sure that it is swapping the elements correctly
public void swap(int src, int dest, int[] a) {
    if(dest <= src)
    {
    int temp = a[dest];
    a[dest] = a[src];
    a[src] = temp;

     dest++;
     src++;
    }
}

public String toString() {
    return "Original: " + prettyPrint(getOriginalArray()) + "\n" +
           "Sorted:   " + prettyPrint(getSortedArray());
}

private String prettyPrint(int[] a) {
    String s = "";
    for (int i : a)
        s += i + " ";
    return s;
}

public static void main(String[] args) {
    // Automate running, but not testing
    int[] array = {5, 67, 12, 20};
    RecursiveSorter s = new RecursiveSorter(array);
    s.sort();
    System.out.println(s); // uses Sorter.toString
}

}

There are multiple problems with your code. First of all: sortedArray = array: keep in mind, that an array is an object. With this statement, you do not copy the array, but array and sortedArray reference to the same memory adress. Look into at System.arraycopy. Can you explain your sort algorithm? This makes debugging easier. — Turing85
– Turing85, Commented Apr 8, 2015 at 20:30

T.Gounelle · Accepted Answer · 2015-04-08 20:50:50Z

2

You have 3 problems. 2 are in getMaxIndex(): you were not including the last element in the test for the max, and the test for max is not the right. You are computing the min.

public int getMaxIndex(int endIndex, int[] a) {
    int max = a[0];
    int maxIndex = 0;
    for (int i = 1; i <= endIndex; i++) {   // use <= instead of <
        if (a[i] > max) {                   // change < in >
            max = a[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}

And one problem in swap()

public void swap(int src, int dest, int[] a) {
    if(src <= dest)      // reverse src and dest
    {
        int temp = a[dest];
        a[dest] = a[src];
        a[src] = temp;

        dest++; // no use, dest is local
        src++; // idem
    }
}

Then you will have:

Original: 5 12 20 67 Sorted: 5 12 20 67

Actually the orginal array is modified because array and sortedArray reference the same array of int. There is no copy in Java. When you do

public int[] sort() {
    sortedArray = array;
    recursiveSort(sortedArray.length - 1);
    return sortedArray;
}

sortedArray points to the same int[] as array. If you want to keep the orginal one, you need to explicitly do a copy, for instance with System.arrayCopy(...).

answered Apr 8, 2015 at 20:50

T.Gounelle

6,0631 gold badge24 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ricardo Desu Perez Over a year ago

@OMG Thank you so much! :D I didn't realize that I did some of that stuff reversed. Once again, thank you! You saved me so much time and aggravation.

Turing85 · Accepted Answer · 2015-04-08 20:46:57Z

1

I traced the problem down to two points:

first, you have an unnecessary if in swap(...):

public void swap(int src, int dest, int[] a)
{
    // if(dest <= src)
    // {
        int temp = a[dest];
        a[dest] = a[src];
        a[src] = temp;

    //     dest++;
    //     src++;
    // }
}

Second, you have a little bug in the for loop of getMaxIndex(...):

public int getMaxIndex(int endIndex, int[] a)
{
    int max = a[0];
    int maxIndex = 0;
    for (int i = 1; i <= endIndex; i++) // substituted < with <=
    {
        if (a[i] < max)
        {
            max = a[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}

With these changes (and mentionded System.arraycopy), the algorithm should work as intended.

edited Apr 8, 2015 at 20:46

answered Apr 8, 2015 at 20:41

Turing85

20.3k7 gold badges41 silver badges66 bronze badges

1 Comment

Ricardo Desu Perez Over a year ago

Thank you :) I really do achieve you helping me by the way. However, according to my assignment, my professor wanted me to use an if statement for some odd reason. I did use your advice when pointing out that endIndex needed to changed to <= . My program is running fine now :D thanks dude.

saravanakumar · Accepted Answer · 2015-04-08 20:29:59Z

-2

Why you are not sing

// sorting array in #java.util.Arrays;
Arrays.sort(array);

And dont need to recusive call and all

If you need to write your own code, then Choose any sorting algorthim, implement that one by your own.

private static void sort(int[] array){
 boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
    swapped = false;
    j++;
    for (int i = 0; i < array.length - j; i++) {
        if (array[i] > array[i + 1]) {
            tmp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = tmp;
            swapped = true;
        }
    }
}

}

answered Apr 8, 2015 at 20:29

saravanakumar

1,7784 gold badges21 silver badges39 bronze badges

Collectives™ on Stack Overflow

How to get my array to sort properly? Recursive Sorting

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related