Home arrow C++ arrow Page 2 - Bubble Sorts And C++

Bubble Sorts And C++

The bubble sort algorithm is the simplest known method of sorting an array of data. In this article Steve describes the concepts behind several sorting methods, focusing on bubble sorts in general. He also creates a C++ sample application that bubble sorts an array of integers.

Author Info:
By: Steve Adcock
Rating: 4 stars4 stars4 stars4 stars4 stars / 81
February 13, 2002
  1. · Bubble Sorts And C++
  2. · Sorting algorithms
  3. · Blowing a bubble
  4. · The bubble sort code
  5. · Conclusion

print this article

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:

An array of integers 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?
blog comments powered by Disqus

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials