1. Sorting problem: We are given a sequence of numbers x1, x2, xn. We scan these
ID: 3809535 • Letter: 1
Question
1. Sorting problem: We are given a sequence of numbers x1, x2, xn. We scan these numbers from left to right, and put xi to left of xin if xais smaller than xi-1. n other words, we continuously move x to the left until the numbers to its left are all smaller than or equal to it. Design an algorithm to resolve this sorting problem.
2. Please analyze the time complexity of your above designed algorithm, in terms of both the best case and worst case complexities.
1. Sorting problem: We are given a sequence of numbers x1, x2, xn. We scan these numbers from left to right, and put xi to left of xin if xais smaller than xi-1. n other words, we continuously move x to the left until the numbers to its left are all smaller than or equal to it. Design an algorithm to resolve this sorting problem. (20 Marks) 2. Please analyze the time complexity of your above designed algorithm, in terms of both the best case and worst case complexities. (10 Marks)Explanation / Answer
1. Algorithm for sorting algorithm
Input : Get sequence of numbers x1,x2,...,xn.
Output : sorted numbers sequence.
Algorithm :
for i:1 to n {
for j=i-1 to n {
if (x[i]<x[j]||x[i]=x[j])
{
temp=x[i]
x[i]=x[j]
x[j]=x[i]
}
}
}
2.Analyze the time complexity:
best case and worst case is o(n^2)
sorting algorithm runs for n number of times, for n number of values.
This algorithm runs o(n^2) time, even if the array is alredy sorted.
It compares all the element with other element, that is, n no of element is compared with n no of elements.
It can be optimized , if it does not have to swap.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.