Selection Sort with Implementation In Java

  • In-place algorithm
  • Time complexity : O(n2)  - Quadratic
  • Unstable Algorithm



import java.util.Arrays;

public class SelectionSortImpl {

    public static int[] sort(int arr[]) {

        for (int lastUnsortedIndex= arr.length-1; lastUnsortedIndex >0; lastUnsortedIndex--) {

            int maxIndex = 0;

            for (int i = 1; i <=lastUnsortedIndex ; i++) {
                if (arr[i] > arr[maxIndex])
                    maxIndex = i;
            }
            swap(arr, maxIndex, lastUnsortedIndex);
        }
        return arr;
    }

    private static void swap(int[] arr, int i, int j) {

        if (i == j) return;

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int arr1[] = {20,35,-15, 7,55,1,-22};
        System.out.println(Arrays.toString(sort(arr1)));
    }
}

Comments

Post a Comment

Popular posts from this blog

Sliding Window Maximum (Maximum of all subarrays of size k) - Java Solution - Leetcode 239

Image
Solution approach : We will be using sliding window. Deque will be used to store useful element of current subarray. Add first element to deque. Then for adding next element, check if earlier elements are smaller, then remove all elements from deque. Maximum will always be at front of deque. For sliding and removing, check if arr[i] == front of queue, then remove the element. import java.util.Arrays ; import java.util.Deque ; import java.util.LinkedList ; public class MaxOfAllSubarrays { private static int [] findMaxOfAllSubArrays ( int [] arr , int subArraySize) { int [] answerArr = new int [arr. length - subArraySize + 1 ] ; int i = 0 , j = 0 , count = 0 ; Deque<Integer> deque = new LinkedList<>() ; while (j < arr. length ) { while (!deque.isEmpty() && deque.getLast() < arr[j]) deque.removeLast() ; deque.add(arr[j]) ; if (j - i + 1 == subArraySize) { answe...
Read more

Count occurrence of anagrams in String

Image
We would be solving this problem using  Sliding Window approach with 1 Hashmap First we will populate pattern map with occurrence of chars in pattern map. Additionally, a new indicator distinctCharsInMapValueMoreThanZero will be created. It's initial value would be map.size(). This variable is for numbers of chars in map with value > 0. This will ensure we don't have to compare all values of map to see, if all characters are zero or not. When variable  distinctCharsInMapValueMoreThanZero is zero, it means current substring is anagram of pattern.  When traversing string via Sliding window, we will keep reduce count of character in pattern map. In map, we will not push any char, which are not part of pattern.
Read more
 Shell Sort Implementation program in Java https://github.com/cbsingh1/DailyCodingProblems/blob/main/src/main/java/com/cbsingh/sorting/ShellSortImpl.java
Read more