Posted in Software Engineering

Sorting Algorithm

 

Sorting classification

Internal vs. External Sorting
Sorting algorithms can be classified into two types of algorithms: internal and external. Internal sorting algorithms require the full data set to fit into main memory whereas external sort is used when the full data set does not fit and have to reside on external storage during the sorting process.

Stable vs. Unstable Sorting
A stable sorting algorithm is when two objects with equal keys appear in the same order in the unsorted input array and the sorted output array. Examples of stable sorting algorithms are Insertion sort, Merge Sort and Bubble Sort.

An unstable sorting algorithm is when two objects with equal keys doesn’t appear in the same order in the unsorted input array and the sorted output array. Examples of unstable sorting algorithms are Heap Sort and Quick Sort.

Time vs. Space Complexity

Time Complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

Space Complexity is the computational complexity that describes the amount of memory space required by an algorithm.

In-place vs. Out-of-place Algorithm
An in-place algorithm is an algorithm which transforms input using no auxiliary data structure. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements.

An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

List of Sort Algorithms

The following algorithms are examples of internal sorting algorithms:

Algorithm Name Time Complexity: Best Time Complexity: Average Time Complexity: Worst Space Complexity: Worst
Bubble Sort Ω(n) Θ(n2) O(n2) O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n2) O(n)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
Cube Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heapsort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Insertion Sort Ω(n) Θ(n2) O(n2) O(1)
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n2 O(n log(n))
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Selection Sort Ω(n2) Θ(n2) O(n2) O(1)
Shell Sort Ω(n log(n)) Θ(n log2n) O(n2) O(1)
Timsort Ω(n) Θ(n log(n)) Θ(n log(n)) O(n)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n2) O(n)

 

source https://www.code2bits.com/algorithms/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s