Selection Sort

What is Selection Sort?

Selection sort is a sorting method that finds the smallest element in an unsorted region of an array and places it at the beginning of the array. In the provided array, the method keeps two subarrays:

• The subarray that has previously been sorted
• The remaining unsorted subarray

Algorithm:

Algorithm for Selection Sort:

1. Find the minimum element in the unsorted part of the array.
2. Swap the minimum element with the first element in the unsorted part of the array.
3. Move the boundary of the sorted part of the array one element to the right.
4. Repeat steps 1-3 until the entire array is sorted.

Time Complexity:

• Worst Case: O(n^2)
• Best Case: Ω(n^2)
• Average Case: Θ(n^2)

Implementation of the algorithm in Java:

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Problems based on Selection Sort:

• Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. Return any array that satisfies this condition.

Example:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Solution:

class Solution {
    public static int[] sortArrayByParity(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (nums[j] % 2 == 0 && nums[j] < nums[minIndex] || nums[minIndex] % 2 != 0) {
                minIndex = j;
            }
        }
        // swap nums[i] and nums[minIndex]
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
    return nums;
}

}

• The outer loop begins with the first member of the array and progresses to the array’s second-to-last element.
• The inner loop begins with the next member of the outer loop and progresses until the array’s last element.
• We find the minimum even number between the current element and the end of the array.
• If a smaller even or odd integer is located, update the minimum element’s index.
• Following the completion of the inner loop, exchange the current element with the smallest even element (if there is one).
• As a result, all even integers are moved to the beginning of the array, followed by all odd integers.

• Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.

Example:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Solution:

class Solution {
    public String frequencySort(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    
    int[] freq = new int[256]; // ASCII has 256 characters
    for (char c : s.toCharArray()) {
        freq[c]++;
    }
    
    char[] sorted = new char[s.length()];
    int idx = 0;
    while (idx < s.length()) {
        char maxChar = 0;
        int maxFreq = 0;
        for (int i = 0; i < 256; i++) {
            if (freq[i] > maxFreq) {
                maxFreq = freq[i];
                maxChar = (char) i;
            }
        }
        while (maxFreq > 0) {
            sorted[idx++] = maxChar;
            maxFreq--;
        }
        freq[maxChar] = 0;
    }
    
    return new String(sorted);
}

}

• Using an integer array freq, the first step is to count the frequency of each character in the input string s.
• It then loops over the array freq to find the character with the highest frequency and adds it to a new sorted character array.
• This method is continued until all characters in sorted have been inserted. Then generate a string from the sorted character array.

Note: also read about Bubble Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py