Clever Geek Handbook

Least time complexity sorting algorithm for an already sorted array?

I have a question about which type of sorting algorithm will have the least time complexity if we are given an already sorted array.

+3


source to share


2 answers


Sounds like a homework question, but I'd say one very simple algorithm, time efficient for sorted or only slightly unsorted lists, is a bubble type . Sorting, time complexity O (n). However, there are many sorting algorithms that have similar time complexity for the best-case scenario (i.e. already sorted), and bubble sort has a worst-case O (n 2 ).



0


source


Wikipedia has a table showing a comparison of the best, average and worst performance of many different sorting algorithms . Here's an excerpt:

enter image description here

There are many algorithms that have (𝑛) running times for the best inputs (i.e. pre-sorted data). However, most of them (eg bubble sort) have 𝓞 (²²) run times for medium and worst-case inputs. This is what you really want to avoid. Sorting a million items with one of these algorithms will take forever.



Fortunately, some of these algorithms have average and worst-case running times of 𝓞 (𝑛 log 𝑛). These are the following:

I would recommend using one of them.

+4


source






More articles:


All Articles