Scientific Programming II

Supplemental Instruction

Sorting Algorithms

Selection Sort

(Adapted from Virginia Tech)

The selection sort is a sorting algorithm that keeps track of the location of the beginning of the unsorted section of a collection. For example, this idea could be represented as follows:

As you can see, the lowest indices are sorted while the marker (the solid line) marks the beginning of the unsorted section of the array. Here are the basic steps of a selection sort:

1. Get a list of unsorted numbers
2. Set a marker for the unsorted section at the front of the list
3. Repeat steps 4 - 6 until one number remains in the unsorted section
4.   Compare all unsorted numbers in order to select the smallest one
5.   Swap this number with the first number in the unsorted section
6.   Advance the marker to the right one position
7. Stop

Or, in code:

package edu.govschool;

import java.util.Scanner;

public class SelectionSort
{
    public static void selectSort(int[] a)
    {
        int pass = 0;
        for (int i = 0; i < a.length - 1; i++) {
            int smallest = a[i];
            int smIndex = i;
            pass++;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < smallest) {
                    smallest = a[j];
                    smIndex = j;
                }
            }
            if (smallest != a[i]) {
                int temp = a[i];
                a[i] = smallest;
                a[smIndex] = temp;
            }
 
            System.out.println("\nAfter Pass #" + pass + ": ");    
 
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[j] + "  ");
            }

            System.out.println("\n");
        }
        System.out.println("Total Number of Passes = " + pass);    
    }
 
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Input the size of the array");
        int size = scanner.nextInt();
        int a[] = new int [size];
 
        for (int i = 0; i < a.length; i++) {
            System.out.println("Enter Value #" + (i+1) + ":");
            a[i] = scanner.nextInt();
        }    

        System.out.println("\nInitial Array: ");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "  ");
        }
        System.out.println("\n");
 
        selectSort(a);
    }
}

Bubble Sort

According to Wikipedia:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list.

In code:

package edu.govschool;

import java.util.Scanner;

public class BubbleSort
{
    public static void bubbleSort(int[] a)
    {
        boolean flag = true;
        int pass = 0;
 
        while (flag) {
            if (pass == (a.length - 1)) {
                flag = false;
            } else {
                pass++;
                flag = false;
                for (int i = 0; i < (a.length - pass); i++) {
                    if (a[i] > a[i+1]) {
                        int temp = a[i];
                        a[i] = a[i+1];
                        a[i+1] = temp;
                        flag = true;
                    }
                }
                System.out.println("\nAfter Pass #" + pass + ": ");    
 
                for (int i = 0; i < a.length; i++) {
                    System.out.print(a[i] + " ");
                }
                System.out.println("\n");
            }
        }
        System.out.println("Total Number of Passes = " + pass);    
    }

    public static void main(String[] args)
    {
        System.out.println("Bubble Sort");
        Scanner scanner = new Scanner(System.in);
        System.out.println("Input the size of the array");
        int size = scanner.nextInt();
        int[] a = new int[size];
 
        for (int i = 0; i < a.length; i++) {
            System.out.println("Enter Value #" + (i+1) + ":");
            a[i] = scanner.nextInt();
        }

        System.out.println("\nInitial Array: ");        
        for (int i = 0; i < a.length; i++) {
            System.out.print (a[i] + " ");
        }
        System.out.println("\n");
 
        bubbleSort(a);
    }
}