SORTING ALGORITHMS

public class BubbleSort {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int size=sc.nextInt();
int[]arr=new int[size];
for(int i=0;i<size;i++) {
arr[i]=sc.nextInt();
}

for(int i=0;i<size;i++) {
boolean swapped=false;
for(int j=0;j<size-1;j++) {
if(arr[j]>arr[j+1]) {
arr[j]=(arr[j]+arr[j+1])-(arr[j+1]=arr[j]);
swapped=true;
}
}
if(!swapped)
break;
}
System.out.println(Arrays.toString(arr));
}
}

public class InsertionSort {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}

for(int i=1;i<size;i++) {
int key=arr[i];
int j=i-1;

while(j>=0&&key<arr[j]) {
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
System.out.println(Arrays.toString(arr));
}
}

public class SelectionSort {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
 int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}

for(int i=0;i<size-1;i++) {
int minIdx=i;
int j;
for(j=i+1;j<size;j++) {
if(arr[j]<arr[minIdx])
minIdx=j;
}

arr[minIdx]=(arr[i]+arr[minIdx])-(arr[i]=arr[minIdx]);
}
System.out.println(Arrays.toString(arr));
}
}

public class MergeSort {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}

int[]res=merge(arr);
System.out.println(Arrays.toString(res));
}

private static int[] merge(int[] arr) {

if(arr.length==1)
return arr;
int mid=arr.length/2;
int[]left=merge(Arrays.copyOfRange(arr, 0,mid));
int []right=merge(Arrays.copyOfRange(arr, mid,arr.length));
return joinArray(left,right);
}

private static int[] joinArray(int[] left, int[] right) {

int[]res=new int[left.length+right.length];
int i=0,j=0,k=0;

while(i<left.length&&j<right.length) {
if(left[i]<right[j])
res[k++]=left[i++];
else
res[k++]=right[j++];
}

while(i<left.length)
res[k++]=left[i++];
while(j<right.length)
res[k++]=right[j++];
return res;
}
}
public class QuickSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}

quickSort(arr,0,size-1);
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int low, int high) {

if(low>=high)
return;
int start=low;
int end=high;
int mid=(low+high)/2;

int pivot=arr[mid];
while(start<=end) {
while(arr[start]<pivot)
start++;
while(arr[end]>pivot)
end--;
if(start<=end) {
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}

quickSort(arr,low,end);
quickSort(arr,start,high);
}
}
 BACKTRACKING
public class NQueens {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] board = new int[n][n];

if (solveNQUtil(board, 0, n) == false)
System.out.println("Solution Does not Exist");
else {
for (int i = 0; i < n; i++) {
System.out.println(Arrays.toString(board[i]));
}
}
}

private static boolean solveNQUtil(int[][] board, int col, int n) {

if (col >= n)
return true;

for (int i = 0; i < n; i++) {

if (isSafe(board, i, col, n)) {
board[i][col] = 1;

if (solveNQUtil(board, col + 1, n))

return true;

board[i][col] = 0;
}
}

return false;
}

private static boolean isSafe(int[][] board, int row, int col, int n) {

for (int i = 0; i < col; i++) {

if (board[row][i] == 1)
return false;
}

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 1)
return false;
}

for (int i = row, j = col; i < n && j >= 0; i++, j--) {

if (board[i][j] == 1)
return false;
}

return true;
}
}
class Solution {
List<List<String>> res=new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
if(n==1){
List<String>list=new ArrayList<>();
list.add("Q");
res.add(list);
return res;
}

char[][] board=new char[n][n];

for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
board[i][j]='.';
}
solve(board,0,n);
return res;
}

private void solve(char[][]board,int col,int n){

if(col>=n){
List<String>list=new ArrayList<>();
for(char[] ch:board){
list.add(new String(ch));
}
res.add(list);
return;
}
for(int i=0;i<n;i++){
if(isSafe(board,i,col)){
board[i][col]='Q';
solve(board,col+1,n);
board[i][col]='.';
}
}

private boolean isSafe(char[][]board,int row,int col){

for(int i=0;i<col;i++){
if(board[row][i]=='Q')
return false;
}

for(int i=row,j=col;i>=0&&j>=0;i--,j--){
if(board[i][j]=='Q')
return false;
}

for(int i=row,j=col;i<board.length&&j>=0;i++,j--){
if(board[i][j]=='Q')
return false;
}
return true;
}
}