Print

[lavakill]

This is a program that I wrote that will allow you to analyze the performance of the following sorting algorithms by providing the sort times of each sorting algorithm. 

• Bubble sort
• Insertion sort
• Merge sort
• Selection sort
• Quicksort
• Heapsort
• Shellsort

This program only supports integers.
The sort times (and step counts) will be outputted into a text and/or excel file.
You may also provide a text file or .csv file (excel file) with numbers to be sorted.
For more information read the Readme.txt file in the download.

---------------------------------------------------------------------------
- Version 1.0.4
---------------------------------------------------------------------------

- Fixed crash on the cancel sorting progress

---------------------------------------------------------------------------
- Version 1.0.3
---------------------------------------------------------------------------

- Increased the up-down counter's maximum values
Range -> Max: 1073741823
      -> Min: 1073741823
OneList -> Size   : 50,000,000
Multi -> firstList: 10,000,000
      -> lastList : 50,000,000
      -> increment: 10,000,000

- Fixed incorrect value of the first generated stepcount

- Fixed memory leaks

- Other minor fixes

- Add Shellsort algorithm

---------------------------------------------------------------------------
- Version 1.0.2
---------------------------------------------------------------------------

- Fixed random elements swapped methods. List size of 1 and 2 now work
correctly.

Version: 1.0.4 (written in C++)
Download
Download(with Source Code)

[Trace]

Nice, in C++ I see. Any reason why you wrote it? For a school project?
I did read some stuff about C++ a while back but I didnt have enough time and also lacked inspiration for something to program with it :p

[lavakill]

Originally it was written for a school project, however it was just a win32 console application, so no GUI, just a console window.  Also it was just for bubble, insertion, and merge sort.  Then months after I decided to add more to it (actually rewrite all of it as the original code was messy) and add a GUI just for the fun of it, as it was something to do.

[dhdc]

Have you ever seen these YouTube Videos? They were posted on r/programming/ a couple of weeks back. They were posted with the title "Sounds of Sorting"

[lavakill]

I've updated the program.

---------------------------------------------------------------------------
- Version 1.0.1
---------------------------------------------------------------------------

- User file is now correctly checked

- Fixed 'Program Not Responding'
- Added a progress bar
- Added the function to cancel the sorting progress

- Fixed the ascending/descending methods

And also, shame on you guys for not testing my program out and letting me know that the ascending/descending methods were not working .

[StealthEye]

Weekly updates! Nice release cycle!

I still intend to have a look at your code (and add radix sort if I get to it ), I just didn't find the time yet.

[lavakill]

Great and if you have more time, other sorting algorithms, or just minor performance enhancements to the one's I already have would be awesome.

And also here's a minor fix.

---------------------------------------------------------------------------
- Version 1.0.2
---------------------------------------------------------------------------

- Fixed random elements swapped methods. List size of 1 and 2 now work
correctly.

[dhdc]

What about bogo sort?

And the solution is from a newer version of vis studio so i can't open it:*(

[lavakill]

No bogo sort ... just no.

[StealthEye]

Try this (it's not bogosort)

1. Generate a new array with random contents of the same length as the input array.
2. Check if the array is sorted.
3. Check if the generated array contains the same items.
4. Otherwise, try again.

More useful algorithms: http://stackoverflow.com/questions/2609857/are-there-any-worse-sorting-algorithms-than-bogosort-a-k-a-monkey-sort

[lavakill]

I'm not going to add anything that has the worse case as being unbounded .

Nice link Seye .

[StealthEye]

Oh, in that case, just generate all permutations, and find the sorted one! Only exponential, not unbounded.

[lavakill]

Updated again...

---------------------------------------------------------------------------
- Version 1.0.3
---------------------------------------------------------------------------

- Increased the up-down counter's maximum values
Range -> Max: 1073741823
          -> Min: 1073741823
OneList -> Size   : 50,000,000
Multi -> firstList: 10,000,000
        -> lastList : 50,000,000
        -> increment: 10,000,000

- Fixed incorrect value of the first generated stepcount

- Fixed memory leaks

- Other minor fixes

- Add Shellsort algorithm

If someone has free time on their hands then it would be helpful if you implement these for me:
- radix sort
- bucket sort
- library sort
- patience sort
- smooth sort

Eventually I'll implement these, but it'll take quite a while.

[StealthEye]

One variant of radix sort (tested, albeit not thoroughly):

Code: [Select]

void SortingAlgorithms::RadixSort(int list[], unsigned int sizeOfList)
{
const int maxShift = sizeof(int)*8; // normally 32 or 64 bits
const int bucketBits = 4; // best be a divisor of maxShift
const int bucketCount = 1 << bucketBits; // must be a power of two

int* input = list;
int* output = new int[sizeOfList];

// Sort, starting with least significant bits.
for (int shift = 0; shift < maxShift; shift += bucketBits)
{
int bucket[bucketCount] = {0};

// Count items per bucket.
for (int i = 0; i < sizeOfList; ++i)
{
++bucket[(input[i] >> shift) & (bucketCount - 1)];
}
// Determine offset to end of bucket (exclusive).
for (int i = 1; i < bucketCount; ++i)
{
bucket[i] += bucket[i-1];
}
// Write items (stable sort on the relevant bits).
for (int i = sizeOfList-1; i >= 0; --i)
{
output[--bucket[(input[i] >> shift) & (bucketCount - 1)]] = input[i];
}
// Swap buffers
int* newInput = output; output = input; input = newInput;
}

// Swap buffers back if necessary (iff. ceil(maxShift / bucketBits) is odd)
if (output != list)
{
for (int i = 0; i < sizeOfList; ++i)
{
list[i] = output[i];
}
}
delete output;
}

I believe bucket sort is pretty much the same idea (although it may be mixed with other algos).

Only works for radii that are powers of two (allows some optimizations).

[lavakill]

Great, I'll take a look at that later.

---------------------------------------------------------------------------
- Version 1.0.4
---------------------------------------------------------------------------

- Fixed crash on the cancel sorting progress

I fix the memory the leaks and end up creating a bug.  You win some and you lose some.