Sorting Algorithms and Analysis

What is Sorting??

So, The arrangement of data in preferred order is called sorting. A simple example of sorting is When you tried to look up a word in a dictionary before the Internet, you had to do so in alphabetical order. Imagine the stress of having to sift through a large book containing all of the English words from around the world in a jumbled order!

It’s the same panic that an engineer would feel if their data isn’t organized and sorted.

A sorting algorithm is nothing more than a set of instructions or orders.

An array is used as an input, and the sorting algorithm performs operations on it to produce a sorted array.

An example of what sorting does –

Suppose you have an array: [e,a,d,c,b]

Now after sorting the output would be –

Output: [a,b,c,d,e]

Types of Sorting in Data Structures

(1) Merge Sort

(2) Selection Sort

(3) Insertion Sort

(4) Shell Sort

(5) Heap Sort

(6) Bubble Sort

Merge Sort –

This algorithm divides an array into two halves of roughly equal size.

The merge () function is then used to sort and merge the two halves back together.

  1. Return if there is only one element in the list that has already been sorted.
  2. Divide the list into two halves recursively until it can no longer be separated.
  3. Sort the lesser lists and merge them into a new list.

Here’s how the algorithm works –

(1) Merge Sort can be used to sort linked lists.

(2) Merge Sort is a stable sort, meaning that the same element in an array maintains its original position in relation to other elements in the array.

(3) Merge sort has an overall time complexity of O(nLogn). It is more efficient since the worst-case runtime is also O(nlogn).

Selection Sort –

A straightforward sorting algorithm is selection sort.

This sorting algorithm is based on in-place comparison and divides the list into two parts: the sorted part on the left end and the unsorted part on the right.

The sorted part is initially empty, while the unsorted part contains the entire list.

The unsorted array’s lowest element is chosen and replaced with the leftmost element, resulting in that element becoming a part of the sorted array.

This process continues to move the unsorted array boundary to the right by one element.

(1) Iterate through the unsorted array, noting the minimum value along the way.

(2) You’ll know which element is the smallest when you reach the end of the array.

(3) In the unsorted array, swap the minimal and first elements.

(4) The first element has now been classified as sorted.

(5) Continue sorting the rest of the array.

Here’s how the algorithm work’s –

Insertion Sort –

In Insertion Sort, The array is divided into two parts, one sorted and the other unsorted. The values from the unsorted part are selected and placed in the sorted part in the proper order.

(1) It is already sorted if it is the first element.

(2) Choose the next component.

(3) Compare all of the items in the sorted sub-list.

(4) All elements in the sorted sub-list that are greater than the value to be sorted should be shifted.

(5) Fill in the value.

(6) Continue until the list is sorted.

Here’s how the algorithm work –

(1) It works well for smaller data sets but not so much for longer lists.

(2) Insertion Sort is adaptive, which means that if given a partially sorted list, it reduces the total number of steps and thus improves efficiency.

(3) It has a lower spatial complexity.

(4) Insertion sort necessitates a single extra byte of memory.

(5) Insertion sort has an overall time complexity of O(n2).

Shell Sort –

Shell Sort is essentially an Insertion Sort variant. We only move elements one position forward in insertion sort. Many movements are required when an element must be moved far ahead. The goal of Shell Sort is to allow for the exchange of items from afar. For a large value of h, we use Shell Sort to sort the array. We reduce the value of h until it equals one.

If all sublists of every h’th element are sorted, the array is said to be h-sorted.

(1) Iterate through the unsorted array, noting the minimum value along the way.

(2) You’ll know which element is the smallest when you reach the end of the array.

(3) In the unsorted array, swap the minimal and first elements.

(4) The first element has now been classified as sorted.

(5) Continue sorting the rest of the array.

Here’s how the algorithm work’s –

Heap Sort –

Heap sort is a sorting technique that uses a Binary Heap data structure to compare items.

It’s analogous to how we find the maximum element first and then place it at the end of a selection sort. The process is repeated for the remaining elements.

Here’s the algorithm –

Bubble Sort –

The simplest sorting algorithm is Bubble Sort, which works by repeatedly swapping adjacent elements if they are in the wrong order.

(1) Start with the first two elements in an unsorted array of five elements and sort them in ascending order.(Compare the elements to see which is larger.)

(2) To determine which element is higher, compare the second and third elements and sort them in ascending order.

(3) To determine which element is higher, compare the third and fourth elements and sort them in ascending order.

(4) To determine which element is higher, compare the fourth and fifth elements and sort them in ascending order.

(5) Steps 1–5 should be repeated until no more swaps are needed.

Here’s the algorithm —

(1) The order of large values is always sorted first.

(2) It only takes one iteration to detect whether or not a collection has been sorted.

(3) Bubble Sort’s best time complexity is O(n). O(n2) is the average and worst time complexity.

(4) Bubble Sort has an O(1) space complexity since only a single extra memory space is needed.

Overall Sorting Algorithms are an important concept to understand when it comes to algorithms. Thank you for reading this blog post.