Insertion Sort in Java/C of an Integer Array

Average Performance: О(n²)
Best Case Performance:О(n)
Worst Case Performance: О(n²)
Classification: stable, in-place, online

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: [from Wiki]

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

Below source code is written in Java, but you can use the function insertionSort() without any modification. Just write your main() function with input array and call insertionSort() with two parameters: array and array size.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

insertionSort(input, input.length);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\n Outerfor loop: " + counter1 + " times, inner while loop: " + counter2 + " times");
}

public static void insertionSort(int input[], int length) {
int i, j, key;

for(i = 1; i<length;i++) {
counter1++;
key = input[i];
j = i - 1;

while (j>=0 && input[j] > key) {
counter2++;
input[j+1] = input[j];
j--;
}
input[j+1] = key;
}
}
}

Read more »

Posted in: C,Insertion Sort,Java,Programming,sorting algorithm

Merge Sort in Java/C of an Integer Array

Conceptually, a merge sort works as follows [From wiki]

1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying the merge sort.
4. Merge the two sublists back into one sorted list.

Merge sort incorporates two main ideas to improve its runtime:

1. A small list will take fewer steps to sort than a large list.
2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted .

public class CodeTest {
static int counter =0;

public static void main(String[] args) {
int input[] = {94,34,53,21,100,102, 21, 53,45, 456, 3, 32,1,5,4};

System.out.print("Before Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

mergeSort(input, 0, input.length-1);

System.out.print("\nAfter Sorting: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");

System.out.println("\nmergerSort() Function is called " + counter + " times");
}

public static void mergeSort(int input[], int left, int right) {
int center;

counter++;

if (left < right) {
center = (left + right)/2;
mergeSort(input, left, center);
mergeSort(input, center+1, right);

merge(input, left, right, center);
}
}

public static void merge(int input[], int left, int right, int center) {
int i = left, j = center + 1, idx = left;
int[] temp = new int[input.length];

while( i<=center && j<=right) {
if(input[i] < input[j])
temp[idx++] = input[i++];
else if (input[i] > input[j]) 
temp[idx++] = input[j++];
else {
temp[idx++] = input[i++];
temp[idx++] = input[j++];
}

if(i > center ) 
while(j<=right)
temp[idx++] = input[j++];
else if (j > right)
while(i<=center)
temp[idx++] = input[i++];
}

for (i = left; i <=right; i++)
input[i] = temp[i];
}
}

Read more »

Posted in: C,Java,Merge Sort,mergesort,Programming,sorting algorithm

Binary Search of an Integer Array

Binary Search Program. It's written in Java, but it's almost same as C program. All you need is just use 'sizeOf()' macro (fuction) to get the length of array.

public static void main(String[] args) {
int input[] = {1,3,5,6,7,8,9,10,11};
                int query = 3;
System.out.println(query + " is in input[" + binarySearch(input, query) + "].");
}

public static int binarySearch(int tree[], int query) {
int beg = 0;
int end = tree.length-1;
int mid = (beg+end)/2;

for(int i=1; mid >=0 ;i++) {
System.out.println(i+ "th try - index:" + (mid + 1) + "/" + tree.length);
if(tree[mid] == query)
break;
else if(tree[mid] > query)
end = mid - 1;
else
beg = mid +1;

mid = (beg + end)/2;
   if (beg >= med)
      mid = -1;
}
return mid;
}

Read more »

Posted in: Binary Search,C,Java,Programming,Search Algorithm