Bubble Sort and Selection Sort (C)

Question

I used the "long" form of all math statements, avoided the use of pointers, and used only while loops for aesthetic purposes (simply put, I think the code is prettier when it is written like that.) I am mainly concerned about the CPU efficiency of the code.

Bubble Sort - The quintessential example of an "inefficient" sorting algorithm. Often the first sorting algorithm introduced to college students.

void BubbleSort(int Array[], int Length) { int CurrentIndex[2]; int TemporaryValue; int WasThereASwap; WasThereASwap = 1; while (WasThereASwap == 1) { WasThereASwap = 0; CurrentIndex[0] = 0; CurrentIndex[1] = 1; while (CurrentIndex[1] != Length) { if (Array[CurrentIndex[0]] > Array[CurrentIndex[1]]) { WasThereASwap = 1; TemporaryValue = Array[CurrentIndex[0]]; Array[CurrentIndex[0]] = Array[CurrentIndex[1]]; Array[CurrentIndex[1]] = TemporaryValue; } CurrentIndex[0] = CurrentIndex[0] + 1; CurrentIndex[1] = CurrentIndex[1] + 1; } } } 

Selection Sort - Usually outperforms bubble sort, but it is still not a very good sorting algorithm for large arrays.

void SelectionSort(int Array[], int Length) { int BeginComparisonsIndex; int CurrentComparisonIndex; int CurrentLowestIndex; int TemporaryValue; BeginComparisonsIndex = 0; while(BeginComparisonsIndex != Length) { CurrentComparisonIndex = BeginComparisonsIndex; CurrentLowestIndex = BeginComparisonsIndex; while (CurrentComparisonIndex != Length) { if (Array[CurrentComparisonIndex] < Array[CurrentLowestIndex]) { CurrentLowestIndex = CurrentComparisonIndex; } CurrentComparisonIndex = CurrentComparisonIndex + 1; } TemporaryValue = Array[BeginComparisonsIndex]; Array[BeginComparisonsIndex] = Array[CurrentLowestIndex]; Array[CurrentLowestIndex] = TemporaryValue; BeginComparisonsIndex = BeginComparisonsIndex + 1; } } 

Answer 1

About aesthetics

I used the "long" form of all math statements, avoided the use of pointers, and used only while loops for aesthetic purposes (simply put, I think the code is prettier when it is written like that.)

While making the code look aesthetically pleasing can be beneficial (especially if it makes it more readable), you should not give that a higher priority than writing maintainable code. The "short" form of modifying variables has the advantage that you don't have to repeat the variable name. This might make the code easier to read, but the big advantage is that it reduces potential errors: for example, it's impossible to accidentily put the wrong variable name on the right hand side if there is none to begin with. So if you'd write:

CurrentIndex[0]++; 

You can't accidentily misspell the variable name, you can't accidentily use [1] on the right hand side, and you can't accidentily write + 2 instead of + 1.

Another benefit is that incrementing a counter using ++ is more ideomatic, which means that there is a big chance that other programmers that are used to C will find the short form more natural.

Toby Speight already mentioned why for-loops can improve clarity over while-loops with separate initialization and incrementing statements.

The use of arrays instead of pointers is perfectly fine here, since you are indeed manipulating arrays.

Variable names

Descriptive variable names help understand code, but having too long variable names can start to hinder readability. Also, some one-letter variable names are justified, for example it is idiomatic to use i and j as loop counters.

Also, when you write CurrentIndex in BubbleSort(), it makes me wonder: is there also PreviousIndex or a NextIndex? If not, just Index would be better (or even just i). In SelectionSort() it makes more sense.

CPU efficiency

Your bubblesort implementation might have the advantage of quiting early if the input array was already sorted, but if it was not, then it takes twice as long as necessary. Instead of comparing two consecutive elements at a time, sort by first comparing the first element to all other elements, and swapping when necessary. After that first pass, you know that the first element is the lowest, so you don't have to consider it in the next pass anymore, and so on.

If you want to sort arrays of integers in the most efficient way, you probably want to implement radix sort.

Make sure you handle corner cases

In BubbleSort(), if the length of the input array is zero, then your code will go into an infinite loop and read out of bounds. Always check that you handle corner cases like arrays of length 0 and 1.

Another issue is that since Length is an int, someone could pass a negative value. To avoid that, use size_t Length instead (and change the type of the indices to match), or at least add in a check that Length is not negative. It still make sense to allow a length of 0 or 1.

Answer 2

It's a very unusual style to begin identifiers with uppercase letters.

Include <stdbool.h> and use the bool type for flags.

Many of the variables can be moved to smaller scopes.

I think you should use for loops where appropriate - grouping the initialisation, predicate and advance clauses together improves clarity.

Obviously this code lacks the generality of qsort() in that it can only work on arrays of int, but that may be acceptable for code that's merely didactic.