jeandersonbc / algorithms-and-ds Goto Github PK

The program seems to be correct but not fast enough. Probably, some kind of Lazy-Propagation technique will solve this issue.

Instead of having only C++ code, it is good to practice, with an editor, some Java programming.

There are several versions of the QuickSort algorithm. It would be interesting to compare their performance.

6.2-5
The code for MAX-HEAPIFYis quite efficient in terms of constant factors, except
possibly for the recursive call in line 10, which might cause some compilers to
produce inefficient code. Write an efficient MAX-HEAPIFYthat uses an iterative
control construct (a loop) instead of recursion.

Instead of using the existing one, I could use (i + 1) << 1. By using this way, I could use 0 as the root of the tree.

Implement a segment tree

This repository should be organized by problems:

ROOT
|
`--- algorithms
|     |
|     `--- The Sorting Problem
|     |     |
|     |     `--- README.md (problem description)
|     |     |
|     |     `--- java-src
|     |     |
|     |     `--- cpp-src
|     |     |
|     |     `--- (other-languages)-src
|     |
|     `--- (other categories...)
| 
`--- .gitignore
|
`--- LICENSE.md
|
`--- README.md

It's clearly visible that the SlowCounter.java solution is faster than the FasterCounter.java, although FasterCounter is asymptotically faster than SlowCounter for N = 10^4.

This is also a problem of figuring out a value of N where the Insertion Sort is faster than Merge Sort.

What would be a proper way to test different inputs and find the value of N?
By finding it, it's possible to improve the Merge Sort to use Insertion Sort for input <= N.

• Cormem
• Competitive Programming 3