The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
What is Bubble Sort?
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required.
The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order).
This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.
Example
Consider the array - {28, 18, 7, 4, 10}
So, in first pass is bubbled at the top, it being the smallest.
Finally 4 is on top.
Now, in second pass, 10 bubbles out , it being second smallest element and so on:
Bubble sort implementation in c
void bubbleSort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
Bubble sort in cpp:
#include <iostream>
class BubbleSort
{
public:
BubbleSort(){}
~BubbleSort(){}
void sort(int arr[], int size);
};
void BubbleSort::sort(int arr[], int size)
{
//With every iteration in outer loop, the next maximum element is moved to it's correct position
for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
{
for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
{
//Comparing two subsequent elements OR bubble comparison
//Placing the larger element on the right
if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
{
int temp = arr[innerLoopIdx];
arr[innerLoopIdx] = arr[innerLoopIdx + 1];
arr[innerLoopIdx + 1] = temp;
}
}
}
}
void print(int arr[], int size)
{
for(int i = 0; i < size; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main()
{
int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
BubbleSort bs;
bs.sort(arr, 9);
print(arr, 9);
return 0;
}#include <iostream>
class BubbleSort
{
public:
BubbleSort(){}
~BubbleSort(){}
void sort(int arr[], int size);
};
void BubbleSort::sort(int arr[], int size)
{
//With every iteration in outer loop, the next maximum element is moved to it's correct position
for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
{
for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
{
//Comparing two subsequent elements OR bubble comparison
//Placing the larger element on the right
if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
{
int temp = arr[innerLoopIdx];
arr[innerLoopIdx] = arr[innerLoopIdx + 1];
arr[innerLoopIdx + 1] = temp;
}
}
}
}
void print(int arr[], int size)
{
for(int i = 0; i < size; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
int main()
{
int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
BubbleSort bs;
bs.sort(arr, 9);
print(arr, 9);
return 0;
}
Bubble sort in java
To come
Bubble sort in java using Generics
import org.junit.Assert;
import org.junit.Test;
class GenericBubbleSorter<T extends Comparable<T>>
{
public void sort(T[] elems) {
int size = elems.length;
for (int outerLoopIdx = 0; outerLoopIdx < size; ++outerLoopIdx) {
for (int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx) {
if (elems[innerLoopIdx].compareTo(elems[innerLoopIdx + 1]) > 0) {
T temp = elems[innerLoopIdx];
elems[innerLoopIdx] = elems[innerLoopIdx + 1];
elems[innerLoopIdx + 1] = temp;
}
}
}
}
}
public class BubbleSortTester
{
private String[] unsortedNames = new String[] {
"Pankaj",
"Paresh",
"Ankit",
"Sankalp",
"Aditya",
"Prem",
"Rocket",
"Singh",
"Alabama",
"Alaska",
"Animal" };
private String[] sortedNames = new String[] {
"Aditya",
"Alabama",
"Alaska",
"Animal",
"Ankit",
"Pankaj",
"Paresh",
"Prem",
"Rocket",
"Sankalp",
"Singh" };
@Test
public void testStringSort() {
GenericBubbleSorter<String> bs = new GenericBubbleSorter<String>();
bs.sort(unsortedNames);
Assert.assertArrayEquals(unsortedNames, sortedNames);
}
}
Thanks.
