Why Sorting ?
Sorting is used to order the elements or data in increasing or decreasing order or in lexicographical order.
More than 25% of time spent on sorting in computing .
Use Cases :
1. For searching , sorting is a kind of pre-computation done on data. So that element can be easily found.
2. Sorting is used to find duplicates in a group of elements.
i.e when you sort all the elements will be in order and duplicate elements will be next to each other and easily be found. (Duplicates will be in consecutive)
3. Matching items in two files . When you sort the two files and matching items can be easily found in single pass.
i.e This can be implemented using merge sort.
4. Median can be easily when sorted.
i.e After sorted middle element will be the median.
5. Top K minimum or maximum elements.
6. Truncated top of items that are relevant to our search.
Ex : Facebook feed , Google search , Gmail search , Twitter feed , Instagram feed , Airbnb homes search , Amazon search bar results.
Main Usage :
1. How to attack new problems .
Algorithm design strategies like Divide and Conquer and Decrease and Conquer.
2. To analyse algorithms to determine their performance. So that you can choose between two competing solutions of a problem.
Brute Force Design Strategy :
Brute Force is a simplest and straight forward design strategy based up on the problem statement.
Selection Sort :
Selection sort means iterate over the unsorted array and find the minimum element and place it in it's right position.
An algorithm efficiency is determined by it's time and space complexity.
Selection sort Algorithm :
Java Solution :
Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Java Solution : Selection Sort
class Solution {
public List<Integer> sortArray(int[] nums) {
List<Integer> sortedList = new ArrayList<>();
for(int i = 0; i < nums.length;i++){
int minimumValueIndex = i;
for(int j=i+1; j < nums.length;j++){
if(nums[j] < nums[minimumValueIndex]){
minimumValueIndex = j;
}
}
if(i != minimumValueIndex){ // To skip this loop when elements at both indexes are equal.
int temp = nums[i];
nums[i] = nums[minimumValueIndex];
nums[minimumValueIndex] = temp;
}
}
for(int i=0;i < nums.length;i++){
sortedList.add(new Integer(nums[i]));
}
return sortedList;
}
}
Time Complexity : O(n*n) because two for loops.
Space Complexity : O(n) space for LinkedList
Bubble Sort :
Java Solution : Bubble Sort
class Solution {
public List<Integer> sortArray(int[] nums) {
// Bubble Sort
// In bubble sort we will iterate from right to left and bubble up if we find any right element is less than it's left element and in each iteration minimum element will come to it's position.
// Bubble sort is a variant of brute force approach.
List<Integer> sortedList = new ArrayList<>();
int temp = 0;
for(int i = 1 ;i < nums.length;i++){
for(int j = nums.length-1; j > 0 ; j--){
if(nums[j-1] > nums[j]){
temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
}
}
}
for(int num : nums){
sortedList.add(new Integer(num));
}
return sortedList;
}
}
Time Complexity : O(n*n) n is no fo iterations . other n for number of swaps.
Space Complexity : O(n)
