Brute Force Sorting Algorithms

The brute force sorting method is the simplest of the design strategies and in most cases the easiest to apply. The brute force approach is used for many algorithmic tasks such as finding the largest numerical value in an array and finding the sum of n numbers. Although the brute force approach is very costly as it must exhaust all items in a list, it is sometimes the only solution and therefore the cost is acceptable. Let us explore some different brute force sorting algorithms and take a closer look at their properties.

The Problem:
Given a list of n orderable items in an array, rearrange them in increasing order.

Selection Sort
Selection sort is the simplest of the sorting algorithms. It begins by scanning the entire array for the smallest element. This element then gets swapped with the element stored in the first position of the array. Then it again scans the list, starting with the second element for the next smallest element, swapping it with the element in position two. This process continues until all n elements have been arranged in increasing order. Selection Sort is a O(n^2) algorithm in all cases (best, worst, average). This means for n elements in an array it will take n^2 steps to complete the sort.

Bubble Sort
Bubble Sort begins by comparing the first two elements in the array. If element two is less than element one, the elements are swapped. Next, elements two and three are compared and swapped if need be. This process continues until the array is sorted. Essentially Bubble Sort compares adjacent elements and swaps them if they are out of order. After a few iterations the algorithm will "Bubble Up" the largest element to the last position. Bubble Sort is also a O(n^2) algorithm for all cases (best, worst, average). An example of the worst case would be a decreasing array.