README.md 2.41 KB
Newer Older
Hrishee Shastri's avatar
Hrishee Shastri committed
1
2
3
4
5
6
# Sorting by Reversals

Sorting by Reversals is a small python program that records the time to sort random permutations using algorithms from the Quantum routing with fast reversals paper: GDC(TBS), GDC(ATBS), OES (odd-even sort).


## Installation
Hrishee Shastri's avatar
Hrishee Shastri committed
7
Simply download the repository. No dependencies required, assuming Python3 is installed. 
Hrishee Shastri's avatar
Hrishee Shastri committed
8
9

## Usage
Hrishee Shastri's avatar
Hrishee Shastri committed
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

### Unit tests 
To run the unit tests, enter ```python -m unittest``` into the command line at the top level directory.

### Reversal routing 
Entering ```echo P | python main.py``` into the command line will print out the reversals in order to sort the permutation P using 
GDC(ATBS). 

For example, `echo 0 1 3 2 | python main.py` will output to the console `[(2,3)]` because a reversal starting at index 2 and ending at index 3 will 
sort the permutation. 

Alternatively, you can type `python main.py` and from there simply input permutations in the command line and recieve the sorting sequence of reversals as output. 

### Data collection
To run the program for data collection, call ```main(NUM_PERMS_PER_LENGTH, LENGTH_FROM, LENGTH_TO)``` in the ```main.py``` file, where 
Hrishee Shastri's avatar
Hrishee Shastri committed
25

Hrishee Shastri's avatar
Hrishee Shastri committed
26
```NUM_PERMS_PER_LENGTH:``` number of random permutations to run the algorithms on per permutation length
Hrishee Shastri's avatar
Hrishee Shastri committed
27

Hrishee Shastri's avatar
Hrishee Shastri committed
28
```LENGTH_FROM:``` starting permutation length
Hrishee Shastri's avatar
Hrishee Shastri committed
29

Hrishee Shastri's avatar
Hrishee Shastri committed
30
31
```LENGTH_TO:``` ending permutation length 

Hrishee Shastri's avatar
Hrishee Shastri committed
32

Hrishee Shastri's avatar
Hrishee Shastri committed
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
In other words, for each ```N``` from ```LENGTH_FROM``` to ```LENGTH_TO```, the program generates a csv file ```data/len_N_random_perms.csv``` containing ```NUM_PERMS_PER_LENGTH``` permutations.

The resulting csv files will be generated in the ```data/```directory. Each csv file will contain a list of the permutations generated and the corresponding routing times for the three algorithms, GDC(TBS), GDC(ATBS), and OES.

For example, the following may be the output for ```data/len_10_random_perms.csv``` when ```NUM_PERMS_PER_LENGTH``` = 9.
```
Permutation,OES,GDC(TBS),GDC(ATBS)
"2, 3, 9, 6, 8, 5, 1, 10, 4, 7",7,6.666666666666667,7.0
"10, 5, 7, 2, 3, 9, 6, 1, 4, 8",10,8.666666666666666,7.666666666666667
"10, 8, 3, 1, 7, 9, 4, 5, 2, 6",10,8.0,7.666666666666667
"5, 6, 8, 3, 1, 9, 2, 10, 7, 4",7,7.666666666666667,8.0
"3, 10, 7, 9, 8, 2, 1, 6, 4, 5",9,9.0,7.666666666666667
"8, 10, 7, 6, 1, 5, 2, 4, 3, 9",9,8.0,6.666666666666667
"5, 8, 9, 2, 3, 6, 10, 1, 4, 7",7,7.666666666666667,6.333333333333333
"7, 10, 2, 5, 8, 1, 3, 9, 6, 4",8,6.666666666666667,8.666666666666666
"2, 1, 6, 3, 9, 8, 10, 4, 5, 7",5,7.333333333333333,5.0
```