Archive for February, 2008

SelectionSort

February 17, 2008 at 8:51 pm · Filed under Sorting Algorithms ·Tagged

O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity. Selecting the lowest element requires scanning all n elements (this takes n – 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n – 1
elements and so on, for (n – 1) + (n – 2) + … + 2 + 1 = n(n – 1) / 2 =O(n2) comparisons. Each of these scans requires one swap for n – 1 elements (the final element is already in place). Thus,the comparisons dominate the running time, which is O(n2).


public class SelectionSort {
public int[] sort(int[] data) {
int minIndex;
for (int i = 0; i < data.length; i++) {
minIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
return data;
}
public static void main(String[] args) {
int[] data = new int[] { 8,15,4,23,16,42 };
System.out.println(new SelectionSort().sort(data).toString());
}

Leave a Comment

BubbleSort

February 17, 2008 at 8:37 pm · Filed under Sorting Algorithms ·Tagged

Bubble sort has best-case complexity O(n). When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. Thus bubblesort will make only n comparisons and determine that list is completely sorted. It will also use considerably less time O(n2) than if the elements in the unsorted list are not too far from their sorted places.


public class BubbleSort {
int[] data;
public BubbleSort(int[] data) {
super();
this.data = data;
}
public int[] sort() {
boolean isSwap = false;
int temp = 0;
do {
isSwap = false;
for (int i = 0; i data[i + 1]) {
temp = data[i];
data[i] = data[i + 1];
data[i + 1] = temp;
isSwap = true;
}
}
} while (isSwap);
return data;
}
/**
* instead of doing n2 comparisons (and swaps), we can use only
* n + (n-1) + (n-2) + ... + 1 comparisons.
* This sums up to n(n + 1) / 2, which is still
* O(n2), but which can be considerably faster in practice.
*
* @return sorted data
*/
public int[] optimezedSort() {
boolean isSwap = false;
int temp = 0;
int n = data.length - 1;
do {
isSwap = false;
n = n - 1;
for (int i = 0; i data[i + 1]) {
temp = data[i];
data[i] = data[i + 1];
data[i + 1] = temp;
isSwap = true;
}
}
} while (isSwap);
return data;
}
public static void main(String[] args) {
int[] data = new int[] {1,2,3,4,5,8,6,9,7};
System.out.println(Arrays.toString(new BubbleSort(data).sort()));
System.out.println(Arrays.toString(new BubbleSort(data).optimezedSort()));
}
}

Leave a Comment

Older Posts »