Sorting
Sorting
Bubble
- Start with last item
- compare with previous and if previous large swap
- move to next
- Continue until first item reached→ smallest item will be the 1st position.
- Start at last and repeat until 2nd item reached. → 2nd smallest at 2nd place.
- Repeat until all items are in order.
Java implementation
static void bubble_sort(int [] data) {
int i,j;
for(i=0; i < data.length; i++) {
for(j = data.length-1; j > i; j--) {
if(data[j] < data[j-1]) {
int tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp;
}
}
}
}
If no swaps in one pass then you are done (No need check again)
With Optimization
static void bubble_sort_opt(int [] data) {
int i,j;
boolean quit = false;
for(i=0; i < data.length; i++) {
quit = true;
for(j = data.length-1; j > i; j--) {
if(data[j] < data[j-1]) {
int tmp = data[j];
data[j] = data[j-1];
data[j-1] = tmp;
quit = false;
}
}
}
}
Selection
Find the smallest item in the unsorted list put it at the end of the sorted list. Continue until sorted.
static void selection_sort(int [] data) {
int i,j;
for(i=0; i < data.length-1; i++) {
int m = i;
for(j = i+1; j < data.length; j++) {
if(data[j]<data[m])m=j;
}
int tmp = data[m];
data[m] = data[i];
data[i] = tmp;
}
}
Insertion
Find i th item and insert into the correct place amongst the already sorted (i-1) items. Placed by moving all items one location upwards.
static void insertion_sort(int [] data) {
int i;
for(i=1; i < data.length; i++) {
int k = data[i];
int j = i-1;
/* Move elements of data[0..i-1] that are greater than key, to one position
ahead of the current position*/
while(j>=0 && data[j]>k){
data[j+1]=data[j];
j = j-1;
}
data[j+1]=k;
}
}