Evaluate this method and compare it to Insertion sort: public static void sort(C

Question

Evaluate this method and compare it to Insertion sort:
public static void sort(Comparable[] a) {
int N = a.length;
for ( int i=0;i<N;i++)
for ( int j = N-1; j > i; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
}
Evaluate this method and compare it to Insertion sort:
public static void sort(Comparable[] a) {
int N = a.length;
for ( int i=0;i<N;i++)
for ( int j = N-1; j > i; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
}
Evaluate this method and compare it to Insertion sort:
public static void sort(Comparable[] a) {
int N = a.length;
for ( int i=0;i<N;i++)
for ( int j = N-1; j > i; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
}

Explanation / Answer

public static void sort(Comparable[] a) {

int N = a.length; ==>Takes O(1) constant time

for ( int i=0;i<N;i++) ==>Takes O(N) time as the Loop will run N time

for ( int j = N-1; j > i; j--) ===> Loop runs for N + N -1 + N-2+ ...+1 => O(N2)

if (less(a[j], a[j-1]))=> If condition check of O(1) bur runs for O(N2) TIME

exch(a, j, j-1);

}

Total time Complexity is O(N2)


Explanation and Comparision with Insertion Sort

=> Outer Loop will run for N time, Inner loop will start from end and keep swapping if the next element is less than its adjacent. If so then swap.
=> In this way we keep swapping. In first iteration the minimum element will be at the firt position.

This way the above Code works


Its different from Insertion Sort because In Insertion Sort we do not Keep swapping instead we keep shifting the elements and then add the element to its correct position

Both Insertion Sort and the above code takes O(n2) time

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.