Bubble Sorts And C++ - Sorting algorithms
(Page 2 of 5 )
If you've worked with any data intensive sorting algorithms before, then you would've had to make an informed decision about which sort method to use. Once you understand the logic of a sorting algorithm, it's fairly easy to implement that algorithm: the hard part is optimizing the algorithm to perform under processor intensive operations, such as when multiple threads are used to run the algorithm on 10,000 sets of complex data.
There are dozens of different sorting algorithms in existence to sort everything from numbers to vectors to custom-defined objects. The four most common sorting algorithms are the heap sort, merge sort, quick sort and bucket sort. Let's take a brief look at each of these now:
- Heap Sort: As the name suggests, a heap sort works with data in a heaped format. It starts with a list and turns that list into a copy of whatever data structure we're using. The smallest object in the data structure is found and is then removed, meaning that the heap sorting algorithm start with the smallest-valued objects and works its way up to the largest-valued objects.
- Merge Sort: The merge sort algorithm splits items to be sorted into two groups; recursively sorts each group, and then merges both groups into a final, sorted sequence.
- Quick Sort: The quick sort algorithm contains two phases: the partition phase, which splits an array of data into two separates partitions, and the sort phase, which sorts each partition. The quick sort algorithm is extremely popular, and is also known as the "divide and conquer" method.
A quick sort algorithm divides an array of items into partitions and calls a quick sort procedure to recursively sort the partitions. Each call to the quick sort procedure divides the results into two further groups until each item in the array is ordered correctly. - Bucket Sort: The bucket sort is a distribution sort where input elements are initially distributed to several "buckets" based on an interpolation of the elements key. Each bucket is sorted if needed, and the buckets contents are concatenated to form the resultant sorted values.
All of these sorting algorithms are great, but most are extremely complex to implement. Luckily, the bubble-sorting algorithm is based on simple logic and its ideas are elementary. The bubble sort looks at two positions within an array, compares the values in those positions, and swaps the values if the latter value is less than the first.
Note: Before we continue, if you are not familiar with arrays then you might get lost in code quite quickly. Allow me to take a moment to explain the concept of an array. Simply speaking, an array is an indexed data type that can hold more than one value. So, instead of a variable named Num holding just the one value, if we declare Num as an array, then it can hold many. Let's look at a quick example.
int Num[6]={10, 12, 14, 16, 18, 20};This array would look something like this in memory:
Since the number 10 was defined first, it will rest in the index position 0. 12 was defined next, so it will rest in index position 1, and so on. We work with values within arrays by the index of the value we're after. So if we wanted to work with the value 10 in our Num integer array, then we'd reference Num[0]. If we wanted to work with 20, we'd reference Num[5], etc... get it?
Next: Blowing a bubble >>
More C++ Articles
More By Steve Adcock
/ 62 
