Calculating sorting performance

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;
	
}

@Mosh Yes thank you! But execution time is system dependable, while this method is independable. I'll look into the execution time.

Sweni wrote: I'll look into the execution time.

On linux you can just do something like markuptime ./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.

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.