Follow us on Twitter!
Few are those who can see with their own eyes and hear with their own hearts. - Albert Einstein
Wednesday, April 23, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 23
Guests Online: 20
Members Online: 3

Registered Members: 82885
Newest Member: ConiBE
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming

Author

Calculating sorting performance


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 25-06-10 21:58
Hello Hellboundhackers!
I've started to look into sorting algorithms and I wonder how you calculate the performance.
Like bubble sort have a worst case performance on O(n^2) and best case on O(n).
How do you calculate this? What's the worst / best case for my algorithm?

I'm pretty new to sorting, so please send me some feedback or links if you have.

The code:
Code

int arr[size];
int sorted[size+1];
int p = 1;

while(!is_sorted(arr)) {
   sorted[0] = arr[0];

   for(int i = 1; i < size; ++i) {
      ++k;
      if(sorted[p]) {
         if(arr[i] <= sorted[p] && arr[i] >= sorted[p-1]) {
            sorted[p+1] = sorted[p];
            sorted[p] = arr[i];

         } else if (arr[i] >= sorted[p] && arr[i] >= sorted[p-1]) {
            sorted[p+1] = arr[i];
         
         } else {
            sorted[p+1] = sorted[p];
            sorted[p]   = sorted[p-1];
            sorted[p-1] = arr[i];                                                         

         }
      } else {
         if(arr[i] > sorted[p]) {
            sorted[p] = arr[i];
            
         } else {
            sorted[p+1] = sorted[p];
            sorted[p] = arr[i];
            
         }
         --p;
         
      }
      ++p;
      
   }

   for(int x = 0; x < size; ++x) {
      arr[x] = sorted[x];
      sorted[x] = 0;
      
   }
   p = 1;
   
}



Author

RE: Calculating sorting performance


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 25-06-10 22:19
@Mosh
Yes thank you!
But execution time is system dependable, while this method is independable.
I'll look into the execution time.
Author

RE: Calculating sorting performance


Member

Your avatar

Posts:
Location:
Joined: 01.01.70
Rank:
Guest
Posted on 26-06-10 07:11
Sweni wrote:
I'll look into the execution time.


On linux you can just do something like
Code
time ./a.out




That should be a pretty good indicator of how fast it runs. Also, you could loop it in a bash script to run it 100 times back to back and take the average or something.


Author

RE: Calculating sorting performance

GTADarkDude
Member



Posts: 142
Location: The Netherlands
Joined: 23.02.08
Rank:
Newbie
Posted on 26-06-10 14:13
Whether you end up with the best or worst case scenario, depends on the data you're sorting. In the case of bubble sort, you get a time complexity of O(n) when you're sorting an already completely sorted list.
To correctly measure different sorting algorithms, you should try this with multiple different lists, as it's hard to determine how sorted your data already is when it's not an extreme case. Then just let it sort the data like a couple of hundred of times and keep track of time by using the right functions. In C++ for example, include ctime and use time() before and after, and calculate the difference.


...

Edited by GTADarkDude on 26-06-10 14:14
- - -