README.md

# Insertion sort

## Overview
 
- Application has 3 implementation of Insertion sort
  - Plain version - this version implements single thread solution
  - Parallel version - my implementation of parallel Insertion sort
  - ChatGPT OMP parallel - this version was designed by me and written by chatGPT

## How to build and run the application

1. Download the repository from gitlab.
2. Open clion and build the project.
3. Run the project either from terminal or from readme with prepared examples.


## Run the application with parameters

- Application has multiple parameters.
- You can choose with what parameters the application should be run.
- After every run results are validated and time is printed to stdout.
- NOTE: When loading data from file, avoid using negative values, as this program is designed for positive huge numbers only

### All parameters
- accessible through --help or -h
```bash
cd cmake-build-debug && ./sem_flekal_app -h
```
```
usage: sem_flekal_app [options]

options, with default in [ ]:
-h --help                   prints this help message
-i=<number>                 specifies how long random array should be sorted
-p                          prints random generated array on entry and sorted one at the end
-f=<file_path>              specifies path to the file from which to load data
-c=<number>                 specifies number of cores the program should run
                            if optional parameter in other option is used, last value is used
--plain                     runs non parallel version of program
--parallel[=num_of_core]    runs parallel version of program with optional num of cores
                            if nothing given, maximum number of cores is used
                            if '-c' parameter is used, last value is used
--chatGPT_omp_parallel      runs parallel version of program using omp parallel generated by chatGPT
--generate_full_report      generates full report for maximum system threads
```

### Examples of run configurations

- Plain insertion sort for array with 50000 elements
```bash
cd cmake-build-debug && ./sem_flekal_app --plain -i=50000
```

- Parallel insertion sort for array with 50000 elements with 8 threads
```bash
cd cmake-build-debug && ./sem_flekal_app --parallel -i=50000 -c=8
```

- Parallel insertion sort for array with 50000 elements with 8 threads, where data were inputted through file
```bash
cd cmake-build-debug && ./sem_flekal_app --parallel -f=../example/input1 -c=8
```

- ChatGPT OMP parallel insertion sort for array with 50000 elements
```bash
cd cmake-build-debug && ./sem_flekal_app --chatGPT_omp_parallel -i=50000
```

- Generate full report to stdout
```bash
cd cmake-build-debug && ./sem_flekal_app --generate_full_report
```
## Report 

### Assigment
- Create two versions of Insertion sort and compare them. One should be parallel, second should be optimized for one thread. 
- You can also compare OMP parallel with your implementation

### Results
- The measurements were conducted on commit 4b5a0891 using an 11th Gen Intel® Core™ i7-1165G7 processor @ 2.80GHz with 8 CPU cores on Ubuntu 24.04.1 LTS. 
- For each measurement, a new randomly shuffled vector of numbers was generated within a defined range. 
- For instance, the measurement for a vector of size 5000 used numbers in the range <0, 4999>, with each number appearing only once.

- The results are presented in the table and graph below. 
- All measurements are recorded in milliseconds.

- To replicate the measurements, use the following command:
```bash
cd cmake-build-debug && ./sem_flekal_app --generate_full_report
```

## Performance Results for Random Array of Various Lengths

| Array Length  | Plain   | Parallel | ChatGPT OMP Parallel |
|---------------|---------|----------|----------------------|
| 100           | 0 ms    | 0 ms     | 0 ms                 |
| 500           | 0 ms    | 0 ms     | 0 ms                 |
| 1000          | 0 ms    | 0 ms     | 0 ms                 |
| 5000          | 2 ms    | 0 ms     | 1 ms                 |
| 10000         | 10 ms   | 1 ms     | 2 ms                 |
| 15000         | 22 ms   | 1 ms     | 4 ms                 |
| 20000         | 38 ms   | 2 ms     | 4 ms                 |
| 100000        | 855 ms  | 43 ms    | 24 ms                |
| 200000        | 3549 ms | 168 ms   | 56 ms                |
| 300000        | 9260 ms | 330 ms   | 74 ms                |
| 400000        | 14254 ms| 575 ms   | 95 ms                |
| 500000        | 22499 ms| 898 ms   | 116 ms               |
| 600000        | 32835 ms| 1327 ms  | 160 ms               |
| 700000        | 44944 ms| 1676 ms  | 165 ms               |
| 800000        | 58115 ms| 2183 ms  | 184 ms               |
| 900000        | 74858 ms| 2874 ms  | 229 ms               |
| 1000000       | 102077 ms| 4935 ms | 326 ms               |
| 2000000       | 449586 ms| 20133 ms | 745 ms               |
| 3000000       | 1576574 ms | 58261 ms | 1106 ms |

![img_1.png](img_1.png)

- From the results we can see that OMP parallel version is the fastest by far.
- My parallel version is faster than OMP with the shorter vectors, but around 100000 elements the omp became faster.