Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning of an array.

How Selection Sorting Works

/*

 * Created by Ali on 8/31/2016. 

 * Selection Sort 

 */

public class SelectionSort {

    public static void main(String str[]){

        int[] arr = new int[]{10,54,2,100,200,121,99,150,51,181};
        SelectionSort obj = new SelectionSort();
        int[] sortedArray = obj.selectionSort(arr);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i] + " ");
        }
    }

    private int[] selectionSort(int[] unsortedArray) {
        int minIndex=0, temp=0;
        for(int i=0;i<unsortedArray.length;i++){
            minIndex = i;
            for(int j=i+1; j<unsortedArray.length; j++){
                if(unsortedArray[j] < unsortedArray[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex != i){
                temp = unsortedArray[minIndex];
                unsortedArray[minIndex] = unsortedArray[i];
                unsortedArray[i] = temp;
            }
        }
        return unsortedArray;
    }
}

Time Complexity: O(n*n) as there are two nested loops.

Auxiliary Space: O(1)

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Binary Search

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

A simple approach is to do linear search, i.e., start from the leftmost element of arr[] and one by one compare x with each element of arr[], if x matches with an element, return the index. If x doesn’t match with any of elements, return -1.
The time complexity in linear search is O(n).

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Logn).

/**
 * Given a sorted array arr[] of n elements, write a function to search a given element n in arr[]
 */
public class BinarySearch {

    public static void main(String a[]){

        int[] arr = new int[]{2,5,6,9,10,54,100,121,150,181};
        BinarySearch obj = new BinarySearch();
        System.out.println(obj.binarySearchRecursive(arr,0,arr.length,150));
        System.out.println(obj.binarySearchIterative(arr,121));
    }

    private int binarySearchIterative(int[] arr, int n) {
        int l=0, r = arr.length;
        int mid=0;
        while(l <= r){
            mid = l + (r - l)/2;
            if(n == arr[mid]){
                return mid;
            }else if(n > arr[mid]){
                l = mid + 1;
            }else if(n < arr[mid]){
                r = mid - 1;
            }
        }
        return -1;
    }

    private int binarySearchRecursive(int[] arr, int l, int r, int n) {
        if(r >= l){
            int mid = l + (r - l)/2;
            if(arr[mid] == n){
                return mid;
            }else if(arr[mid] < n){
                return binarySearchRecursive(arr,mid+1,r,n);
            }else if(arr[mid] > n){
                return binarySearchRecursive(arr,l,mid-1,n);
            }
        }
        return -1;
    }
}