What is Sorting? Type of Sorting

Sorting refers to ordering data in an increasing or decreasing fashion according to some linear relationship among the data items.

 Sorting can be done on names, numbers and records. Sorting reduces the For example, it is relatively easy to look up the phone number of a friend from a telephone dictionary because the names in the phone book have been sorted into alphabetical order.

This example clearly illustrates one of the main reasons that sorting large quantities of information is desirable. That is, sorting greatly improves the efficiency of searching. If we were to open a phone book, and find that the names were not presented in any logical order, it would take an incredibly long time to look up someone’s phone number.

Sorting can be performed using several methods, they are:

Insertion sort.

In this method, sorting is done by inserting elements into an existing sorted list. Initially, the sorted list has only one element. Other elements are gradually added into the list in the proper position.

Merge Sort.

In this method, the elements are divided into partitions until each partition has sorted elements. Then, these partitions are merged and the elements are properly positioned to get a fully sorted list.

Quick Sort.

In this method, an element called pivot is identified and that element is fixed in its place by moving all the elements less than that to its left and all the elements greater than that to its right.

Radix Sort.

In this method, sorting is done based on the place values of the number. In this scheme, sorting is done on the less-significant digits first. When all the numbers are sorted on a more significant digit, numbers that have the same digit in that position but different digits in a less-significant position are already sorted on the less-significant position.

Heap Sort

In this method, the file to be sorted is interpreted as a binary tree. Array, which is a sequential representation of binary tree, is used to implement the heap sort.

The basic premise behind sorting an array is that its elements start out in some random order and need to be arranged from lowest to highest.

It is easy to see that the list

1, 5, 6, 19, 23, 45, 67, 98, 124, 401

is sorted, whereas the list

4, 1, 90, 34, 100, 45, 23, 82, 11, 0, 600, 345

is not. The property that makes the second one “not sorted” is that there are adjacent elements that are out of order. The first item is greater than the second instead of less, and likewise the third is greater than the fourth and so on. Once this observation is made, it is not very hard to devise a sort that proceeds by examining adjacent elements to see if they are in order, and swapping them if they are not.

Selection sort: In this technique, the first element is selected andcompared with all other elements. If any other element is less thanthe first element swapping should take place.By the end of this comparison, the least element most top position in the array. This is known as pass1. In pass II, the second element is selected and compared with all other elements. Swapping takes place if any other element is less than selected element. This process continuous until array is sorted.

The no. of passes in array compare to size of array –1.

Bubble sort: This technique compares last element with the preceding element. If the last element is less than that of preceding element swapping takes place. Then the preceding element is compared with that previous element. This process continuous until the II and I elements are compared with each other. This is known as pass 1.

This way the number of passes would be equal to size of array –1.