Need of Sorting Techniques... By-SY IT group 4

- December 20, 2020

INTRODUCTION TO SORTING...

There are so many things in our daily life that we need to search for, like particular record in any database, roll numbers in the merit list, a particular telephone number in the telephone directory, a particular page in any book etc. All this would have been a litter if the data was retained unordered and unsorted, but fortunately the idea of sorting came into existence, making it efficient for everyone to arrange data in perfect order, hence making it efficient to search. Here's a simple example, if you have pile of clothes on your bed and your sister have arranged her clothes in almirah properly. Your mother ordered both you to clean your rooms. Then who's room will get cleaned first? You got the idea, right! This is what the concept of sorting is about.

Sorting refers to the functioning or the system of arranging and rearranging sets of data in some specific manner. Basically, sorting is arranging data in ascending or descending order. Actually, term sorting came into picture, as humans realized importance of searching quickly. Sorting refers to arranging the data in a particular format. Sorting algorithm specifies way to arrange the data in a particular order and format.

Sorting arranges the data in a sequence which makes searching efficient. Sorting is the operation performed to arrange records of a table or list in some order according to some specific ordering criteria. Sorting technique is performed according to some key value of each record. The significance of sorting lies in the fact, that data finding can be optimized to high level, if data is kept in a sorted manner. Sorting is also used to represent the data in more precise formats.

Need of Sorting Techniques...

Arrangement of the data in preferred order is called sorting in the data structure. By sorting data, it is efficient to search through it quickly and easily. The simplest example of sorting is a dictionary. Before the age of Internet, when you wanted to look up a word in a dictionary, you would do so in alphabetical order. This made it easy.

1. Accuracy: Sorting Algorithms give an abstract way of studying program accuracy. We don’t have to be concerned about other development tasks, such as system configuration or working with dependencies. Instead we are able to simply focus on our data input and outputs.

2. Speed: Sorting Algorithms brings speed in the data handling which makes the performance in your program which apparently reflects the working of your project.

3. Decency: Some types of sorting algorithms may end up being optically more pleasing, giving good intermediate steps allowing for optical inspection of data where a we guys can recognize where in the process one is and analyze what goes wrong and sanitize the data suitably.

4. Time Complexity : The main advantage of sorting is time complexity and that’s the most important thing when you solve problem because it’s not enough you’re able to solve a problem but you should be able to answer it in the minimum time possible. Sometimes problems can be solved easily and fast based on sorting.

The Complexity Of Sorting Algorithms...

The complexity of Sorting Algorithms calculates running time of function in which 'n' number of items are to be sorted. The choice for which sorting method is suitable for problem depends on some dependency configurations for different problems. The most noteworthy of these considerations are:

1. The length of time spent by the programmer in programming a specific sorting problem.

2. The amount of machine time necessary for running program.

3. The amount of memory necessary for running the program.

Different Sorting Algorithms...

There are various techniques available for sorting, basically, metamorphosed by their efficiency and space requirements. Each Sorting technique has its own way of execution making it different from others. Following are some sorting techniques:

1.Bubble Sort

2.Insertion Sort

3.Selection Sort

4.Quick Sort

5.Merge Sort

6.Heap Sort

1. BUBBLE SORT :

Bubble sort is an algorithm that compares the neighboring elements and swaps their positions if they are not in the intended sequence. The order can be ascending or descending.

The primary advantage of the bubble sort it is easy to implement. In the bubble sort, elements are swapped in place without using additional provisional storage, so the space requirement is at a minimum.

To perform bubble sort, we have to follow below steps:

Step 1: Check if data on the 2 adjacent nodes are in ascending order or not. If not, swap the data of the 2 adjacent nodes.

Step 2: At the end of pass 1, the largest element will be at the end of the list. In 2nd pass 2nd largest element will be at its position.

Step 3: We terminate the loop, when all the elements are sorted.

Time Complexity : Worst and Average Case Time Complexity is O(n*n) and Best Case Time Complexity is O(n).

Space Complexity : Space Complexity is O(1).

2. INSERTION SORT :

Insertion sort is a sorting algorithm that places an unsorted element at its worthy place in each iteration.

The important advantage of the insertion sort is its simplicity. It also exhibits a good performance when dealing with a tiny list. The insertion sort is an in place sorting algorithm so the space requirement is very little.

To perform insertion sort, we have to follow below steps:

Step 1 : If it is the first element, it is already sorted, return 1.

Step 2 : Pick next element

Step 3 : Compare with all elements in the sorted sub-list

Step 4 : Shift all the elements in the sorted sub-list that is greater than the value to be sorted

Step 5 : Insert the value

Step 6 : Repeat until list is sorted

Time Complexity : Worst and Average Case Time Complexity is O(n*n) and Best Case Time Complexity is O(n).

Space Complexity : Space Complexity is O(1).

3. SELECTION SORT :

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the starting of the unsorted list.

The important advantage of the selection sort is that it performs well on a small list. Because it is an in place sorting technique, no additional provisional storage is required beyond what is needed to hold the original list. Its performance is easily affected by the initial ordering of the items before the sorting process.

To perform selection sort, we have to follow below steps:

Step 1 : Set MIN to location 0

Step 2 : Search the minimum element in the list

Step 3 : Swap with value at location min

Step 4 : Increment MIN to point to next element

Step 5 : Repeat until list is sorted

Time Complexity : Worst and Average Case Time Complexity is O(n*n) and Best Case Time Complexity is O(n*n).

Space Complexity : Space Complexity is O(1).

4. QUICK SORT :

Quick sort is an algorithm based on divide and conquer approach in which the array is split into sub-arrays and these sub-arrays are recursively called to sort the elements.

It is in place since it uses only a tiny auxiliary stack. It requires only n (log n) time for sorting of n items. It has an extremely short inner loop. This algorithm has been subjected to a thorough mathematical analysis, accurate statement can be made about performance issues.

To perform quick sort, we have to follow below steps:

Step 1 : Choose the highest index value has pivot

Step 2 : Take two variables to point left and right of the list excluding pivot

Step 3 : left points to the low index

Step 4 : right points to the high

Step 5 : while value at left is less than pivot move right

Step 6 : while value at right is greater than pivot move left

Step 7 : if both step 5 and step 6 does not match swap left and right

Step 8 : if left ≥ right, the point where they met is new pivot

Time Complexity : Worst Case Time Complexity is O(n*n) , Average Case Time Complexity is O(n log n) and Best Case Time Complexity is O(n log n).

Space Complexity : Space Complexity is O(log n).

5. MERGE SORT :

Merge Sort is a basically kind of Divide and Conquer algorithm in computer programming. It is one of the most favored sorting algorithms and a great way to develop confidence in building recursive algorithms.

It is quicker for larger lists because unlike insertion and bubble sort it doesn't go through the whole list several times. It has a congruous running time, carries out different bits with near time in a stage.

To perform merge sort, we have to follow below steps:

Step 1 : if it is only one element in the list it is already sorted, return.

Step 2 : divide the list recursively into two halves until it can no more be divided.

Step 3 : merge the smaller lists into new list in sorted order.

Time Complexity : Worst and Average Case Time Complexity is O(n log n) and Best Case Time Complexity is O(n log n).

Space Complexity : Space Complexity is O(n).

6. HEAP SORT :

Heap Sort is a popular and systematic sorting algorithm in computer programming. Studying how to write the heap sort algorithm requires understanding of two types of data structures - arrays and trees.

The Heap sort algorithm is widely used because of its logicality. The Heap sort algorithm can be executed as an in place sorting algorithm. Its memory usage is minimal.

To perform heap sort, we have to follow below steps:

Step 1 : use heapify to build a max heap of element present in an array A.

Step 2 : once the heap is ready, the largest element will be present in the root node of the heap i.e, A[1].

Step 3 : swap the element at A[1] with the last element of array, and heapify the max heap excluding the last element.

Step 4 : repeat steps 2 and 3 till all the element in the array are sorted.

Time Complexity : Worst and Average Case Time Complexity is O(n log n) and Best Case Time Complexity is O(n log n).

Space Complexity : Space Complexity is O(1).