### akattack's blog

By akattack, history, 6 weeks ago, ,

May the lights of Diwali diyas fill your home with wealth, happiness, and everything that brings you joy! Wish you and your entire family a very happy Diwali! May prosperity and happiness fill your life with the shine of diyas and the echoes of chants.

• +51

By akattack, history, 6 weeks ago, ,

There are many sorting algorithms like merge sort, quick sort, etc to sort a linear data structure.

Of all the sort algorithms Counting sort is better, because time complexity is approx O(n).

But counting sort is only viable when

• values of element lie in the small range.
• the values are non-negative.

Counting sort make use of an extra array also known as counting array.

Consider the following array [5, 9, 11, 10, 15, 12, 2, 8 ,10] — Min = 2 and Max = 15.

Counting array will store the frequency of each element of the original array at the relative index position. For example in our case, the frequency of 2 will be stored at index 0, frequency of 3 at 1, frequency of 4 at 2 and so on.

Finally, after storing the frequency of each element in the counting array, we will rewrite the original array on the basis of the counting array. For example in our case index position 0 has 1 – it means only a single 2 was present in the original array, index position 1 has 0 – it means no 3 was present in the original array.

## Implementation of Counting Sort in C++

#include <stdio.h>
#include <stdlib.h>

int main()
{
int arr[] = {5, 9, 11, 10, 15, 12, 2, 8 ,10};
countingSort(arr,0,8,2,15);

return 0;
}

void countingSort(int arr[], int s, int e, int mn, int mx){
int i,k=0,sizeTemp = mx-mn+1;
int temp[sizeTemp];

// Initializing all element of counting array with 0
for(i=0; i<sizeTemp; i++){
temp[i] = 0;
}

//Store the frequency of each element of the original array
//at the relative position in counting array
for(i=0; i<=e; i++){
temp[arr[i]-mn]++;
}

//Iterate through the counting array and re-write the original array.
for (i=mn; i<=mx; i++){
while(temp[i-mn]-->0){
arr[k++]=i;

}
}

for(i=0; i<=8; i++){
printf("%d ",arr[i]);
}

}


Output

2 5 8 9 10 10 11 12 15


Counting sort should only be used when the input lies in the specific range and space is not an issue.

Reference: My Blog

• -14

By akattack, history, 2 months ago, ,

## What is N Queen Problem?

We are given N chess’s queens and is asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

• Same Row
• Same Column
• Same Diagonal (left or right)

Solution using Backtracking

import java.util.Scanner;

public class Board {

int chessBoard[][];
int queens;

public Board(int queens) {
chessBoard = new int[20][20];
this.queens = queens;
}

void displayBoard(){
int i, j;
for(i=0; i<queens; i++){
for(j=0; j<queens; j++){
if(chessBoard[i][j] == 1)
System.out.print(" * ");
else
System.out.print(" - ");
}
System.out.print("\n");
}
System.out.print("\n");
System.out.print("\n");
}

void reset(){
for(int i=0; i<queens; i++){
for(int j=0; j<queens; j++){
chessBoard[i][j] = 0;
}
}
}

boolean isValidPlace(int row, int col){
int i,j;

//Checking horizontally
for(i=col; i>=0; i--){
if(chessBoard[row][i] == 1)
return false;
}

//checking left diagonal
for(i=row, j=col; i>=0 && j>=0; i--,j--){
if(chessBoard[i][j] == 1)
return false;
}

//checking right diagonal
for(i=row, j=col; i<queens && j>=0; i++,j--){
if(chessBoard[i][j] == 1)
return false;
}

return true;
}
}

public class NQueen {

int queens;
boolean flag;
Board board;

public NQueen(int queens) {
this.flag = false;
this.board = new Board(queens);;
this.queens = queens;
}

void solveNqueen(){

int i;
//starting from (0,0) of the board
hasSolution(0,0);

//After running hasSolution() still flag == false
//It means no Solution
if(!flag)
System.out.println("No Solution");

}

boolean hasSolution(int ctr, int colQueen){

//Reached beyond last column
//Means solution (configuration) found

if(colQueen == queens){
flag = true;
board.displayBoard();
//intentionally returning false to find more possible solution
return false;
}

int i,j;
for(i=ctr; i<queens; i++){

//checking if position is safe
if(board.isValidPlace(i,colQueen)){
//setting current value to 1 means placing a queen
board.chessBoard[i][colQueen] = 1;
//moving to next column's 1st row
if(hasSolution(0,colQueen+1))
return true;

//backtrack
//reset to 0 means removing queen
board.chessBoard[i][colQueen] = 0;
}

}

//When no row is safe in current column
return false;
}
}

public class App {

static Scanner in = new Scanner(System.in);

public static void main(String args[]){
System.out.println("Enter number of Queens");
int queens = in.nextInt();

NQueen nQueen = new NQueen(queens);
nQueen.solveNqueen();

}
}


Reference: My Programming Blog