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

In-Place Quick Sort of An Integer Array

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. [From wiki]
The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

Time Complexity: for n entries,
   Θ(n log(n)) in the average case.
   Θ(n^2) in the worst case.

Space Complexity:
   Θ(log(n)) in the average case.
   Θ(n log(n)) when the input array is very large. the space is needed for storing variables like left, right and pivot. .

Java code for in-place Quick Sort here:

public void quickSort(int input[], int left, int right) {
int pivot = input[(left +right)/2];
int i = left, j = right;
int temp;


while (i <= j){
while(input[i] < pivot && i < right)
i++;
while(input[j] > pivot && j > left)
j--;

if (i <= j ) {
temp = input[j];
input[j] = input[i];
input[i] = temp;
i++; j--;
}
}

if (left <j)
quickSort(input, left, j);
if (i < right)
quickSort(input, i, right);
}

Read more »

Posted in: Java,Programming,qsort,Quick Sort,quicksort,Search Algorithm,sorting algorithm