Recursive sort, using two functions

Question

Im trying to write a program to perform a recursive sort on a string using only 2 processes:

Move the last character to the front and have everything else shift to the right.
Swap the first and second character in the array.

so for example if i have a char array {"b","e","c","a","d"};

In this test case the program would perform the processes in following order: 2111212 to eventually get the desired output ("abcde").

Im trying to figure out what program logic I need to use to achieve this behavior, here is what I tried so far:

private static int sort(String[] items, String[] target, int first, int last) {
    if(Arrays.equals(target, items)) {
        return 1;
    }
    else if(items[first].compareTo(items[last]) > 0) {
        String temp = items[last];
        for(int i = last-1; i >= 0; i--) {
            items[i+1] = items[i];
        }
        items[first] = temp;
        System.out.print("s ");
        System.out.println(Arrays.toString(items));
        return sort(items,target,first,last);
    }
    else if (items[first].compareTo(items[first+1]) < 0){
        String temp = items[first];
        items[first] = items[first+1];
        items[first+1] = temp;
        System.out.print("b ");
        System.out.println(Arrays.toString(items));
        return sort(items,target,first,last);
    }
    return 2;
}

The output isn't quite correct, I think I have a logical error in there somewhere.

The rules seem oriented to an iterative process, not a recursive one. Is recursion a requirement? As already answered, any adjacent swap method like bubble sort could be used. — rcgldr
– rcgldr, Commented Jan 31, 2016 at 1:25
I did some pretty drastic reformatting of the question. OP if you feel that this compromises the intent of your post you can roll it back in the revision history. — Magisch
– Magisch, Commented Feb 6, 2016 at 16:09

rcgldr · Accepted Answer · 2016-02-08 18:45:03Z

The rules restrict the operation to swapping the first pair of elements, and rotating the array to the right. The rules don't state what other operations are allowed, but I'll assume that compare is also restricted to the first pair of elements. I also assume that the size of the array is known, let n equal the number of elements in the array.

One iterative (non-recursive) strategy would be to find the currently smallest element in the array by using compare, swap if out of order, and rotate, so that the currently smallest element is swapped to array[0] if needed, after which the rotate moves it to array[1].

To find the smallest of n elements, it will take n-1 iterations of the primary loop, compare, swap if out of order, rotate right. After n-1 iterations, the smallest element ends up at array[1]. Do one more rotate so that the smallest element is now at array[2], and there are new values to check at array[0] and array[1].

Then n-2 iterations are done to find the second smallest element. This will end up with the smallest element at array[0], and second smallest element at array[1]. So now a run of 2 elements is sorted. Rotate the array 2 times to move the sorted run to array[2] and array[3], to set up the next loop with new values at array[0] and array[1].

The sequence continues, n-3 iterations to find third smallest element, rotate array 3 times. For each i = 1 to n-1, it's n-i iterations of compare, swap if out of order, rotate 1 time, then after the iterations, rotate array i times.

After this, the second largest element is at array[1], and the largest is at array[2]. Rotate n-2 times to get the sorted array.

Example, each iteration is compared, swapped if needed, rotated once

b a d e c   do 4 iterations
c a b d e
e a c b d
d a e c b

b d a e c   do 1 rotate

c b d a e   do 3 iterations
e b c d a
a b e c d

c d a b e   do 2 rotates

e c d a b   do 2 iterations
b c e d a

e d a b c   do 3 rotates

c d e a b   do 1 iteration

a b c d e   do final 2 rotates

stark · Accepted Answer · 2016-01-30 23:33:27Z

0

Rule 1 treats the array as a circular buffer, allowing you to shift it to any position while keeping the same order (modulo the length of the buffer). Rule 2 changes the order, but only at the current position.

One fairly inefficient method would be to implement bubble sort by shifting the smallest value not in the correct position to the end of the group that has been sorted. This can be done by shifting with rule 1 until it is in the second position then alternating rules 2 & 1. Once they are all in order shift with rule 1 until the smallest number is first.

answered Jan 30, 2016 at 23:33

stark

13.3k3 gold badges39 silver badges56 bronze badges

Collectives™ on Stack Overflow

Recursive sort, using two functions

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related