Sort Integers(lintcode 463)

Description

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.

Example

Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].

Interface

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers(int[] A) {
        // Write your code here
    }
}

Solution

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */

    //Selection Sort
    public void sortIntegers(int[] A) {
        // Write your code here
        for (int i = 0; i < A.length - 1; ++i) {
            int minIndex = i;
            for (int j = i + 1; j < A.length; ++j) {
                if (A[j] < A[minIndex]) {
                    minIndex = j;
                }
            }

            swap(A, i, minIndex);
        }
    }


    //Insertion Sort
    public void sortIntegers(int[] A) {
        // Write your code here
        for (int i = 1; i < A.length; ++i) {
            int j = i;
            while (j > 0 && A[j] < A[j - 1]) {
                swap(A, j, j - 1);
                --j;
            }
        }
    }


    //Bubble Sort
    public void sortIntegers(int[] A) {
        // Write your code here
        for (int i = 0; i < A.length - 1; ++i) {
            for (int j = 0; j < A.length - 1 - i; ++j) {
                if (A[j] > A[j + 1]) {
                    swap(A, j, j + 1);
                }
            }
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}