complexity

Question

We want to sort input sequence in ascending order. If inputs are already ascending order , then what is the time complexity to run this of all well known sort (Bobble sort, quick sort,merge sort, insertion sort, selection sort, heap sort,...)

Which complexity of sorting will be change with general case complexity? Which are not ?

If any resource u have for this question plz. provide

Answer 1

For already sorted sequence,

Bubble sort will take $o(n)$

Insertion sort will take $o(n)$, but better than bubble sort.

Merge sort will take $o(n log n)$

Quick sort will take $o(n^{2})$

Heap sort will take $o(n log n)$

Comments

how r  u finding?

any process?

why insertion sort better than bubble sort?

---

If you will visualize the sorting algorithms you will realize that in Insertion sort and Bubble sort, only n-1 comparisons will be needed to identify that it is already sorted. Therefore, O(n)

No need to talk about Merge sort, because it will be always O(nlogn) .

In heap sort, when it is already sorted, we would still need to max-heapify when numbers are extracted from root.

In quicksort, it depends on pivot and its value and not in sorted order. Therefore, it will be O(n^2).

Insertion sort is faster than Bubble sort when list is almost sorted. Because swapping can be done in 1 assignment.

---

Because even if already sorted, bubble sorting takes one complete traversing of inputs to ensure that no swaps now occur.

Answer 2

Insertion sort--->Best Case : Θ(n); when input is already sorted

Selection sort--->Average Case / Worst Case / Best Case: Θ(n2)

Merge sort--->Average Case / Worst Case / Best case : Θ(nlgn) ; doesn't matter at all whether the input is sorted or not

Quick sort--->Best Case : Θ(nlogn)when pivot divides array in exactly half

Bubble sort--->Best Case : Θ(n) ; on already sorted

Heap sort--->Θ(nlogn) in best case

All complexities depend on the size of the input.

Comments

No I donot want that

I know this

I want special case as sorted order

---

Why do you want to sort when already sorted. I don't understand. Plz can u clarify more..?

---

chk now