Java backtracking problem

Question

i want to build a sorting method to sort array "4,2,7,5,1" into "1,2,4,5,7" my current code is

public static Node<Integer> sort_it(int[] arr, int fst, int last, Node<Integer> part_soln) 

{
    if (fst>last)
        return part_soln; // return a sorted list
    else { 
        for (int row=0; row<=last; row++)
        {
            if (!exists(arr[row],part_soln) && ((arr[row]<=part_soln.getItem())||part_soln==null))
            {
                Node<Integer> new_soln = new Node<Integer>(row,part_soln);
                Node<Integer> ret=sort_it(arr,fst++,last,new_soln);
                if(ret!=null)
                    return ret;
            }
        }
        return null; 
    }
}

what is wrong

Answer 1

First thing I see is that when you called the recursive method, you used fst++ instead of ++fst.

Answer 2

If this isn't homework, then you should be using Arrays.sort(int[]) to sort ints in Java.

Answer 3

You can use the pre-existing sorting methods, and rely on the natural ordering of Integer (or any other type). All you need to do is write a forwarding compareTo method (implementing Comparable) for Node that checks if the generic argument implements 'Comparable' and then forwards the method call to compareTo of the stored object.

You store the value as a field, and then just use the normal 'instanceof' check to check that Comparable is implemented, cast to Comparable and then just call that method. Easy. Now, you can use Arrays.sort(nodearray) where nodearray is an array of Node<?>. Is that what you were after? :)

The sort algorithm is a tuned quicksort.

As another poster mentioned, if you have an array of int or Integer, you can use an Arrays.sort(..) method directly, but we need to forward the call due to the encapsulation in the Node class.

Implementation of quicksort from Arrays.java (you can modify this):

    1   /*
    2    *  Licensed to the Apache Software Foundation (ASF) under one or more
    3    *  contributor license agreements.  See the NOTICE file distributed with
    4    *  this work for additional information regarding copyright ownership.
    5    *  The ASF licenses this file to You under the Apache License, Version 2.0
    6    *  (the "License"); you may not use this file except in compliance with
    7    *  the License.  You may obtain a copy of the License at
    8    *
    9    *     http://www.apache.org/licenses/LICENSE-2.0
   10    *
   11    *  Unless required by applicable law or agreed to in writing, software
   12    *  distributed under the License is distributed on an "AS IS" BASIS,
   13    *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   14    *  See the License for the specific language governing permissions and
   15    *  limitations under the License.
   16    */

 2390       private static void sort(int start, int end, int[] array) {
 2391           int temp;
 2392           int length = end - start;
 2393           if (length < 7) {
 2394               for (int i = start + 1; i < end; i++) {
 2395                   for (int j = i; j > start && array[j - 1] > array[j]; j--) {
 2396                       temp = array[j];
 2397                       array[j] = array[j - 1];
 2398                       array[j - 1] = temp;
 2399                   }
 2400               }
 2401               return;
 2402           }
 2403           int middle = (start + end) / 2;
 2404           if (length > 7) {
 2405               int bottom = start;
 2406               int top = end - 1;
 2407               if (length > 40) {
 2408                   length /= 8;
 2409                   bottom = med3(array, bottom, bottom + length, bottom
 2410                           + (2 * length));
 2411                   middle = med3(array, middle - length, middle, middle + length);
 2412                   top = med3(array, top - (2 * length), top - length, top);
 2413               }
 2414               middle = med3(array, bottom, middle, top);
 2415           }
 2416           int partionValue = array[middle];
 2417           int a, b, c, d;
 2418           a = b = start;
 2419           c = d = end - 1;
 2420           while (true) {
 2421               while (b <= c && array[b] <= partionValue) {
 2422                   if (array[b] == partionValue) {
 2423                       temp = array[a];
 2424                       array[a++] = array[b];
 2425                       array[b] = temp;
 2426                   }
 2427                   b++;
 2428               }
 2429               while (c >= b && array[c] >= partionValue) {
 2430                   if (array[c] == partionValue) {
 2431                       temp = array[c];
 2432                       array[c] = array[d];
 2433                       array[d--] = temp;
 2434                   }
 2435                   c--;
 2436               }
 2437               if (b > c) {
 2438                   break;
 2439               }
 2440               temp = array[b];
 2441               array[b++] = array[c];
 2442               array[c--] = temp;
 2443           }
 2444           length = a - start < b - a ? a - start : b - a;
 2445           int l = start;
 2446           int h = b - length;
 2447           while (length-- > 0) {
 2448               temp = array[l];
 2449               array[l++] = array[h];
 2450               array[h++] = temp;
 2451           }
 2452           length = d - c < end - 1 - d ? d - c : end - 1 - d;
 2453           l = b;
 2454           h = end - length;
 2455           while (length-- > 0) {
 2456               temp = array[l];
 2457               array[l++] = array[h];
 2458               array[h++] = temp;
 2459           }
 2460           if ((length = b - a) > 0) {
 2461               sort(start, start + length, array);
 2462           }
 2463           if ((length = d - c) > 0) {
 2464               sort(end - length, end, array);
 2465           }
 2466       }