Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Binary sort#26

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
bhadrik wants to merge2 commits intoalgorithm-visualizer:master
base:master
Choose a base branch
Loading
frombhadrik:Binary-Sort
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
30 changes: 30 additions & 0 deletionsDivide and Conquer/Binary Sort/README.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
# BinarySort
Binary sort is an algorithm that sorts the given array of numbers based on its binary value.

# How to use
1. First compile both C file using following command: "gcc -o BinarySort BinarySort.c" & "gcc -o Generator Generator.c"
2. Then run "Generator.exe" file using following command: "Generator.exe 10000 Data.txt" - Here 10000 is size of array which is going to be generated.
3. It will generate Data.txt file, filled with 10000 random numbers.
4. Then run "BinarySort.exe" file using following command: "BinarySort.exe 10000 Data.txt" for windows & "./BinarySort 10000 Data.txt" for linux
5. It will use Data.txt file as an input to the algorithm and sort thos data and will generate "Sorted Data.txt" file which is sorted output.

# Working of an algorithm
* This algorithm is based on binary value of the numbers.

```
8 - 1000
5 - 0011
6 - 0110

4th bit 4th bit(R) 4th bit(R) 3rd bit(L) 3rd bit(L)
+-----------+ +-------+ +---+ +-------+ +---+ +-------+ +---+ +---+ +---+ +---+ Everything is fixed
| 8 | 5 | 6 | -> | 6 | 5 | | 8 | -> | 6 | 5 | | 8 | -> | 6 | 5 | | 8 | -> | 5 | | 6 | | 8 | -> so arry is solved
+-----------+ +-------+ +---+ +-------+ +---+ +-------+ +---+ +---+ +---+ +---+ easily without
L U L U U=L L U Fix L U Fix Fix Fix Fix comparing single no.

Input array Found 4th bit of Recursion call Recusion call for Found 3rd bit of
8 is *1* so swap right array is left array for 6 is *1* so swap
with number at U sorted. *bitNo* 3. with number at U
and devide the and decide the
array. array.
```
105 changes: 105 additions & 0 deletionsDivide and Conquer/Binary Sort/code.java
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
import org.algorithm_visualizer.*;
import java.util.Arrays;

public class Main {
private static ChartTracer chartTracer = new ChartTracer("Chart");
private static LogTracer logTracer = new LogTracer("Console");
private static Integer [] data = (Integer[]) new Randomize.Array1D(15, new Randomize.Integer(1, 20)).create();

public static void main(String[] args) {
int length = data.length, bitNo = 6,lowerBound = 0;
int upperBound = length - 1;

logTracer.printf("original data = %s\n",Arrays.toString(data));
chartTracer.set(data);
Layout.setRoot(new VerticalLayout(new Commander[]{chartTracer, logTracer}));
Tracer.delay();

// binaryOfAllNumbers();

binarySort(data, bitNo-1, lowerBound, upperBound);

logTracer.printf("sorted data = %s\n",Arrays.toString(data));
}

private static void binarySort(Integer [] data, int bitNo, int lowerBound, int upperBound) {
logTracer.reset();
logTracer.printf("scanning bitNo:%s for (%s, %s)\n", bitNo, lowerBound, upperBound);
chartTracer.set(data);
chartTracer.select(lowerBound, upperBound);
Tracer.delay();

int l_backup = lowerBound, u_backup = upperBound, i;
boolean letsGo = false;

do{
//Scaning all the numbers between location "lowerBound" to "upperBound"
for (i = l_backup; i <= upperBound; i++) {
int temp = (data[i] >> bitNo) & 1;
boolean condition;
if(temp >= 1){
condition = true;
}
else{
condition = false;
}
if (condition) {
letsGo = true;
if (i != upperBound) {
logTracer.printf("swap %s and %s\n",data[i],data[upperBound]);

swap(data, i, upperBound);

chartTracer.set(data);
chartTracer.select(lowerBound, upperBound);
Tracer.delay();
i--;
}
chartTracer.deselect(upperBound);
upperBound--;
}
}

bitNo--;
}while(!letsGo && bitNo > 0);

bitNo++;

int hold = upperBound;

if (upperBound == u_backup){
hold = lowerBound;
}
else{
hold = upperBound + 1;
}

//Again calling for divided subarry, and now for (bitNo - 1)th bit
if(bitNo > 0 && (hold != u_backup || lowerBound != upperBound)){
binarySort(data, (bitNo - 1), hold, u_backup);
binarySort(data, (bitNo - 1), lowerBound, upperBound);
}
}

private static void swap(Integer [] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;

chartTracer.patch(x, data[x]);
chartTracer.patch(y, data[y]);
Tracer.delay();
chartTracer.depatch(x);
chartTracer.depatch(y);
}

private static void binaryOfAllNumbers(){
for(int i=0; i<data.length; i++){
logTracer.printf("%s [",data[i]);
for(int bit=5; bit>=0; bit--){
logTracer.printf(" %s",(data[i] >> bit) & 1);
}
logTracer.printf("]\n");
}
}
}
[8]ページ先頭
©2009-2025 Movatter.jp