Sorting: Bubble Sort
13th January 2006 - By Paradochs
Information
- Order: O(n²)
- Best Case: O(n)
- Average: ?
- Memory Usage: O(1)
- Stable: Yes
- Comparison Based: Yes
Description (from wikipedia)
Bubble sort, also known as exchange sort, is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top (i.e. head) of the list via the swaps. Because it only uses comparisons to read elements, it is a comparison sort.
In more detail, the bubble sort algorithm works as follows:
- Compare adjacent elements. If the first is greater than the second, swap them.
- Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest.
- Repeat the steps for all elements except the last one.
- Keep repeating for one fewer element each time, until you have no more pairs to compare. (Alternatively, keep repeating until no swaps are needed.)
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:9 Feb 05
File: BubbleSort.h
*/
#include <time.h>
class BubbleSort {
public:
BubbleSort();
BubbleSort(int *,int);
~BubbleSort();
int * getArray();
int getN();
bool getSorted();
double getTime();
int getIncrements();
void setArray(int *);
void sort();
private:
void setN(int);
void setSorted(bool);
void resetTime();
void resetIncrements();
int * A;
int n;
bool sorted;
double time;
int increments;
};
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 9 Feb 05
Updated:16 Feb 05
File: BubbleSort.cpp
*/
#ifndef BUBBLESORT_H
#define BUBBLESORT_H
#include "BubbleSort.h"
#endif
BubbleSort::
BubbleSort() {
n = 1;
A = new int[n];
A[0] = 0;
sorted = true;
}
BubbleSort::
BubbleSort(int * newArray, int N) {
n = N;
A = new int[n];
for(int i=0; i<n; i++)
A[i] = newArray[i];
sorted = false;
resetIncrements();
}
BubbleSort::
~BubbleSort() {
delete(A);
}
int *
BubbleSort::
getArray() {
return A;
}
int
BubbleSort::
getN() {
return n;
}
bool
BubbleSort::
getSorted() {
return sorted;
}
double
BubbleSort::
getTime() {
return time;
}
int
BubbleSort::
getIncrements() {
return increments;
}
void
BubbleSort::
setArray(int * newArray) {
delete(A);
n = sizeof(newArray);
A = new int[n];
sorted = false;
}
void
BubbleSort::
sort() {
clock_t t1, t2;
t1 = clock();
for(int i=0; i<n-1; i++)
for(int j=n-1; j>=i+1; j--)
if(increments++, A[j]<A[j-1]) {
int t = A[j];
A[j] = A[j-1];
A[j-1] = t;
}
t2 = clock();
time = (t2 - t1)/CLOCKS_PER_SEC;
}
void
BubbleSort::
setN(int newN) {
n = newN;
}
void
BubbleSort::
setSorted(bool newSorted) {
sorted = newSorted;
}
void
BubbleSort::
resetTime() {
time = 0.0;
}
void
BubbleSort::
resetIncrements() {
increments = 0;
}