Sorting-1 Assignment

Q1 - Given an array of strings arr[]. Sort given strings using Bubble Sort and display the sorted array.

     
import java.util.Scanner;
public class Test{
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        System.out.println("Enter the length of array");
        int n = scn.nextInt();
        String[] arr = new String[n];
        System.out.println("Enter the elements of array");
        for(int i = 0; i < n; i++){
            arr[i] = scn.next();
        }
        for (int j = 0; j < n - 1; j++){
            for (int i = j + 1; i < n; i++){
                if (arr[j].compareTo(arr[i]) > 0){
                   String temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        for(int i = 0; i < n; i++){
            System.out.print(arr[i] + " ");
        }
    }
}

Q2- Given a string s, return the string which contains all characters of s in lexicographical order.
import java.util.Scanner;
public class Test{
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the string: ");
                String s = scn.nextLine();
                char[] arr = s.toCharArray();
                //insertion sort
                for (int i = 1; i < arr.length; i++) {
                        int j = i;
                        // Insert a[i] into sorted left part 0..i-1
                        while (j > 0 && arr[j] < arr[j - 1]) {
                                // Swap a[j] and a[j-1]
                                char temp = arr[j];
                                arr[j] = arr[j-1];
                                arr[j-1] = temp;
                                // Decrement j by 1
                                j--;
                        }
                }
                        String ans = "";
                for(int i = 0; i < arr.length; i++){
                        ans += arr[i];
                }
                System.out.println(ans);
        }
}

Q3 - Given an integer array and an integer k where k<size of array, We need to return the kth smallest element of the array.
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        System.out.println("Enter the length of array");
        int n = scn.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter the elements of array");
        for (int i = 0; i < n; i++) {
            arr[i] = scn.nextInt();
        }
        System.out.println("Enter the index");
        int k = scn.nextInt();
        for (int i = 1; i < n; i++) {
            int j = i;
            // Insert a[i] into sorted left part 0..i-1
            while (j > 0 && arr[j] < arr[j - 1]) {
                // Swap a[j] and a[j-1]
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                // Decrement j by 1
                j--;
            }
 
        }
        System.out.print(arr[k - 1]);
    }
}

Q4 - Given an array of n elements, the task is to find the elements that are greater than half of elements in an array.
In case of odd elements, we need to print elements larger than floor(n/2) elements where n is total number of elements in array.
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        System.out.println("Enter the length of array");
        int n = scn.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter the elements of array");
        for (int i = 0; i < n; i++) {
            arr[i] = scn.nextInt();
        }
        for (int i = 1; i < n; i++) {
            int j = i;
            // Insert a[i] into sorted left part 0..i-1
            while (j > 0 && arr[j] < arr[j - 1]) {
                // Swap a[j] and a[j-1]
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                // Decrement j by 1
                j--;
            }
        }
        int si;
        if(n % 2 == 0){
            si = n/2;
        }else{
            si = n/2 + 1;
        }
        for (int i = si; i < n; i++)
            System.out.print(arr[i] + " ");
    }
}
Q5 - Given an array of digits (values are from 0 to 9), the task is to find the minimum possible sum of two numbers formed from digits of the array. 
Please note that all digits of the given array must be used to form the two numbers.

import java.util.Scanner;
public class Test{
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the length of the array: ");
                int n = scn.nextInt();
                int[] arr = new int[n];
                System.out.println("Enter the elements of the array: ");
                for(int i = 0; i < n; i++){
                        arr[i] = scn.nextInt();
                }
                //insertion sort
                for (int i = 1; i < arr.length; i++) {
                        int j = i;
                        // Insert a[i] into sorted left part 0..i-1
                        while (j > 0 && arr[j] < arr[j - 1]) {
                                // Swap a[j] and a[j-1]
                                int temp = arr[j];
                                arr[j] = arr[j-1];
                                arr[j-1] = temp;
                                // Decrement j by 1
                                j--;
                        }
                }
                int a = 0;
                int b = 0;
                for(int i = 0; i < arr.length; i++){
                        if(i % 2 == 0){
                                a = a * 10 + arr[i];
                        }else{
                                b = b * 10 + arr[i];
                        }
                }
                System.out.println(a + b);
        }
}
Q6 - Given an array with N distinct elements, convert the given array to a form where all elements are in the range from 0 to N-1. The order of elements is the same, i.e., 0 is placed in the place of the smallest
element, 1 is placed for the second smallest element, ... N-1 is placed for the largest element.
import java.util.Scanner;
public class Test {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        System.out.println("Enter the length of the array");
        int n = scn.nextInt();
        System.out.println("Enter the elements of the array");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = scn.nextInt();
        }
        int[] temp = arr.clone();
        for (int i = 1; i < n; i++) {
            int j = i;
            while (j > 0 && temp[j] < temp[j - 1]){
                int val = temp[j];
                temp[j] = temp[j-1];
                temp[j-1] = val;
                j--;
            }
        }
        int pos = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[j] == temp[i]){
                    arr[j] = pos;
                    pos++;
                    break;
                }
            }
        }
        for(int i = 0; i < n; i++){
            System.out.print(arr[i] + " ");
        }
    }
}