search

codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
199 stars 270 forks source link

implemented introsort #546

Closed Kishan-Ved closed 6 months ago

Kishan-Ved commented 6 months ago

Brief description of what is fixed or changed

This PR is for issue: https://github.com/codezonediitj/pydatastructs/issues/545

I have implemented introsort as described in Wikipedia: https://en.wikipedia.org/wiki/Introsort (as mentioned in the issue).

Please note:

  1. I strongly believe array is modified in the function heapsort and insertion_sort that I have called.
  2. comp is not an argument as heapsort does not have comp as an argument.
  3. Please let me know how I can test this, as I tried running the example in the comments but I'm getting the following error: 
    line 1, in <module>
from pydatastructs import OneDimensionalArray as ODA, intro_sort
ModuleNotFoundError: No module named 'pydatastructs'

    Please let me know if any other changes are needed.

Kishan-Ved commented 6 months ago

Also, may I please know why 7 checks are failing?

Kishan-Ved commented 6 months ago

I've figured this out and I'm working on it now, thanks!

Kishan-Ved commented 6 months ago

May I please know which files I'm supposed to change? I've read the testing instructions and tried to test the existing code. However, when I test with my code, there are errors: I added relevant (similar to other sorting functions) tests to test_algorithms file in tests folder and test_algorithms file in the benchmarks folder. But the errors exist. The error is that intro_sort (my function) cannot be imported. I'm unable to trace this error, please help.

For now, I've added the intro_sort function to algorithms.py (not in the all list), with proper formatting (whitespaces, newline characters etc.)

Adding introsort to all list in algorithms.py increases number of errors significantly (all being import errors for intro_sort)