Notes
sorting
1. Bubble
sort
public
static void BubbleSort( int arr[] ) {
int n = arr.length;
for ( int i=0; i <= ( n - 2 ); i++)
for ( int j=0; j <= ( n - 2 - i );
j++)
if (arr[j+1] < arr[j])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
2. Selection
sort
The
selection sort improves on the bubble sort by making only one exchange for
every pass through the list. In order to do this, a selection sort looks for
the largest value as it makes a pass and, after completing the pass, places it
in the proper location. As with a bubble sort, after the first pass, the
largest item is in the correct place. After the second pass, the next largest
is in place. This process continues and requires n−1 passes to sort n items,
since the final item must be in place after the (n−1) st pass.
public
static void SelectionSort( int
arr[] ) {
int n = arr.length;
for ( int i=0; i <= ( n - 2 ); i++)
for ( int j=0; j <= ( n - 2 - i );
j++)
if (arr[j+1] < arr[j])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
int
unsortedArray[] = {17,3,10,16,12,4,27,15,30,1,8,3
int i;
System.out.println("Before Sorting
SelectionSort :");
for(i=0; i<unsortedArray.length; i++)
{
System.out.print(unsortedArray[i] +
" ");
}
SelectionSort(unsortedArray); //Pass the
array to be sorted and its length.
3. The
Insertion Sort
The insertion sort, although still O(n2), works in a
slightly different way. It always maintains a sorted sublist in the lower
positions of the list. Each new item is then “inserted” back into the previous
sublist such that the sorted sublist is one item larger. Figure 4 shows the
insertion sorting process. The shaded items represent the ordered sublists as
the algorithm makes each pass.
public static void
InsertionSort( int arr[] ) {
int n =
arr.length;
int
v,j;
for (
int i=1; i <= ( n - 1 ); i++)
{
v
= arr[i];
j
= i - 1;
while( j>= 0 && arr[j]
> v )
{
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = v;
}
}
4. The
Merge Sort
We now turn our attention to using a divide and
conquer strategy as a way to improve the performance of sorting algorithms. The
first algorithm we will study is the merge sort. Merge sort is a recursive
algorithm that continually splits a list in half. If the list is empty or has
one item, it is sorted by definition (the base case). If the list has more than
one item, we split the list and recursively invoke a merge sort on both halves.
Once the two halves are sorted, the fundamental operation, called a merge, is
performed. Merging is the process of taking two smaller sorted lists and
combining them together into a single, sorted, new list.
Merge Sort Recursive
import java.io.*;
import java.util.*;
import java.lang.*;
class MergeSort {
static
public void DoMerge(int [] numbers, int left, int mid, int right)
{
int []
temp = new int[25];
int i,
left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while
((left <= left_end) && (mid <= right))
{
if
(numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while
(left <= left_end)
temp[tmp_pos++] = numbers[left++];
while
(mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i
= 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
static
public void MergeSort_Recursive(int [] numbers, int left, int right)
{
int mid;
if
(right > left)
{
mid =
(right + left) / 2;
MergeSort_Recursive(numbers, left, mid);
MergeSort_Recursive(numbers, (mid + 1), right);
DoMerge(numbers, left, (mid+1), right);
}
}
public
static void main(String[] args)
{
int[]
numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };
int
len = 9;
System.out.println("MergeSort By Recursive Method");
MergeSort_Recursive(numbers, 0, len - 1);
for
(int i = 0; i < 9; i++)
System.out.println(numbers[i]);
}
}
Merge Sort Iterative
import java.io.*;
import java.util.*;
import java.lang.*;
class MergeSort {
static
public void DoMerge(int [] numbers, int left, int mid, int right)
{
int []
temp = new int[25];
int i,
left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while
((left <= left_end) && (mid <= right))
{
if
(numbers[left] <= numbers[mid])
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while
(left <= left_end)
temp[tmp_pos++] = numbers[left++];
while
(mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i
= 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
static
public class MergePosInfo
{
public
int left;
public
int mid;
public
int right;
}
static
public void MergeSort_Iterative(int [] numbers, int left, int right)
{
int mid;
if
(right <= left)
return;
LinkedList<MergePosInfo> list1 = new
LinkedList<MergePosInfo>();
LinkedList<MergePosInfo> list2 = new
LinkedList<MergePosInfo>();
MergePosInfo info = new MergePosInfo();
info.left = left;
info.right = right;
info.mid = -1;
list1.add(info);
while(true)
{
if(list1.size() == 0)
break;
left = list1.get(0).left;
right = list1.get(0).right;
list1.remove(0);
mid = (right + left) / 2;
if(left < right)
{
MergePosInfo info2 = new MergePosInfo();
info2.left = left;
info2.right = right;
info2.mid = mid + 1;
list2.add(info2);
info.left = left;
info.right = mid;
list1.add(info);
info.left = mid + 1;
info.right = right;
list1.add(info);
}
}
for
(int i = 0; i < list2.size(); i++)
{
DoMerge(numbers, list2.get(i).left, list2.get(i).mid,
list2.get(i).right);
}
}
public
static void main(String[] args)
{
int[]
numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };
int
len = 9;
System.out.println();
System.out.println("MergeSort
By Iterative Method");
MergeSort_Iterative(numbers, 0, len - 1);
for
(int i = 0; i < 9; i++)
System.out.println(numbers[i]);
}
}
HEAP SORT :
//Source
code for Heap Sort
public class
HeapSort
{
private static
int[] a;
private static
int n;
private static
int left;
private static
int right;
private static
int largest;
public static
void buildheap(int []a){
n=a.length-1;
for(int i=n/2;i>=0;i–){
maxheap(a,i);
}
}
public static
void maxheap(int[] a, int i){
left=2*i;
right=2*i+1;
if(left <= n && a[left] > a[i]){
largest=left;
}
else{
largest=i;
}
if(right <= n && a[right] > a[largest]){
largest=right;
}
if(largest!=i){
exchange(i,largest);
maxheap(a, largest);
}
}
public static
void exchange(int i, int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
public static
void sort(int []a0){
a=a0;
buildheap(a);
for(int i=n;i>0;i–){
exchange(0, i);
n=n-1;
maxheap(a, 0);
}
}
public static
void main(String[] args) {
int []a1={4,1,3,2,16,9,10,14,8,7};
sort(a1);
for(int i=0;i<a1.length;i++){
System.out.print(a1[i] + " ");
}
}
}
The Quick Sort
The quick sort uses divide and conquer to gain the
same advantages as the merge sort, while not using additional storage. As a
trade-off, however, it is possible that the list may not be divided in half.
When this happens, we will see that performance is diminished.
A quick sort first selects a value, which is called
the pivot value. Although there are many different ways to choose the pivot
value, we will simply use the first item in the list. The role of the pivot
value is to assist with splitting the list. The actual position where the pivot
value belongs in the final sorted list, commonly called the split point, will
be used to divide the list for subsequent calls to the quick sort.
import java.io.*;
import java.util.*;
public class QuickSort
{
public
static void swap (int A[], int x, int y)
{
int temp
= A[x];
A[x] =
A[y];
A[y] =
temp;
}
//
Reorganizes the given list so all elements less than the first are
// before
it and all greater elements are after it.
public
static int partition(int A[], int f, int l)
{
int
pivot = A[f];
while (f
< l)
{
if
(A[f] == pivot || A[l] == pivot)
{
System.out.println("Only distinct integers allowed - C321");
System.out.println("students should
ignore this if statement");
System.out.exit(0);
}
while
(A[f] < pivot) f++;
while
(A[l] > pivot) l--;
swap
(A, f, l);
}
return
f;
}
public
static void Quicksort(int A[], int f, int l)
{
if (f
>= l) return;
int
pivot_index = partition(A, f, l);
Quicksort(A, f, pivot_index);
Quicksort(A, pivot_index+1, l);
}
public
static void main(String argv[])
{
int A[]
= new int[argv.length];
for (int
i=0 ; i < argv.length ; i++)
A[i]
= Integer.parseInt(argv[i]);
Quicksort(A, 0, argv.length-1);
for (int
i=0 ; i < argv.length ; i++) System.out.print(A[i] + " ");
System.out.println();
}}
