Author : Iordan Pavlov
Page : 1
This little tutorial and the dsort algorythms are written by Iordan
Pavlov(e-mail:dani84_vd@yahoo.com)
I'll begin with how did I created the dsort algorythm.
I was making one of my first real programs with C++ and Qt for GUI for Linux.
It should be able to manage around 5000 files for cash registers.So I needed an algorythm for searching in database containing around 5000 objects.
And It should be very fast. I made a function dfind which uses max 150 if()s to find something in a 5000 element array.After some time and advices from friends I made it use around 12 if()s for the same array(that's may be the fastest method in the world and it seems I just reinvented it).But this function dfind serches only in sorted arrays(a little trouble). I knew for quicksort but I don't fully understand it but after all I needed something a lot faster than bubblesort so I made dsort.In fact it is similar to bubblesort but the if() it needs to sort an array are max equal to the if()s that bubblesort needs and I think that happens extremely rarely. I testeted it on Win98 and it's around 80% faster than fast_bi_bubble sort(I used the same array read from a file).
Now let's understand how the dsort function sorts an array.
Let's say we have a 5000 elements array.
To sort such array we will need 4999 basic compares.
Now it's quite simple(you can look at the source provided).We begin with the first element and compare it with the next.If it is bigger we swap them else we go ahead.But you'll say "Will the result be a really sortet array?".No,to explain the basis of the method we'll need to go let's say to the 50th element.We compare it with the 51th element and let's say the 50th element is bigger -then we swap them but we don't know if the ex 51th element is really the 50th in the sorted array so we enter a loop that begins with the place of the smallest one of the swapped elements.This loop(for() loop) ends at the beginning of the array(the first element on the 0th place).We compare the element of wich we want to find the real place in the array with the elements before it in the array using the index of the for() loop and when we find the place we go back to the place we begun the backward loop.
In that way we move the big elements forward and the small elements backward in the array and when we finish with the 4999th base compare (between the 4999 and the 5000th element) we have a sorted array.
That's it,don't you think it's quite simple.
In the near future I think to make ot like quick sort-first divide the array of two parts and move the biggest elements in the one one half of the array and the smallest elements in the other.In that way we'll sort the array around two times faster.
I accept ideas for improving the dsort sorting algorythm on my current e-mail:
dani84_vd@yahoo.com.
Page : 1