GEEKS FOR GEEKS

SORTING ALGORITHMS
public class BubbleSort {
public static void main(String[] args) {
Scanner sc=new Scanner([Link]);
int size=[Link]();
int[]arr=new int[size];
for(int i=0;i<size;i++) {
arr[i]=[Link]();
}

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;
}
[Link]([Link](arr));
}
}

public class InsertionSort {

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

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;
}
[Link]([Link](arr));
}
}
public class SelectionSort {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int size = [Link]();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = [Link]();
}

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]);
}
[Link]([Link](arr));
}
}

public class MergeSort {

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

int[]res=merge(arr);
[Link]([Link](res));
}

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

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

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

int[]res=new int[[Link]+[Link]];
int i=0,j=0,k=0;

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

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

quickSort(arr,0,size-1);
[Link]([Link](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([Link]);
int n = [Link]();
int[][] board = new int[n][n];

if (solveNQUtil(board, 0, n) == false)
[Link]("Solution Does not Exist");
else {
for (int i = 0; i < n; i++) {
[Link]([Link](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<>();
[Link]("Q");
[Link](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){
[Link](new String(ch));
}
[Link](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<[Link]&&j>=0;i++,j--){
if(board[i][j]=='Q')
return false;
}
return true;
 }
}