The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Insertion sort:
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed
Pseudocode for selection sort
- Starts by considering the first two elements of the array data, if out of order, swap them
- Consider the third element, insert it into the proper position among the first three elements.
- Consider the forth element, insert it into the proper
Example
Consider the following array:
We have to sort the array in increasing order. So, first we take first 2 elements i.e. 28 and 18 and swap them as they are out of order.
2nd pass - Now, we consider first 3 elements. As, 7 is smallest element, we bring it in 0th index, and shift the rest of the elements from there on, as they are already sorted. So, the idea is to exchange the element selected in this pass (here 7) to swap with all elements in the left which are higher than that element.
Likewise, the algorithm goes on.
Pseudocode
public static void sort(int[] array)
{
int N = array.length;
for(int i=0;i < N;i++)
for(int j=0;j>0;j--)
if(a[j] < a[j-1])
swap(a[j],a[j-1]);
else
break;
}
Implementation in cpp
Implementation in cpp using templates
#include <iostream>
#include <string.h>
template <typename T>
class InsertionSort
{
public:
InsertionSort();
~InsertionSort();
void sort(T arr[], int size);
private:
void compareExchange(T arr[], int l, int r);
bool greater(T left, T right);
};
//Constructor
template <typename T>
InsertionSort<T>::InsertionSort(){}
//Destructor
template <typename T>
InsertionSort<T>::~InsertionSort(){}
template <typename T>
void InsertionSort<T>::sort(T arr[], int size)
{
for(int i = 1; i < size; ++i)
{
for(int j = i; j > 0; --j)
{
compareExchange(arr, j-1, j);
}
}
}
template <typename T>
void InsertionSort<T>::compareExchange(T arr[], int l, int r)
{
if(greater(arr[l], arr[r]))
{
T temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
}
template <typename T>
bool InsertionSort<T>::greater(T left, T right)
{
return left > right;
}
template <>
bool InsertionSort<const char*>::greater(const char *left, const char *right)
{
return strcmp(left, right) > 0;
}
template <typename T>
void print(T arr[], int size)
{
for(int i = 0; i < size; ++i)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
template <>
void print(std::string arr[], int size)
{
for(int i = 0; i < size; ++i)
std::cout << arr[i].c_str() << " ";
std::cout << std::endl;
}
template <>
void print(const char *ptrArray, int size)
{
for(int i = 0; i < size; ++i)
std::cout << ptrArray[i] << " ";
std::cout << std::endl;
}
int main()
{
int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
InsertionSort<int> isInt;
isInt.sort(arr, 9);
print(arr, 9);
std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
InsertionSort<std::string> isString;
isString.sort(strArr, 8);
print(strArr, 8);
const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
InsertionSort<const char*> isPtr;
isPtr.sort(ptrArray, 9);
print(ptrArray, 9);
return 0;
}
Implementation in java using generics
import org.junit.Assert;
import org.junit.Test;
class GenericInsertionSorter
{
public <T extends Comparable<T>> void sort(T[] elems) {
int size = elems.length;
for (int outerLoopIdx = 1; outerLoopIdx < size; ++outerLoopIdx) {
for (int innerLoopIdx = outerLoopIdx; innerLoopIdx > 0; --innerLoopIdx) {
if (elems[innerLoopIdx - 1].compareTo(elems[innerLoopIdx]) > 0) {
T temp = elems[innerLoopIdx - 1];
elems[innerLoopIdx - 1] = elems[innerLoopIdx];
elems[innerLoopIdx] = temp;
}
}
}
}
}
public class InsertionSortTester
{
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() {
GenericInsertionSorter ss = new GenericInsertionSorter();
ss.sort(unsortedNames);
Assert.assertArrayEquals(unsortedNames, sortedNames);
}
}
