6 TYPE OF SORTING

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();

   }}