Table of Contents
hide
Sorting
Introduction of Sorting
 It puts items in a list into a specific order for further use.
Definition of Sorting
 Sorting is the process/technique of rearrangement of data items (stored inside the memory) in some specific order(such as either in ascending order or in descending order or in alphabetical order or any other userdefined order) so that retrieval of information becomes easier.
Characteristics of Sorting
 Sorting algorithms can be characterized in the following two ways:
(i) Simple algorithms uses the order of n2 (written as O(n2))comparisons to sort n items.
(ii) Sophisticated algorithms uses the O(nlog2n) comparisons to sort n items.
 The performance of a sorting algorithm/type can also depend on the degree of order already present in the data.
Types of Sorting
 There are so many sorting algorithms available to sort the data. These sorting algorithms vary in their way of sorting mechanism. Different environments require different sorting methods.
 There are several categories of sorting(Comparison and NonComparision Sorting, InPlace and Notinplace Sorting, Adaptive and Nonadaptive Sorting, and Stable and NonStable Sorting ) but two basic categories of sorting methods: – Internal Sorting and External Sorting.
(A.) Comparisonbased and NonComparisionbased Sorting
(a)Comparisionbased Sorting :


 Comparisonbased sorting algorithms are a class of sorting algorithms that sort elements in an array list by comparing them pairwise based on some defined comparison operator (usually less than or greater than).
 Comparisonbased sorting algorithms are widely used due to their simplicity and effectiveness.
 The most wellknown sorting algorithms, including some of the fundamental ones, fall into this category such as Bubble sort, Selection sort, Insertion sort, Quick sort, Merge sort, Heap sort etc.

(b)NonComparisionbased Sorting :


 Noncomparisonbased sorting algorithms, also known as lineartime or linearithmictime sorting algorithms, are a class of sorting algorithms that do not rely on pairwise comparisons between elements to determine their relative order.
 This sorting works using certain properties of the data, such as integer values or specific patterns, to sort the elements more efficiently than comparisonbased algorithms.
 They can achieve better time complexity than comparisonbased algorithms in some cases, particularly when the range of input values is limited or when the distribution of data exhibits certain patterns.
 This algorithm is not as versatile as comparisonbased algorithms, as their applicability can be restricted by the nature of the data.
 For example – Counting sort, Bucket sort, Radix sort, etc.

(B.) Adaptive and NonAdaptive Sorting
(a)Adaptive Sorting :


 When a sorting algorithm takes advantage of already ‘sorted’ elements present in the list that is to be sorted.
 It takes advantage of some elements present that are already sorted and do not reorder them.

(b)NonAdaptive Sorting :


 A nonadaptive algorithm does not take into account the elements which are already sorted.
 They try to force every element to be reordered to confirm their sorting process.

(C.) InPlace and NotinPlace Sorting
(a)InPlace Sorting :


 Inplace sorting algorithms there is no requirement of any extra space for comparison and temporary storage of a few data elements during the sorting process say for example, within the array itself.
 Bubble sort is an example of inplace sorting.

(b) NotInPlace Sorting :


 In NotInPlace sorting algorithms, the program requires some extra space that is more than or equal to the elements being sorted.
 Mergesort is an example of notinplace sorting.

(D.) Stable and NonStable Sorting
(a)Stable Sorting :


 A Stable sorting algorithm, after sorting the contents/values of lists, does not change the sequence(after/before location) of similar values/contents(not different values) in which they appear, it is called stable sorting.

(b)NonStable Sorting :


 A NonStable sorting algorithm, after sorting the contents/values of lists, changes the sequence(after/before location) of similar values/contents(not different values) in which they appear, it is called nonstable sorting.

(E.) Internal and External Sorting
(a) Internal Sorting :


 When sorting is applied the entire collection of data is to be sorted in a small enough space inside the Primary or Main memory or RAM. It is called Internal Sorting.
 There is a limitation for internal sorts i.e. they can only process relatively small lists due to memory constraints.
 The time required to read or write is not considered to be significant in evaluating the performance of internal sorting methods.
 These algorithms work on the principle of comparing elements in the input array to determine their relative order called the Comparisionbased sorting algorithm (eg – Insertion, Bubble, Selection, Quick, Heap, Tree, Merge sort), and NonComparison Sorting Algorithms(Sorts elements without directly comparing them, often leveraging properties of the input data. eg Counting, Radix, Bucket sort)
 Examples of Internal sorting are :
 Insertion sort
 Bubble sort
 Selection sort
 Quick sort
 Heap sort
 Tree sort
 Merge sort
 Counting sort
 Radix sort
 Bucket sort
 Shell sort

(a.) Insertion Sort



 This is a type of Internal sort.
 This is a naturally occurring sorting method.
 In this sorting, at every step, we insert an item into its proper place in an alreadyordered list. Here, insertion sort does not exchange elements rather the element is inserted at an appropriate sorted place. Here the list is divided into two parts sorted and unsorted sublists. In each step, the first element of the unsorted sublist is picked up and moved into the sorted sublist by inserting it in a suitable position. When we have ‘n’ elements then we need n1 steps to sort the elements.


(b.) Bubble Sort



 Bubble sort is a type of Internal Sort.
 Bubble sort is a simple, comparisonbased sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The pass/iteration through the list is repeated until no swaps are needed, and the list is sorted.
 The Bubble sort performs a sorting operation using the exchange/swap of elements.
 Bubble sort gets its name because it filters out or sorts the elements at the top of the array like bubbles on water.
 Bubble sorting is one of the easiest ways of sorting techniques.
 We can sort both numeric as well as string values using it.
 It is very simple to implement.
 Bubble Sort repeatedly steps through the array list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire array is sorted.
 While conceptually simple, Bubble Sort is inefficient for larger datasets.
 It gives quite accurate results.
 It is the slowest algorithm.
 The best time complexity of a bubble sort can be O(n). O(n) is only possible if the array is sorted.
 Algorithms of Bubble Sort:


Step 1: Start with the first element (with index 0) of the list.
Step 2: Compare the current element with the next adjacent element (index 1 or more).





 If the current element value is greater than the next element, swap them(when sorted in ascending order and viceversa in descending order).
 If not, move/skip to the next pair of elements.




Step 3: Continue comparing and swapping adjacent elements until we reach the end of the list. Finally, the largest element in the unsorted portion “bubbles up” to the end of the list in one pass or iteration.
Step 4: Repeat steps 13 for the remaining unsorted portion of the list, excluding the sorted last element, which is already in its correct position after the first pass or iteration.
Step 5: Continue these passes through the list, each time one less element to compare, until no more swaps are needed in a pass/iteration which is the indication that the entire list is sorted.
(c.) Selection Sort



 This is a type of Internal sort.
 The selection sort performs a sorting operation using the exchange of elements.
 Selection sort is a simple sorting algorithm.
 Selection sort is another simple comparisonbased sorting algorithm.
 It sorts an array list by repeatedly selecting the minimum element from the unsorted portion of the array and moving it to the beginning of the sorted portion.
 This sorting algorithm is an ‘inplace comparison’ based algorithm or working principle in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially sorted part is empty and the unsorted part is the entire list. Here, the smallest element is selected from the unsorted array and swapped with the leftmost element and that element becomes part of the sorted array. This process continues moving unsorted array boundary by one element to the right.
 It also performs a lot of unnecessary swaps. However, it has the advantage of being simple to understand and easy to implement.
 This algorithm is not suitable for large data sets or lists because its average and worstcase time complexity is O(n^{2}) which is not effective where n are no. of items.
 Algorithms of Selection Sort:


Step 1: Start with the first element of the array list (as the minimum value).
Step 2: Iterate through the rest of the array list to find the minimum element in the unsorted portion of the array by comparing each element with the current minimum value.
Step 3: If a smaller element is found, update/swap the minimum value to be that element otherwise skip it.
Step 4: Increment the index of the sorted portion and repeat steps 14 until the entire array is sorted.
(d.) Quick Sort



 Quick sorts are based on the Divide and Conquer concept. The divide and conquer strategy solves a problem by :
(i) Breaking the main problems into several subproblems that are themselves smaller instances of the original problem.
(ii) Recursively solving these subproblems.
(iii) Appropriately combining these solved subproblems.
 Quick sorts are based on the Divide and Conquer concept. The divide and conquer strategy solves a problem by :


(e.) Heap Sort



 Heap Sort is a popular comparisonbased sorting algorithm that creates the structure of a binary heap (specifically, a maxheap or minheap) to efficiently sort an array of elements.
 It is known for its optimal worstcase and averagecase time complexity of O(n log n), making it suitable for sorting large datasets.
 Heap Sort works by transforming the input array into a binary heap repeatedly extracting the root element (maximum or minimum, depending on the type of heap) and placing it at the end of the sorted portion of the array.
 Heap sort is completed in two steps – (i) Heap Creation and, (ii) Heap sorting.

Heap Sort has the following characteristics:

Time Complexity: The worstcase, averagecase, and bestcase time complexity of Heap Sort are all O(n log n), making it efficient for sorting large datasets.

InPlace Sorting: Heap Sort requires only a constant amount of additional memory space for its operations, making it an inplace sorting algorithm.

Unstable Sort: Heap Sort is generally unstable, meaning that it might change the relative order of equal elements in the input array.

Not Adaptive: The time complexity of Heap Sort is not affected by whether the input is partially sorted or not. It performs equally well regardless of the initial order of elements.

 Heap Sort is widely used in various applications due to its predictable time complexity and inplace nature.


(b)External Sorting :


 External sorting is a method that is applied to a larger collection of data items that cannot fit entirely in the main memory (RAM) of a computer but reside on Secondary or External devices such as Hard disks to perform sorting operations efficiently.
 All external sorts are based on the process/principle of merging i.e. different parts of data are sorted separately and merged together.
 Read and write access times are a major concern in determining the sorting performances of such methods.
 Examples are: External Merge Sort, Polyphase Merge Sort, Replacement Selection Sort, External Quick/Bubble/Insertion Sort, Tape Sort, and Kway Merge Sort.

Merge Sort/TwoWay Merge Sort
 Merge sort is based on the principle of “divide and conquer” principle i.e., divides the array into smaller subarrays, sorts them, and then merges them back together.
 TwoWay Merge Sort, also known as Merge Sort, is a classic comparisonbased sorting algorithm that follows the divideandconquer paradigm.
 It is a sorting algorithm that follows the divideandconquer approach to sort an array of elements by splitting it into smaller subarrays, sorting those subarrays, and then merging them back together. TwoWay Merge Sort differs from the standard Merge Sort in how it merges two subarrays.
 It works by recursively dividing the input array into smaller subarrays, sorting those subarrays, and then merging them back together to obtain the final sorted array.
 Merge Sort has a time complexity of O(n log n), making it efficient for sorting large datasets.
 TwoWay Merge Sort’s consistent time complexity and efficient performance make it a popular choice for sorting applications where stability and predictable behavior are important.

The working mechanism of the TwoWay Merge Sort algorithm is completed in the following steps:

Divide: The input array is divided into two halves, roughly equal in size. This process continues recursively until each subarray contains only one element (which is already sorted by definition).

Conquer: The individual subarrays are sorted by comparing elements within each subarray. Since each subarray contains only one element, they are already considered sorted at this point.

Merge: The sorted subarrays are merged back together in a sorted manner. This involves comparing the elements of both subarrays and placing them in order in a new merged array. The process continues until all elements from both subarrays are merged into a single sorted array.

 Thus, in brief, the basic working mechanism of merge sort is to divide the list into two smaller sublists of approximately equal size. Recursively repeat this procedure till only one element is left in the sublist. After this, various sorted sublists are merged to form a sorted parent list. This process goes on recursively till the original sorted list arrives. Thus, the merge sort is completed in three major steps – Divide part, Conquer part, and finally Combine part.

Types of Merge Sort:

TopDown Merge Sort:

The standard form of Merge Sort is often referred to as TopDown Merge Sort.

It follows the divideandconquer approach by recursively dividing the input array into smaller subarrays, sorting them, and then merging them.

This version of Merge Sort is characterized by its clarity and ease of implementation.


BottomUp Merge Sort:

Bottomup Merge Sort is a variation that starts by treating each element as a sorted subarray and then repeatedly merges adjacent subarrays to form larger sorted subarrays.

This version avoids the recursive approach of the topdown variant and is sometimes considered more efficient in practice due to better cache utilization and reduced function call overhead.


TwoWay Merge Sort:

Twoway merge Sort is a simplified version of Merge Sort that performs the merging step by comparing elements from two subarrays directly and placing the smaller elements into a temporary array.

This is in contrast to the standard Merge Sort, which uses an auxiliary array to store merged subarrays.

Twoway merge Sort is straightforward to implement and is used in cases where memory usage is a concern.


InPlace Merge Sort:
 Inplace Merge sort algorithms do not require any extra space for comparison and temporary storage of a few data elements during the sorting process.

InPlace Merge Sort is an advanced variant that aims to minimize memory usage by performing the merging step in place, without requiring additional memory for temporary arrays.

It employs techniques like swapping and shifting elements to achieve this.

InPlace Merge Sort is challenging to implement correctly and efficiently due to the complex nature of inplace merging.

KWay Merge Sort:

KWay Merge Sort generalizes the concept of merging by allowing the algorithm to merge more than two subarrays at a time.

Instead of merging pairs of subarrays, KWay Merge Sort merges multiple subarrays using a priority queue or a heap data structure.

This variant can improve efficiency when dealing with a large number of subarrays.



Efficiency of Sorting Techniques
 The efficiency of the Sorting technique is to get the amount of time required to sort an array of ‘n’ elements by a particular method.
 There may be any of three ways to measure the efficiency of sorting techniques:
 Best case
 Average case
 Worst case
Advantages of Sorting
 Sorting creates the specific sequence of the list of items which helps in fast & quick searching.
 It helps to analyze the data to get the desired filtered data.
 It helps to optimize the efficiency of other algorithms.
Disadvantages of Sorting
 The sorting process may take a long time, especially when it is a large list.
0 Comments