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.

1. 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 (θ)
2. Space Complexity: The entire amount of memory utilised by the method for

   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.

   1. 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 (θ)
   2. 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	n2	n2	1
   Selection Sort	n2	n2	n2	1
   Insertion Sort	n	n2	n2	1
   Merge Sort	n log n	n log n	n log n	N
   Quick Sort	n log n	n2	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	n2	n	max
   Heap Sort	n log n	n log n	n log n	1
   Shell Sort	n log n	n2	n log n	N
   Comb Sort	n log n	n2/2p	n2	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

   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	n2	n2	1
Selection Sort	n2	n2	n2	1
Insertion Sort	n	n2	n2	1
Merge Sort	n log n	n log n	n log n	N
Quick Sort	n log n	n2	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	n2	n	max
Heap Sort	n log n	n log n	n log n	1
Shell Sort	n log n	n2	n log n	N
Comb Sort	n log n	n2/2p	n2	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