Writing a recursive sorting algorithm of an array of integers

Question

I am trying to write a recursive sorting algorithm for an array of integers. The following codes prints to the console: 3, 5, 2, 1, 1, 2, 6, 7, 8, 10, 20

The output should be sorted but somehow "it doesn't work".

public static void main(String[] args)
{
    int[] unsortedList = {20, 3, 1, 2, 1, 2, 6, 8, 10, 5, 7};
    duplexSelectionSort(unsortedList, 0, unsortedList.length-1);

    for (int i = 0; i < unsortedList.length; i++)
    {
        System.out.println(unsortedList[i]);
    }
}


public static void duplexSelectionSort(
    int[] unsortedNumbers,
    int startIndex,
    int stopIndex)
{
    int minimumIndex = 0;
    int maximumIndex = 0;

    if (startIndex < stopIndex)
    {
        int index = 0;
        while (index <= stopIndex)
        {
            if (unsortedNumbers[index] < unsortedNumbers[minimumIndex])
            {
                minimumIndex = index;
            }
            if (unsortedNumbers[index] > unsortedNumbers[maximumIndex])
            {
                maximumIndex = index;
            }
            index++;
        }
        swapEdges(unsortedNumbers, startIndex, stopIndex, minimumIndex, maximumIndex);
        duplexSelectionSort(unsortedNumbers, startIndex + 1, stopIndex - 1);
    }
}


public static void swapEdges(
    int[] listOfIntegers,
    int startIndex,
    int stopIndex,
    int minimumIndex,
    int maximumIndex)
{
    if ((minimumIndex == stopIndex) && (maximumIndex == startIndex))
    {
        swap(listOfIntegers, startIndex, stopIndex);
    }
    else
    {
        if (maximumIndex == startIndex)
        {
            swap(listOfIntegers, maximumIndex, stopIndex);
            swap(listOfIntegers, minimumIndex, startIndex);
        }
        else
        {
            swap(listOfIntegers, minimumIndex, startIndex);
            swap(listOfIntegers, maximumIndex, stopIndex);
        }
    }
}

public static void swap(int[] listOfIntegers,
    int index1,
    int index2)
{
    int savedElementAtIndex1 = listOfIntegers[index1];
    listOfIntegers[index1] = listOfIntegers[index2];
    listOfIntegers[index2] = savedElementAtIndex1;
}

dreamcrash · Accepted Answer · 2013-02-05 12:29:02Z

The merge sort is an well-known recursive algorithm that you can take ideas from to do your own recursive sort algorithm:

public void mergeSort(int[] data) {
    if(data.length <= 1) return;               // Base case: just 1 elt

    int[] a = new int[data.length / 2];        // Split array into two
    int[] b = new int[data.length - a.length]; //   halves, a and b
    for(int i = 0; i < data.length; i++) {
        if(i < a.length) a[i] = data[i];
        else             b[i - a.length] = data[i];
    }

    mergeSort(a);                              // Recursively sort first
    mergeSort(b);                              //   and second half.

    int ai = 0;                                // Merge halves: ai, bi
    int bi = 0;                                //   track position in
    while(ai + bi < data.length) {             //   in each half.
        if(bi >= b.length || (ai < a.length && a[ai] < b[bi])) {
            data[ai + bi] = a[ai]; // (copy element of first array over)
            ai++;
        } else {
            data[ai + bi] = b[bi]; // (copy element of second array over)
            bi++;
        }
    }
}

Patricia Shanahan · Accepted Answer · 2012-11-19 01:07:43Z

1

You need to remember when initializing variables in your recursive method that you are working on the startIndex through stopIndex slice of the array, not the whole array, and you should not be touching anything outside that slice.

Take another look at the initialization of index, minimumIndex, and maximumIndex in your duplexSelectionSort method.

answered Nov 19, 2012 at 1:07

Patricia Shanahan

26.2k4 gold badges42 silver badges75 bronze badges

Comments

Deepak · Accepted Answer · 2016-02-05 04:20:13Z

0

This is one type of recursive sorting that I tried. Hope this helps. On similar lines to your code, but I feel a bit less complicated.

public static void main(String[] args)
{
int [] array = {5,9,2,3,10,20,1,7};
int len = array.length-1;
sort(array, 0, len);
for(int i=0;i<=len;i++)
{
  System.out.println(array[i]);
}
}

public static void sort(int[] array, int start, int end)
{
if (start < end)
{
  sort(array, start+1, end);
  if(array[start]<=array[end])
  {
    sort(array, start, end-1);
  }
  else if(array[start]>array[end])
  {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    sort(array, start, end-1);
  }
}
else if(start == end)
  return;
}

answered Feb 5, 2016 at 4:20

Deepak

31 silver badge5 bronze badges

Comments

Donggun Jung · Accepted Answer · 2016-06-12 05:42:33Z

You can also use selection sort method.

It is good algorithm to apply recursive style.

public static int FindMinIndex(int[] data, int x, int y){

    int mini;

    if(x==y){
        mini=x;
    }

    else{
        int tempmini=FindMinIndex(data, x+1, y);
        if (data[tempmini]<data[x]){
            mini=tempmini;
        }
        else{
            mini=x;
        }
    }
    return mini;
}

//Do selection sort between data[x]~data[y]
public static void SelectionSort(int[] data, int x, int y){

    if (x==y){
        return;
    }

    else{
        int index=FindMinIndex(data, x, y);

        int temp=data[index];
        data[index]=data[x];
        data[x]=temp;

        SelectionSort(data,x+1,y);
    }

}

Bohemian · Accepted Answer · 2012-11-19 01:15:13Z

-2

To sort an array from smallest the largest, do this:

Arrays.sort(array);

answered Nov 19, 2012 at 1:15

Bohemian♦

427k103 gold badges603 silver badges750 bronze badges

1 Comment

Kitsune Over a year ago

It looks like his goal is more so to write a sort himself, as opposed to just using pre-made code.

Collectives™ on Stack Overflow

Writing a recursive sorting algorithm of an array of integers

5 Answers 5

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related