Nth Highest salary of the employee, this is general question. I am giving answer my own style.
select * from employee e1 where n-1 = (select count(distinct(emp2.salary)) from employee 2 where
e2.salary > e1.salary);
Employee Table:
id salaray
1 5
2 4
3 3
Nest query means query contain another query, nothing
e1 - for loop
e2 - nested for loop
1st pass:
e2.salary > e1.salary
5 > 5 NO
4 > 5 NO
3 > 5 NO
2nd Pass:
e2.salary > e1.salary
5 > 4 Yes - This will match
Internally All sql queries using algorithms, I am not remember exactly either merge sort or bubble sor t or selection sort they are using internally.
I want to highlight here is the bubble sort - it's matching above criteria.
Bubble Sort:
Main logic:
for(int i=0; i < n; i++) {
for(j=1; j < n-i; j++) {
if(a[j-1] > a[j] ) {
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
The nested loop why it's using j < n-i , I will give answer
2 3 4 5 1 - Unsorted
1st Pass: i = 0, j < 5
2 3 4 5 1 - 2 < 3 ok
2 3 4 5 1 - 3 < 4 ok
2 3 4 5 1 - 4 < 5 ok
2 3 4 5 1 - 5 > 1 swap
2 3 4 1 5
After 1st pass is over, you have filter highest element 5 in the last.
2nd Pass: i = 1; j < 4
in the 2nd pass observer here j < 4 means in the 1st pass we had already filtered highest element 5.
2 3 4 1 5 - 2 < 3 ok
2 3 4 1 5 - 3 < 4 ok
2 3 4 1 5 - 4 < 1 swap
2 3 1 4 5 -
In the 2nd pass we had filtered 2nd highest element 4 in the last .
like this way it will perform.
Above nested sql query similar to the bubble sort.
Wrost case: O(n2), Average Case: O(n2).
Now we will see selection sort:
1) First find the smallest element in the list and put it in the first position. Then find the second smallest element in the list and put it in the second position and so on..
otherwise
First find the highest element in the list and put it in the last position. Then find the second highest element in the list and put in the second last position and so on.
I am showing 2 examples
Approach Find Smallest Element:
selectionSort(int[] arr) {
int i, j,minIndex,temp;
int n = arr.length;
for (i =0; i < n - 1; i++ ) {
minIndex = i;
minValue = arr[i]
for( j = i+1; j < n ; j++ ) {
if( arr[j] < minValue ) {
minIndex = j;
minValue = arr[minIndex]
}
}
//once inner loop over, we will find the smallest element then swap
if(minIndex ! = i ) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
In this approach 1st we fill find the smallest element put it in the first position.
Example:
Unsorted Array: 2 3 4 5 1
1st Pass; i = 0, minValue=2, minIndex = 0, j = 1
2 3 4 5 1 ; j=1, 3 > 2 then minIndex = 0, minValue = 2
j=2 , 4 > 2 then minIndex = 0, minValue = 2
j=3 , 5 > 2 then minIndex = 0, minValue = 2
j=4, 1 > 2 then minIndex = 4, minValue = 1
Once first pass will be over check whether minIndex != i and then swap
i=0, minIndex=4
Now swap with a[i] with a[minIndex], first position "2" swap with "1"
In this after 1st pass we had filter minValue put it in the first position,
After the 1st pass:
1 3 4 5 2
for( j = i+1; j < n ; j++ ) {,
Then for 2nd smallest element, here observer here starting with j = i+1 , means we already done 1st place, now in the 2nd pass identify i = 1, j = 3 , from 2nd to Nth
2nd Pass; i = 1, minValue=3, minIndex = 1, j = 2
1 3 4 5 2 ; j=2, 4 > 3 then minIndex = 1, minValue = 3
j=3 , 5 > 3 then minIndex = 1, minValue = 3
j=4 , 2 > 3 then minIndex = 4, minValue = 2
After 2nd Pass identified 2nd minimum value, then put in 2nd position
After 2nd Pass
1 2 4 5 3
What I am trying to say means in selection sort also after every pass we will filter min value like this.
In the inner loops,
filter highest value put it in the last means for(j=1; j < n-i; j++)
filter smallest value in the first like selection then for( j = i+1; j < n ; j++ )
select * from employee e1 where n-1 = (select count(distinct(emp2.salary)) from employee 2 where
e2.salary > e1.salary);
Employee Table:
id salaray
1 5
2 4
3 3
Nest query means query contain another query, nothing
e1 - for loop
e2 - nested for loop
1st pass:
e2.salary > e1.salary
5 > 5 NO
4 > 5 NO
3 > 5 NO
2nd Pass:
e2.salary > e1.salary
5 > 4 Yes - This will match
Internally All sql queries using algorithms, I am not remember exactly either merge sort or bubble sor t or selection sort they are using internally.
I want to highlight here is the bubble sort - it's matching above criteria.
Bubble Sort:
Main logic:
for(int i=0; i < n; i++) {
for(j=1; j < n-i; j++) {
if(a[j-1] > a[j] ) {
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
The nested loop why it's using j < n-i , I will give answer
2 3 4 5 1 - Unsorted
1st Pass: i = 0, j < 5
2 3 4 5 1 - 2 < 3 ok
2 3 4 5 1 - 3 < 4 ok
2 3 4 5 1 - 4 < 5 ok
2 3 4 5 1 - 5 > 1 swap
2 3 4 1 5
After 1st pass is over, you have filter highest element 5 in the last.
2nd Pass: i = 1; j < 4
in the 2nd pass observer here j < 4 means in the 1st pass we had already filtered highest element 5.
2 3 4 1 5 - 2 < 3 ok
2 3 4 1 5 - 3 < 4 ok
2 3 4 1 5 - 4 < 1 swap
2 3 1 4 5 -
In the 2nd pass we had filtered 2nd highest element 4 in the last .
like this way it will perform.
Above nested sql query similar to the bubble sort.
Wrost case: O(n2), Average Case: O(n2).
Now we will see selection sort:
1) First find the smallest element in the list and put it in the first position. Then find the second smallest element in the list and put it in the second position and so on..
otherwise
First find the highest element in the list and put it in the last position. Then find the second highest element in the list and put in the second last position and so on.
I am showing 2 examples
Approach Find Smallest Element:
selectionSort(int[] arr) {
int i, j,minIndex,temp;
int n = arr.length;
for (i =0; i < n - 1; i++ ) {
minIndex = i;
minValue = arr[i]
for( j = i+1; j < n ; j++ ) {
if( arr[j] < minValue ) {
minIndex = j;
minValue = arr[minIndex]
}
}
//once inner loop over, we will find the smallest element then swap
if(minIndex ! = i ) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
In this approach 1st we fill find the smallest element put it in the first position.
Example:
Unsorted Array: 2 3 4 5 1
1st Pass; i = 0, minValue=2, minIndex = 0, j = 1
2 3 4 5 1 ; j=1, 3 > 2 then minIndex = 0, minValue = 2
j=2 , 4 > 2 then minIndex = 0, minValue = 2
j=3 , 5 > 2 then minIndex = 0, minValue = 2
j=4, 1 > 2 then minIndex = 4, minValue = 1
Once first pass will be over check whether minIndex != i and then swap
i=0, minIndex=4
Now swap with a[i] with a[minIndex], first position "2" swap with "1"
In this after 1st pass we had filter minValue put it in the first position,
After the 1st pass:
1 3 4 5 2
for( j = i+1; j < n ; j++ ) {,
Then for 2nd smallest element, here observer here starting with j = i+1 , means we already done 1st place, now in the 2nd pass identify i = 1, j = 3 , from 2nd to Nth
2nd Pass; i = 1, minValue=3, minIndex = 1, j = 2
1 3 4 5 2 ; j=2, 4 > 3 then minIndex = 1, minValue = 3
j=3 , 5 > 3 then minIndex = 1, minValue = 3
j=4 , 2 > 3 then minIndex = 4, minValue = 2
After 2nd Pass identified 2nd minimum value, then put in 2nd position
After 2nd Pass
1 2 4 5 3
What I am trying to say means in selection sort also after every pass we will filter min value like this.
In the inner loops,
filter highest value put it in the last means for(j=1; j < n-i; j++)
filter smallest value in the first like selection then for( j = i+1; j < n ; j++ )
