Sorting rearranges the elements in a list into either ascending or descending order (we’ll use ascending order). In this post we discuss three O(n2) sorting algorithms only. These include Bubble sort, Selection sort, and Insertion Sort.

Bubble Sort

Compares neighboring pairs of array elements, starting with the last array element, and swaps neighbors whenever they are not in correct order. On each pass, this causes the smallest element to “bubble up” to its correct place in the array.

Selection Sort

Divides the array into two parts: already sorted, and not yet sorted. On each pass, finds the smallest of the unsorted elements, and swaps it into its correct place, thereby increasing the number of sorted elements by one.

Insertion Sort

Works like someone who “inserts” one more card at a time into a hand of cards that are already sorted. For example, To insert 12, we need to make room for it by moving first 36 and then 24 in an array of 6, 10, 24 and 36.

Demonstration in C++

#include <iostream>
#include <conio.h>
#include <stdio.h>

void bubbleSort(int[],int );
void insertionSort(int[],int);
void selectionSort(int[],int);

int main()
{
	/* Bubble Sort Demonstration */
	printf("Bubble Sort Demonstration\n");
	int a[200] = {2, 10, 5, 3, 8, 7, 32, 29, 18, 20};
	bubbleSort(a, 10);
	for(int i=0; i<10; i++)
	{
		printf("%d\n", a[i]);
	}

	/* Selection Sort Demonstration */
	printf("\nSelection Sort Demonstration\n");
	int b[200] = {2, 10, 5, 3, 8, 7, 32, 29, 18, 20};
	bubbleSort(b, 10);
	for(int i=0; i<10; i++)
	{
		printf("%d\n", b[i]);
	}

	/* Insertion Sort Demonstration */
	printf("\nInsertion Sort Demonstration\n");
	int c[200] = {2, 10, 5, 3, 8, 7, 32, 29, 18, 20};
	bubbleSort(c, 10);
	for(int i=0; i<10; i++)
	{
		printf("%d\n", c[i]);
	}
}

void bubbleSort(int arr[], int size)
{
	for (int i=0; i < size; i++)
		for (int j = size-1; j>i; j--)
		{
			if(arr[j] < arr[j-1] )
			{
				int temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			}
		}
}

void selectionSort(int arr[], int size)
{
	for (int i=0; i < size; i++)
	{
		int min = i;
		for (int j=i+1; j < size; j++)
		     if(arr[j] < arr[min] )
			min = j;

		if (min != i)
		{
		     int temp = arr[i];
		     arr[i] = arr[min];
		     arr[min] = temp;
		}
}
}

void insertionSort(int arr[], int size)
{
	for (int i=1; i< size; i++)
	{
		int value = arr[i];
		int j;
		for(j = i-1; j >= 0 && arr[j] > value;  j--)
			arr[j+1] = arr[j];
		arr[j+1] = value;
	}
}
Tagged with: C/C++ languageProgrammingSource Code
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.