# Sorting
---
title: Introduction
description: Intro to Sorting
duration: 240
card_type: cue_card
---
**Sorting** is an arrangement of data in particular order on the basis of some parameter
### Example 1:
```
A[ ] = { 2, 3, 9, 12, 17, 19 }
```
The above example is sorted in ascending order on the basis of magnitude.
### Example 2:
```
A[ ] = { 19, 6, 5, 2, -1, -19 }
```
The above example is sorted in descending order on the basis of magnitude.
---
title: Quiz 1
description:
duration: 45
card_type : quiz_card
---
# Question
Is the array { 1, 13, 9 , 6, 12 } sorted ?
# Choices
- [x] Yes
- [ ] No
---
title: Quiz 1 Explanation
description:
duration: 60
card_type : cue_card
---
In the above quiz, array is sorted in ascending order on the basis of count of factors. Count of factors for the above array is { 1, 2, 3, 4, 6 }.
---
title: Why sorting is required?
description:
duration: 60
card_type : cue_card
---
**Sorting** is essential for organizing, analyzing, searching, and presenting data efficiently and effectively in various applications and contexts.
---
title: Problem 1 Minimize the cost to empty array
description:
duration: 200
card_type: cue_card
---
Given an array of **n** integers, minimize the cost to empty given array where cost of removing an element is equal to **sum of all elements left in an array**.
### Example 1
```plaintext
A[ ] = { 2, 1, 4 }
Ans = 11
```
### Explanation
After removing 4 cost = 4+2+1 = 7
After removing 2 cost = 2+1 = 3
After removing 1 cost = 1 = 1
Total cost = 11
---
title: Quiz 2
description:
duration: 60
card_type : quiz_card
---
## Question
Minimum cost to remove all elements from array {4, 6, 1} ?
## Choices
- [ ] 11
- [ ] 15
- [x] 17
- [ ] 21
---
title: Quiz 2 Explanation
description:
duration: 60
card_type : cue_card
---
After removing 6 cost = 4+6+1 = 11
After removing 4 cost = 4+1 = 5
After removing 1 cost = 1 = 1
Total cost = 17
---
title: Quiz 3
description:
duration: 60
card_type : quiz_card
---
# Question
Minimum cost to remove all elements from array[] = {3, 5, 1, -3}
# Choices
- [ ] 4
- [x] 2
- [ ] 0
- [ ] 18
---
title: Quiz 3 Explanation
description:
duration: 60
card_type : cue_card
---
After removing 5 cost = 5+3+1+(-3) = 6
After removing 3 cost = 3+1+(-3) = 1
After removing 1 cost = 1+(-3) = -2
After removing -3 cost = -3) = -3
Total cost = 2
---
title: Problem 1 Solution Approach
description:
duration: 60
card_type : cue_card
---
### Observation
* Start removing from the largest element.
Here we can see if we have to minimise the cost we should add the largest number minimum number of times, that implies it should be the first one to be removed.
The formula would be **$\sum$(i+1)\*arr[i]** where **i** is the index.
Follow the below steps to solve the problem.
* **Sort** the data in descending order.
* Initialise the **ans** equal to 0.
* Run a loop for i from 0 to **n** – 1, where **n** is the size of the array.
* For every element add **arr[i]\*i** to the ans.
### Pseudocode
```cpp
int calculate_cost(int arr[], int n)
{
reverse_sort(arr);
int ans =0;
for (int i = 0; i < n; i++) {
ans += i*arr[i];
}
return ans;
}
```
### Time and Space Complexity
-- TC - O(nlogn)
-- SC - O(n)
---
title: Problem 2 Find count of Noble Integers
description:
duration: 60
card_type : cue_card
---
Given an array of distinct elements of size n, find the count of **noble integers**.
> Note: arr[i] is **noble** if count of elements smaller than arr[i] is equal to arr[i] where arr[i] is element at index i.
### Example 1
```plaintext
A[ ] = { 1, -5, 3, 5, -10, 4}
Ans = 3
```
### Explanation
For arr[2] there are three elements less than 3 that is 1, -5 and -10. So arr[0] is noble integer.
For arr[3] there are five elements less than 5 that is 1, 3, 4, 5, -5 and -10. So arr[3] is noble integer.
For arr[5] there are four elements less than 4 that is 1, 3, -5 and -10. So arr[5] is noble integer.
In total there are 3 noble elements.
---
title: Quiz 4
description:
duration: 60
card_type : quiz_card
---
### Question
Count the number of noble integers in the array. A = { -3, 0, 2 , 5 }
### Choices
- [ ] 0
- [x] 1
- [ ] 2
- [ ] 3
---
title: Quiz 4 Explanation
description:
duration: 60
card_type : cue_card
---
**Explanation:**
For arr[2] there are two elements less than 2 that is -3 and 0. So arr[2] is noble integer.
In total there are 2 noble elements.
---
title: Problem 2 Bruteforce Solution
description:
duration: 60
card_type : cue_card
---
### Observation
Iterate through every element in the array, for every element count the number of smaller elements.
### Pseudocode
```cpp
int find_nobel_integers(int arr[], int n)
{
int ans =0;
for (int i = 0; i < n; i++) {
int count =0;
for(int j=0;j<n;j++) {
if(arr[j]< arr[i])
count++;
}
if(count == arr[i]) {
ans++;
}
}
return ans;
}
```
### Time and Space Complexity
-- TC - O(N^2)
-- SC - O(1)
---
title: Problem 1 Optimised Solution
description:
duration: 60
card_type : cue_card
---
### Optimised Solution - 1
* Hint 1: What is the extra work being done?
Expected: For every element, we are using an extra loop for calculating the count of smaller elements.
* Hint 2: Can sorting the array help here?
### Observation:
If we sort the data all elements smaller than the element at index i will be on from index **0 to i-1**. So total number of smaller elements will be equal to **i**.
#### Pseudocode
```cpp
int find_nobel_integers(int arr[], int n)
{
sort(arr);
int ans =0;
for (int i=0; i<n; i++) {
if(arr[i] == i) {
ans = ans+1;
}
}
return ans;
}
```
### Time and Space Complexity
-- TC - O(nlogn)
-- SC - O(1)
---
title: Problem 3 Find count of nobel integers (Not Distinct)
description:
duration: 20
card_type : cue_card
---
### Problem 3
Given an array of size n, find the count of noble integers.
> Note: Same as previous question, but all elements need not to be distinct
---
title: Quiz 5
description:
duration: 60
card_type : quiz_card
---
# Question
Count the no of noble integers in the array. A = { -10, 1, 1, 3, 100 }
# Choices
- [ ] 1
- [x] 3
- [ ] 2
- [ ] 4
---
title: Quiz 5 Explanation
description:
duration: 60
card_type : cue_card
---
**Explanation:**
For arr[1] and arr[2] there is one element less than 1. So arr[1] and arr[2] are noble integers.
Similarly arr[3] will be the npble lement as there are 3 elements less than 3.
So in total 3 elements are noble integers.
---
title: Quiz 6
description:
duration: 60
card_type : quiz_card
---
# Question
Count the no of noble integers in the array
A = { -10, 1, 1, 2, 4, 4, 4, 8, 10 }
# Choices
- [ ] 4
- [x] 5
- [ ] 6
- [ ] 7
---
title: Quiz 6 Explanation
description:
duration: 60
card_type : cue_card
---
**Explanation:**
arr[1], arr[2], arr[4], arr[5], arr[6] are the noble elements here.
---
title: Quiz 7
description:
duration: 60
card_type : quiz_card
---
# Question
Count the no of noble integers in the array
A = { -3, 0, 2, 2, 5, 5, 5, 5, 8, 8, 10, 10, 10, 14 }
# Choices
- [ ] 4
- [ ] 5
- [ ] 6
- [x] 7
---
title: Quiz 7 Explanation
description:
duration: 60
card_type : cue_card
---
**Explanation:**
For arr[8] and arr[9] there are eight elements less than 8 that is -3, 0, 2, 5. So arr[8] and arr[9] are noble integers.
Similarly arr[9], arr[10], arr[11], ar[12] are noble elements.
So in total 6 elements are noble integers.
---
title: Problem 3 Solution
description:
duration: 500
card_type : cue_card
---
### Observation
* If the current element is same as previous element then the total number of smaller elements will be same as previous element.
* If current element is not equal to previous element then the total number of smaller elements is equal to its index.
### Pseudocode
```cpp
int find_nobel_integers(int arr[], int n)
{
sort(arr);
int count = 0, ans=0;
if(arr[0] == 0) ans++;
for (int i = 1; i < n; i++) {
if(arr[i] != arr[i-1])
count = i;
if(count == arr[i])
ans++;
}
return ans;
}
```
### Time and Space Complexity
-- TC - O(nlogn)
-- SC - O(1)
---
title: Question (Sort by swapping adjacent values)
description: Bubble Sort
duration: 900
card_type: cue_card
---
# Bubble Sort
* Sorting is done by **swapping adjacent values**.
## Question 1
*Given an array a[N], sort ar[] in increasing order only by swapping adjacent values.*
### Example
- Given array, ar[9] = {8, 2, 4, -1, 6, 7, 5, 10, -1}
* Iteration 1: {8, 2, 4, -1, 6, 7, 5, 10, -1}
* Compare 8 and 2: Swap since 8 > 2. Array becomes (2, 8, 4, -1, 6, 7, 5, 10, -1)
* Compare 8 and 4: Swap since 8 > 4. Array becomes (2, 4, 8, -1, 6, 7, 5, 10, -1)
* Compare 8 and -1: Swap since 8 > -1. Array becomes (2, 4, -1, 8, 6, 7, 5, 10, -1)
* Compare 8 and 6: Swap since 8 > 6. Array becomes (2, 4, -1, 6, 8, 7, 5, 10, -1)
* Compare 8 and 7: Swap since 8 > 7. Array becomes (2, 4, -1, 6, 7, 8, 5, 10, -1)
* Compare 8 and 5: Swap since 8 > 5. Array becomes (2, 4, -1, 6, 7, 5, 8, 10, -1)
* Compare 8 and 10: No swap as 8 < 10. Array remains (2, 4, -1, 6, 7, 5, 8, 10, -1)
* Compare 10 and -1: Swap since 10 > -1. Array becomes (2, 4, -1, 6, 7, 5, 8, -1, 10)
*Here we see the greatest element has come in it's correct position.*
Similarly all the iterations are done:
* Iteration 2 : {2, -1, 4, 6, 5, 7, -1, 8, 10}
*After two iterations, two greatest elements are at the correct positions*
* Iteration 3 : {-1, 2, 4, 5, 6, -1, 7, 8, 10}
**Observation:** Repeat above iterations N times, entire ar[] will be sorted in increasing order.
### Pseudocode
```java
void bubbleSort (int ar[]){
int N = ar.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
if (ar[j] > ar[j + 1]) {
int temp = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = temp;
}
}
}
}
```
**Why inner loop is running till N - 1?**
If j = N - 1, ar[j] > ar[j + 1] => ar[N - 1] > ar[N]. Due to ar[N], we will get index out of bounds error.
#### Dry Run
Sort array, ar[5] = {3, 1, 6, 10, 8} using bubble sort.
- Iteration 1: ar[5] = {1, 3, 6, 8, 10}, swaps = 2
- Iteration 2: ar[5] = {1, 3, 6, 8, 10}, swaps = 0
**Observation**: *If in a full iteration, there are no swaps, then the data is already sorted.*
**Optimized Solution:**
- Use a variable swap for every iteration, initialized with zero. It will keep track of number of swaps done in that iteration.
- In case, the number of swaps are zero for a iteration, we can early exit as the code is already sorted.
```java
void bubbleSort (int ar[]){
int N = ar.length;
for (int i = 0; i < N; i++) {
int swap = 0;
for (int j = 0; j < N - 1; j++) {
if (ar[j] > ar[j + 1]) {
// swap ar[j] and ar[j + 1]
swap++;
}
}
if (swap == 0) {
// data is sorted
break;
}
}
}
```
* **Time Complexity :** $O(N^2)$
As we are using two nested loops, which can yield $O(N^2)$ time in the worst case.
* **Space Complexity :** O(1)
As we are not using any additional space.
---
title: Quiz 8
description:
duration: 40
card_type: quiz_card
---
# Question
In Bubble Sort, which elements are compared and swapped?
# Choices
- [ ] Random elements
- [ ] Elements at even indices
- [x] Adjacent elements
- [ ] Elements with the maximum difference
---
title: Quiz 9
description:
duration: 40
card_type: quiz_card
---
# Question
In a bubble sort, after one pass through the array, where is the largest element guaranteed to be?
# Choices
- [ ] At the beginning of the array
- [x] At the end of the array
- [ ] In the middle of the array
- [ ] It depends on the initial arrangement of elements
---
title: Sorting Algorithm - Insertion Sort
description:
duration: 500
card_type : cue_card
---
**Insertion Sort** is one of the simplest sorting techniques which you might have used in your daily lives while arranging a deck of cards.
> So without going into how this algorithm works, let’s think about how you would usually go about arranging the deck of cards?
**Say you are given 10 cards, 1 to 10 of spades, all shuffled, and you want to sort these cards.**
1. You would basically pick any random card(e.g. 7), and place it into your left hand, assuming the left hand is meant to carry the sorted cards.
2. Then you would pick another random card, say 2, and place 2 in the correct position on your left hand, i.e. before 7.
3. Then again if you pick 5, you would place it between 2 and 7 on your left hand, and this way we know we are able to sort our deck of cards. Since we insert one element at a time in its correct position, hence its name “Insertion Sort”.
### Dry Run
E.g. if elements were in order:
```3, 5, 2```
You can start by picking 3, and since there is no element to the left of 3, we can assume it is in the correct place.
Array:
```3, 5, 2```
You can pick 5, you compare 5 with 3, and you find 5 is in the correct order amongst the array of [3, 5].
Array:
```3, 5, 2```
Then you pick 2, you find the place in the left side array of [3,5] to place this 2. Since 2 must come before 3, we insert 2 before 3.
Array:
```2, 3, 5 →```
Which is a sorted order.
### Approach
Line 2: We don’t process the first element, as it has nothing to compare against.
Line 3: Loop from i=1 till the end, to process each element.
Line 4: Extract the element at position i i.e. array[i]. Let it be called E.
Line 5: To compare E with its left elements, loop j from i-1 to 0
Line 6, 7: Compare E with the left element, if E is lesser, then move array[j] to right by 1.
Line 8: Once we have found the position for E, place it there.
### Pseudocode
```cpp=
void insertionSort(int arr[], int n){
for (int i = 1; i < n; i++){ // Start from 1 as arr[0] is always sorted
Int currentElement = arr[i];
Int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement){
arr[j + 1] = arr[j];
j = j - 1;
}
// Finally place the Current element at its correct position.
arr[j + 1] = currentElement;
}
}
```
### TC & SC
**Time Complexity:**
**Worst Case:** O(N^2), when the array is sorted in reverse order.
**Best Case:** O(N), when the data is already sorted in desied order, in that case there will be no swap.
Space Complexity: O(1)
## Note
1. Both Selection & Insertion are in-place sorting algorithms, means they don't need extra space.
2. Since the time complexity of both can go to O(N^2), it is only useful when we have a lesser number of elements to sort in an array.
---
title: Motivation for attending Bit Manipulation
description:
duration: 900
card_type: cue_card
---
Bit manipulation is crucial in the world of computer science and programming! It's all about working directly with individual bits within binary data representations. Let's dive into why bit manipulation matters:
**Memory and Space Efficiency:** Computers use binary (0s and 1s) to store data. Tweaking these bits can lead to smaller data representations, saving precious memory and storage space. This is especially vital in resource-limited environments like mobile devices and embedded systems.
**Performance Boost:** Bit manipulation speeds up algorithms. Many hardware-level operations rely on bits, and using these directly in your code optimizes execution. This means faster results without costly higher-level processes.
**Data Compression and Encryption:** Tricks with bits are essential in data compression and encryption. Algorithms cleverly manipulate bits to represent data efficiently. Think of Huffman coding, where frequently used characters get shorter bit representations.
**Masking and Flags:** You can use individual bits for flags and settings. By toying with these bits, you can set, clear, toggle, or check settings without complex conditions. Simple yet powerful!
**Logic and Algorithm Design:** Fancy algorithms often rely on bit manipulations. Think `AND, OR, XOR, and NOT` operations directly on bits. This leads to slick and efficient solutions in various scenarios.
**Puzzles and Challenges:** Bit manipulation is a gem in programming puzzles and competitions. Mastering this skill helps you breeze through challenges like a champ!
To wrap it up, bit manipulation offers a nifty, efficient way to play with binary data. It shines in programming, optimization, data magic, and hardware interactions. While not needed in every task, understanding bit manipulation turbocharges your problem-solving and coding skills.
Sign in with Wallet
Connect another wallet