Use this page for sharing your knowledge on week -3 Topics
- Comment
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
Lets share our knowledge and remain wise
Use this page for sharing your knowledge on week -3 Topics
Expertvision 
Good day all,
What will be the time complexity , O(n), when we want sort a list ,which is already sorted, in the reversed order using Bubble Sort algorithm?
Good day Otamurod
I believe the complexity would be O(n^2) and it will perfom the whole sorting process (it is the worst case).
Yes. You are right. Thanks for your response.
For the best case when the list is sorted in ascending order it is O(n). I believe that when it is in reverse order (descending) it will be the worst case with O(n^2)
Yes, this is exactly same with the process of sorting unordered list.
It is the worst case, and time complexity will be O(n^2). In this case your first element (f) of a list must be at the last position (n), but to make it happen a program will compare the first element with the next one and swap these elements until the first element gets to the last position. Then you need to sort (n-1) elements because you know that one of them is in appropriate position. Then just repeat these two actions.
That’s true. The time complexity is O(n^2).
I guess if it is sorted in descending order, the complexity is in worst case, i.e. O(n^2)
Yes, it will be O(n^2).
It looks like that if you are given a sorted array in ascending order, then you must sort it in descending order. Or if you are given a sorted array in descending order, then you should perform the process above oppositevly.
Hello! A reverse order can’t be considered as an equally ordered list. For example, we can sort the list in descending and increasing order, and these are two distinct ordering ways.Thus, if we traverse the descending list in order to re-organize it into the increasing order, we will still have to do the n^2 number of operations. (Moreover, it would be the worst case)
Hello Yasmina. Yes you are right. Thanks for your reply.
O(n) is the best-case running time for bubble sort. It is possible to modify bubble sort to keep track of the number of swaps it performs. If an array is already in sorted order, and bubble sort makes no swaps, the algorithm can terminate after one pass.
Hi Javokhirbek,
Here what I wanted to say is that it depends on the task which you are required to do. I mean that if you are given a sorted array in ascending order, then your task is sorting the data in descending order. Or if you are given a sorted array in descending order, then you should do the process in opposite direction. In that case, the time complexity is O(n^2).
Morever, if you must sort a list in increasing order and you have a list that is in ascending order, then you are lucky. The time complexity of your algorithm is O(n) in this way.
Thank you for your reply
What could be the exact definition for the application of Master’s Theorem to forms of Recurrences as an example in scenarios of “Subtraction” and “Division”?
Hello dear Anvar,
The master theorem can be applied to dividing functions.
Dividing functions can be defined as
T(n) = T(n/2) + c, T(n)=2T(n/2)+logn, etc.
The general form for the dividing functions :
T(n) = aT(n/b) + f(n), where a and b are constants. a≥1, b>1 and f(n) can be expressed as O(n^k * (logn)^p).
a = Number of subproblems and
b = The cost of dividing and merging the subproblems.
To find the time complexity for these kinds of functions there are 3 cases. Here we have to find two things
1. loga base b and
2. k
For simplicity, let’s take loga base b as x for all below cases.
Case : 1
If k -1 then T(n) = O(f(n)*logn)
2. If p = -1 then T(n) = O(n^k*log(logn))
3. If p x then T(n) = O(f(n)).
I hope I could give you proper answer for your question.
Hello dear Anvar,
Master theorem for Dividing functions :
Dividing functions can be defined as
T(n) = T(n/2) + c, T(n)=2T(n/2)+logn, etc.
The general form for the dividing functions :
T(n) = aT(n/b) + f(n), where a and b are constants. a≥1, b>1 and f(n) can be expressed as O(n^k * (logn)^p).
a = Number of subproblems and
b = The cost of dividing and merging the subproblems.
To find the time complexity for these kinds of functions again there are 3 cases. Here we have to find two things
1. loga base b and
2. k
For simplicity, let’s take loga base b as x for all below cases.
Case : 1
If k -1 then T(n) = O(f(n)*logn)
2. If p = -1 then T(n) = O(n^k*log(logn))
3. If p x then T(n) = O(f(n)).
I hope I could give you proper answer for your question
Hello Professor,
I have tried to implement the algorithm for selection sort in C++.I got wrong output.
When I tried to debug the code I have understood that the initial value for j loop should be i where i is the outer loop but in the video lecture it was 1 and it led to incorrect output. Could you please check the code I am attaching and tell me which one is correct?
Also I really think that5 initial value for j has to be i beacuse as we iterate through array the number of elements we have to compare with smallest reduce by 1 in each iteration.However, in the algorithm you showed j always iterates through entire array.
Here is my source code in C++:
#include
#include
using namespace std;
int main()
{
int temp, small, loc, i, j;
int a[6] = {14,89,75,23,45,105};
cout << "Before sorting:" << endl;
for (int b = 0; b < 6; b++){
cout << a[b] << "\n";
}
cout << endl;
for (i = 1; i <= 5; i++){
small = a[i – 1];
loc = i – 1;
//Note that here I canged initial value of j from 1 to i
for (j = i; j <= 5; j++){
if (a[j] < small){
small = a[j];
loc = j;
}
}
if (loc != i – 1){
temp = a[i – 1];
a[i – 1] = a[loc];
a[loc] = temp;
}
}
cout << "After sorting:" << endl;
for (int k = 0; k < 6; k++){
cout << a[k] << endl;
}
system("pause");
return 0;
}
Cool. I also implemented it but in Java. And you right in the inner loop there value of j should be set to i otherwise the complexity would be n^2 not n(n-1)/2.
n(n-1)/2 is actually equal to n^2. If you open the brackets you get (n^2-n)/2.Which denotes as O(n^2) because we only take the highest order of n.
I assume there was a typo in the slides. You see, if in the loop j=1, then when i=2 the small will be 89 with location 1. Thus, in the second loop the j starts with 1, so, it will compare 89 to 89. Here the error has started in the algorithm. So, I believe you are right.
Good evening Javokhirbek,
I see you are absolutely right. There was a minor mistake which you said. However, if you see a slide (using video) which contains a pseudocode for the selection algorithm, you will obviously see the correct statement there.
Take care.
What is the main disadvantage of selection sort? And can we work with this algorithm when we use a large number of items in a list?
Hello Iroda,
It is a good question.
I can say that the primary disadvantage of the selection sort is its poor efficiency when dealing with a huge list of items. The selection sort requires n^2 number of steps for sorting n elements. Additionally, its performance is easily influenced by the initial ordering of the items before the sorting process. Because of this, the selection sort is only suitable for a list of few elements that are in random order.
Hence, we cannot work with this algorithm when we use a large number of items in a list.
I hope you are satisfied with the answer.
Basically this sort requires n^2 steps to sort n elements. Also its performance depends on ordering items before sorting. Therefore, this kind of sorting is good list of few elements
The Selection Sort has both Advantages and Disadvantages of which are followings
1) – The main advantage of the Selection Sort is that it performs well on a small list.
2) – The primary disadvantage of the Selection Sort is its poor efficiency when dealing with a huge list of items.
-_- Simultaneously, similar to the bubble sort, the Selection Sort requires n-squared number of steps for sorting n elements.
-_- It shows that using Large number of List Items is not proper and not valid.
Hi Iroda. The main disadvantage of selection sort is that it’s not so efficient when working with big number of elements, because it uses in-place algorithm.
If O(n^2) is the running time for both selection and bubble sort can we still choose a better one?
Why bubble sorting is inefficient when there is a big amount of data comparing with other methods of sorting?
I think the main disadvantage of the bubble sort method is the time it requires. With a running time of O(n^2), it is highly inefficient for large data sets while in selection sort, the sorted and unsorted array doesn’t make any difference and consumes an order of n2 (O(n2)) in both best and worst case complexity. So, in that case, Selection sort is faster than Bubble sort.
Hello! Bubble sort is inefficient because of a huge number of swaps even in the middle-cases. For example, you’d still have to complete a number of swaps even if the first n-1 elements of the array are sorted, but the last element should be moved forward. That is why bubble sort is almost never used in any big project.
Answer:
Because the bubble sort has running time as worst case ->O(n^2) and when we compare big amount of date it will be inefficient. It depends on n^2.
Which sort is more efficient to sort ascending and descending order?
One of the most useful and efficient sort is the “Insertion” sort which has outstanding contribution to sort lists as ascending and descending order despite it is not for large arrays.
Quicksort is the good option. It is generally considered as the best sorting algorithm.
What sorting method do we use when array is constantly updated?
Hi Elina)
We can use Insertion Sort because it divides an array into two parts (sorted and unsorted)
Well it depends if there is any rules that array conforms while changing(in other words you know how approximately the array will be after modifying) then you have to analize which sort algorithm works best for you. If it is chaotic and you have no idea how it will look then probably quicksort. This is if array is completedly changed. But if changing happens by single element(like u insert or delete or stuff like that) then you better be sorting initial array once and inserting the new element into it.