sort made with linked lists

[HellOfMice]

A small program to see how to sort a list of words using a linked-list.

[HellOfMice]

This is a new version that allocates a buffer before to sort, using VirtualAlloc.
When using this buffer I don't have to call malloc and to initialize the structure for each call.
Sorting 14130 words takes between 15/20 seconds.
If you have some ideas to be quicker I accept the suggestion.
The words to sort be in UTF-8.

[HellOfMice]

This version is improved and add a comparaison with qsort.
qsort takes 1 seconds and my function takes 14 seconds.

Here is the log file:

[26/12/2022 19:52:49] *** Log Started ***
[26/12/2022 19:52:50] Openning Log
[26/12/2022 19:52:50] Log Ready
[26/12/2022 19:52:50] Starting Sort
[26/12/2022 19:53:04] Ending Sort
[26/12/2022 19:53:04] Starting QSort
[26/12/2022 19:53:04] Ending QSort
[26/12/2022 19:53:04] Writing Result
[26/12/2022 19:53:05] Result Written
[26/12/2022 19:53:05] Closing Log file
[26/12/2022 19:53:05] *** Log Stoped ***

[HellOfMice]

This new version takes 2/3 seconds for sorting 14130 words.
I have modified the structure to avoid lstrcpy but directly store the input string pointer to the structure
I make comparison on the first letter and if it is equal I use lstrcmp.

[HellOfMice]

The previous versions rejected the string if it already was in the list.
This one doe not do that.

It sorts 18369 words in 4 seconds.

[27/12/2022 09:18:52] *** Log Started ***
[27/12/2022 09:18:52] Openning Log
[27/12/2022 09:18:52] Log Ready
[27/12/2022 09:18:52] Starting Sort
[27/12/2022 09:18:56] Ending Sort
[27/12/2022 09:18:56] Writing Result
[27/12/2022 09:18:56] Result Written
[27/12/2022 09:18:56] Closing Log file
[27/12/2022 09:18:56] *** Log Stoped ***

[HellOfMice]

This is the last version.
It is shorter and quicker.
4 seconds for 18369 words.

[27/12/2022 13:10:47] *** Log Started ***
[27/12/2022 13:10:47] Openning Log
[27/12/2022 13:10:47] Log Ready
[27/12/2022 13:10:47] Starting Sort
[27/12/2022 13:10:51] Ending Sort
[27/12/2022 13:10:51] Writing Result
[27/12/2022 13:10:51] Result Written
[27/12/2022 13:10:51] Closing Log file
[27/12/2022 13:10:51] *** Log Stoped ***

[John Z]

Hi Hello....

Thanks got it. Going to learn from it.
I've used linked lists too so maybe I
can improve mine. You made significant
improvements along the way.

Thanks for contribution

John Z

[HellOfMice]

Don't forget that for sorting linked-lists a the worst solutions.
BTree is the best solution that I am trying to do without copying anyone.
Today I have sorted 23 324 lines in 7 seconds.

[HellOfMice]

Sorting 351213 words tooke 1 hour and 57 minutes.

[28/12/2022 20:00:19] *** Log Started ***
[28/12/2022 20:00:19] Openning Log
[28/12/2022 20:00:19] Log Ready
[28/12/2022 20:00:19] Starting Sort
[28/12/2022 21:57:40] Ending Sort
[28/12/2022 21:57:40] Writing Result
[28/12/2022 21:57:45] Result Written
[28/12/2022 21:57:45] Closing Log file
[28/12/2022 21:57:45] *** Log Stoped ***

[HellOfMice]

With this version I reduced by 35 minutes the time to sort more than 350000 words.
It takes 1h24 rather than 1h57 with the previous version.
This version only contents 1000 words in the file datas.c
I tried to measure the qsort function but with all the words it crashes.
Maybe it crashes because of bad parameters.
The tests I made tooke 4 seconds for 350000 words, strange...
It is very fast but I think it takes more time...

[29/12/2022 17:16:38] *** Log Started ***
[29/12/2022 17:16:38] Openning Log
[29/12/2022 17:16:38] Log Ready
[29/12/2022 17:16:38] Starting Sort
[29/12/2022 17:16:38] Ending Sort
[29/12/2022 17:16:38] Sorted 1000 words
[29/12/2022 17:16:38] Writing Result in file "Sort Result.txt"
[29/12/2022 17:16:38] Result Written
[29/12/2022 17:16:39] Closing Log file
[29/12/2022 17:16:39] *** Log Stoped ***

[cosh]

Great job, HellOfMice
This program significantly inspired me.
May I ask you what algorithm did you use to sort linked list?
Did you use merge sort or other sort of kind algorithms?
I wrote a linked list sorting program before that I actually use quick sort to sort separate linked list nodes and finally combine them together.
Here is the code:https://github.com/coshcage/StoneValley/blob/master/Samples/exp_2018-09-26_1.c

[John Z]

Hi cosh  (hyperbolic cosine?)

I wrote a linked list sorting program before that I actually use quick sort to sort separate linked list nodes and finally combine them together.
Here is the code:https://github.com/coshcage/StoneValley/blob/master/Samples/exp_2018-09-26_1.c

Have you successfully built the "StoneValley" lib with PellesC 11.002?

John Z

[MrBcx]

Hi cosh  (hyperbolic cosine?)

John Z

Actually, it's Professor K.C. Wang.
Dr. Wang's files on Github cite his book:

https://books.google.com/books?id=qbB3DgAAQBAJ&printsec=frontcover&dq=Embedded+and+RealTime+Operating+Systems&hl=en&newbks=1&newbks_redir=1&sa=X&ved=2ahUKEwiGnJHcqPT8AhX4K0QIHUlKDJ8Q6AF6BAgCEAI

https://www.amazon.com/Embedded-Real-Time-Operating-Systems-K-C/dp/3319846728/ref=sr_1_4?qid=1675254919&refinements=p_27%3AK.C.+Wang&s=books&sr=1-4&ufe=app_do%3Aamzn1.fos.006c50ae-5d4c-4777-9bc0-4513d670b6bc

[cosh]

Hi cosh  (hyperbolic cosine?)

Hi, John Z
It's been a long time that I haven't visit forum for many reasons that I was struggling with such a mess thing around me. I am sorry.
I am very glad to hear your message. I have tested StoneValley project on recent Pelles C IDE/Compiler.
For such nearly 2 years, I have been advancing StoneValley project continuously and the latest version of StoneValley is 1.1.9.1.
Of course, SV 1191 has been successfully tested under Pelles C 11.00.2. I hope this tiny project can help others.

By the way, for nick my name, it's a pun. The 1st. meaning of Cosh is hyper-cosine. The 2nd. meaning of Cosh is something like a short rod because I am tall and thin and I look like a rod.  So I decide that Je m' appelle Cosh. And for sure that you can call me Cosh directly.

Regards,

[cosh]

Hi cosh  (hyperbolic cosine?)

I wrote a linked list sorting program before that I actually use quick sort to sort separate linked list nodes and finally combine them together.
Here is the code:https://github.com/coshcage/StoneValley/blob/master/Samples/exp_2018-09-26_1.c

Have you successfully built the "StoneValley" lib with PellesC 11.002?

John Z

Sorry I'm not K.C. Wang but I am one of his student. Cosh is a now an ordinary programmer. I modified professor Wang's UPOS and republished it to my Github page.