Question

Java Programm please!

Design and implement an algorithm using recursion and backtracking to sort an array of integers into ascending order. Consider the given array as input and produce a sorted array as output. Each time you take an integer from the input array, place it at the end of the output array. If the result is unsorted, backtrack.

Answer 1

Java program to sort an array using recursion and backtracking

Code:

import java.util.Scanner;
public class Main
{
    //sortArray recursive method to sort array using recursion and bactracking
    public static void sortArray(int array[], int n)
    {
        //quitting the function if array is sorted from end to start
        if(n==1){
            return;
        }
        //iterating through array
        for(int i=0;i<n-1;i++)
            //changing integer position if array if not sorted
            if(array[i]>array[i+1]){
                int temp=array[i];
                array[i]=array[i+1];
                array[i+1]=temp;
            }
        //calling sortArray recursively 
        sortArray(array, n-1);
    }
    
    //main method
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int size;
            //reading array size
            System.out.print("Enter array size: ");
            size=sc.nextInt();sc.nextLine();
            //declaring array of size entered
            int array[]=new int[size];
            //reading array elements
            for(int i=0;i<size;i++){
                System.out.print("Enter array element "+(i+1)+": ");
                array[i]=sc.nextInt();sc.nextLine();
            }
            //printing array elements before sorting
            System.out.println("Array elements before sorting: ");
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            //calling sortArray method
            sortArray(array, size);
            //printing array elements after sorting
            System.out.println("\nArray elements after sorting: ");
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
        }
}

Code Screenshot:

Output: