HellBound Hackers
Join us at IRC!
The measure of a mans life is not how well he dies, but how well he lives.
Wednesday, May 23, 2012
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
HellBoundHackers Additional:
Shop
Learn
Communicate
Submit
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Interact
Other
HellBoundHackers Executive:
HellBoundHackers Leisure:
Members Online
Total Online: 34
Web Spiders: 14
Guests Online: 31
Members Online: 3
moospit, quixote, vmczzyx

Registered Members: 70170
Newest Member: bahmx
Latest Articles
View Thread

HellBound Hackers | Computer General | Programming
Author

Calculating sorting performance
Sweni
Member



Posts: 36
Location: Sweden, Gothenburg
Joined: 06.06.08
Rank: God
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:

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
Sweni
Member



Posts: 36
Location: Sweden, Gothenburg
Joined: 06.06.08
Rank: God
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
mattseanbachman
Member



Posts: 57
Location: In the sky lol
Joined: 24.02.10
Rank: Elite
Posted on 26-06-10 07:11
Sweni wrote:
I'll look into the execution time.


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


That should be a pretty good indicator of how fast it runs. Also, you could loop it in a bash scblockedript 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: God
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
- - - -
Guest
Username

Password

Remember Me


Bookmark This Page
Affiliates
Adverts

 

 

Links

Anime Wallpaper Site
By using, viewing or obtaining any information contained on this site, you agree to the disclaimer.

© HellBound Hackers 2008- 2009. Since 3rd December 2004.

20602881 Unique Visits

Powered by HBH-Fusion