# Sorting Algorithms in Data Structures

A sorting algorithm is used to organize the elements of an array or list. Sorting an array, for example.

**Unsorted array**

5 | 7 | 2 | 9 | 4 | 1 |

**Sorted array**

1 | 2 | 4 | 5 | 7 | 9 |

We're sorting the array in ascending order right now.

This procedure may be completed using a variety of sorting algorithms. And, depending on the situation, we may apply any algorithm.

## Various Sorting Algorithms

- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
- Comb Sort

## Sorting Algorithms' Complexity

The time complexity and space difficulty of any sorting algorithm influence the method's efficiency.

**Time Complexity:**The time it takes an algorithm to finish its execution in relation to the amount of the input is referred to as time complexity. It can be expressed in a variety of ways:- Big-O notation (O)
- Omega notation (Ω)
- Theta notation (θ)

**Space Complexity:**The entire amount of memory utilised by the method forA sorting algorithm is used to organize the elements of an array or list. Sorting an array, for example.

**Unsorted array**5 7 2 9 4 1 **Sorted array**1 2 4 5 7 9 We're sorting the array in ascending order right now.

This procedure may be completed using a variety of sorting algorithms. And, depending on the situation, we may apply any algorithm.

## Various Sorting Algorithms

- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
- Comb Sort

## Sorting Algorithms' Complexity

The time complexity and space difficulty of any sorting algorithm influence the method's efficiency.

**Time Complexity:**The time it takes an algorithm to finish its execution in relation to the amount of the input is referred to as time complexity. It can be expressed in a variety of ways:- Big-O notation (O)
- Omega notation (Ω)
- Theta notation (θ)

**Space Complexity:**The entire amount of memory utilised by the method for a complete execution is referred to as space complexity. Both the extra memory and the input are included.

Auxiliary memory is the space used up by the method in addition to the input data. When determining the space complexity of an algorithm, auxiliary memory is usually taken into account.

Let's look at the complexity of several sorting methods.

**Sorting Algorithms****Time Complexity****Best****Time Complexity****Average****Time Complexity****Worst****Space complexity**Bubble Sort n n ^{2}n ^{2}1 Selection Sort n ^{2}n ^{2}n ^{2}1 Insertion Sort n n ^{2}n ^{2}1 Merge Sort n log n n log n n log n N Quick Sort n log n n ^{2}nlog n log n Counting Sort n + k n + k n + k max Radix Sort n + k n + k n + k max Bucket Sort n + k n ^{2}n max Heap Sort n log n n log n n log n 1 Shell Sort n log n n ^{2}n log n N Comb Sort n log n n ^{2}/2^{p}n ^{2}1 ## Sorting Algorithm Stability

When two or more items with the same value keep the same relative positions after sorting, the sorting method is deemed stable.

In the figure below, for example, there are two objects with the identical value of 3. The two places of 3 may or may not be maintained depending on the stability of the sorting algorithm.

**Unsorted array**5 7 2 9 4 2 **After unstable sorting there are 2 possibilities**2 2 4 5 7 9 2 2 4 5 7 9 However, there is always one alternative following a stable sorting algorithm in which the locations are preserved as in the original array.

**Unsorted array**5 7 2 9 4 2 **Sorted array**2 2 4 5 7 9 This table displays the consistency of several sorting algorithms.

a complete execution is referred to as space complexity. Both the extra memory and the input are included.**Sorting Algorithms****Stability**Bubble Sort Yes Selection Sort No Insertion Sort Yes Merge Sort Yes Quick Sort No Counting Sort Yes Radix Sort Yes Bucket Sort Yes Heap Sort No Shell Sort No Comb Sort No

Auxiliary memory is the space used up by the method in addition to the input data. When determining the space complexity of an algorithm, auxiliary memory is usually taken into account.

Let's look at the complexity of several sorting methods.

Sorting Algorithms | Time Complexity Best | Time Complexity Average | Time Complexity Worst | Space complexity |

| | | | |

Bubble Sort | n | n^{2} | n^{2} | 1 |

Selection Sort | n^{2} | n^{2} | n^{2} | 1 |

Insertion Sort | n | n^{2} | n^{2} | 1 |

Merge Sort | n log n | n log n | n log n | N |

Quick Sort | n log n | n^{2} | nlog n | log n |

Counting Sort | n + k | n + k | n + k | max |

Radix Sort | n + k | n + k | n + k | max |

Bucket Sort | n + k | n^{2} | n | max |

Heap Sort | n log n | n log n | n log n | 1 |

Shell Sort | n log n | n^{2} | n log n | N |

Comb Sort | n log n | n^{2}/2^{p} | n^{2} | 1 |

## Sorting Algorithm Stability

When two or more items with the same value keep the same relative positions after sorting, the sorting method is deemed stable.

In the figure below, for example, there are two objects with the identical value of 3. The two places of 3 may or may not be maintained depending on the stability of the sorting algorithm.

**Unsorted array**

5 | 7 | 2 | 9 | 4 | 2 |

**After unstable sorting there are 2 possibilities**

2 | 2 | 4 | 5 | 7 | 9 |

2 | 2 | 4 | 5 | 7 | 9 |

However, there is always one alternative following a stable sorting algorithm in which the locations are preserved as in the original array.

**Unsorted array**

5 | 7 | 2 | 9 | 4 | 2 |

**Sorted array**

2 | 2 | 4 | 5 | 7 | 9 |

This table displays the consistency of several sorting algorithms.

Sorting Algorithms | Stability |

| |

Bubble Sort | Yes |

Selection Sort | No |

Insertion Sort | Yes |

Merge Sort | Yes |

Quick Sort | No |

Counting Sort | Yes |

Radix Sort | Yes |

Bucket Sort | Yes |

Heap Sort | No |

Shell Sort | No |

Comb Sort | No |