Sorting in Data Structure

  • Sorting is nothing but storage of data in sorted order, it can be in ascending or descending order. The term Sorting comes into picture with the term Searching.
  • There are so many things in our real life that we need to search, like a particular record in database, roll numbers in merit list, a particular telephone number, any particular page in a book etc.
  • Sorting arranges data in a sequence which makes searching easier. Every record which is going to be sorted will contain one key. Based on the key the record will be sorted.
  • For example, suppose we have a record of students, every such record will have the following data: Roll No. Name Age
  • Here Student roll no. can be taken as key for sorting the records in ascending or descending order. Now suppose we have to search a Student with roll no. 15, we don't need to search the complete record we will simply search between the Students with roll no. 10 to 20.

Sorting Efficiency

  • There are many techniques for sorting. Implementation of particular sorting technique depends upon situation. Sorting techniques mainly depends on two parameters.
  • First parameter is the execution time of program, which means time taken for execution of program.
  • Second is the space, which means space taken by the program.

Type of Sorting

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort
  • Shell Sort
  • Bucket or Radix Sort

Bubble Sort

  • Bubble sorting is a simple sorting technique in which we arrange the elements of the list by forming pairs of adjacent elements
  • Bubble Sort is an algorithm which is used to sort N elements that are given in a memory for eg: an Array with N number of elements.
  • Bubble Sort compares all the element one by one and sort them based on their values.
  • It is called Bubble sort, because with each iteration the smaller element in the list bubbles up towards the first place, just like a water bubble rises up to the water surface.
  • Sorting takes place by stepping through all the data items one-by-one in pairs and comparing adjacent data items and swapping each pair that is out of order.

Selection Sort

  • The selection sort technique is based upon the extension of the minimum/maximum technique.
  • Selection sorting is conceptually the simplest sorting algorithm.
  • This algorithm first finds the smallest element in the array and exchanges it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continues in this way until the entire array is sorted.
  • Selection sort is a simplicity sorting algorithm. It works as its name as it is. Here are basic steps of selection sort algorithm:
    • Find the minimum element in the list
    • Swap it with the element in the first position of the list
    • Repeat the steps above for all remainder elements of the list starting at the second position.

Advantages of Selection Sort

  • It is simple and easy to implement.
  • It can be used for small data sets.
  • It is 60 per cent more efficient than bubble sort.

Insertion Sort

  • An insertion sort is one that sorts a set of values by inserting values into an existing sorted file.
  • It is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. This algorithm is less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Advantages of Insertion Sort

The advantages of this sorting algorithm are as follows:

  • It is easy to implement and efficient to use on small sets of data.
  • It can be efficiently implemented on data sets that are already substantially sorted.
  • It performs better than algorithmslike selection sort and bubble sort. Insertion sort algorithm is simpler than shell sort, with only a small trade-off in efficiency. It is over twice as fast as the bubble sort and almost 40 per cent faster than the selection sort.
  • It requires less memory space (only O(1) of additional memory space).
  • It is said to be online, as it can sort a list as and when it receives new elements.

Quick Sort

  • It is one of the most popular sorting techniques. Quick sort possesses a very good average-case behaviour among all the sorting techniques. This is developed by C.A.R. Hoare.
  • Quick Sort, as the name suggests, sorts any list very quickly. Quick sort is not stable search, but it is very fast and requires very less additional space. It is based on the rule of Divide and Conquer (also called partition-exchange sort).
  • This algorithm divides the list into three main parts:
  • Elements less than the Pivot element
  • Pivot element
  • Elements greater than the pivot element

Merge Sort

  • Merge sort is a sorting technique which divides the array into subarrays of size 2 and merge adjacent pairs.
  • Merge Sort follows the rule of Divide and Conquer. But it doesn't divide the list into two halves.
  • In merge sort the unsorted list is divided into N sub lists, each having one element, because a list of one element is considered sorted.
  • Then, it repeatedly merge these sub lists, to produce new sorted sub lists, and at lasts one sorted list is produced.
  • Merge Sort is quite fast, and has a time complexity of O(n log n). It is also a stable sort, which means the equal elements are ordered in the same order in the sorted list.

Heap Sort

  • Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios.
  • Heap is a special tree-based data structure that satisfies the following special heap properties
  • Shape Property: Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled.
  • Heap Property: All nodes are either greater than or equal to or less than or equal to each of its children. If the parent nodes are greater than their children, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.

Shell Sort

  • Shell sort, invented by Donald Shell in 1959, is a sorting algorithm that is a generalization of insertion sort. While discussing insertion sort, we have observed two things:
    • First, insertion sort works well when the input data is ‘almost sorted’.
    • Second, insertion sort is quite inefficient to use as it moves the values just one position at a time.
  • Shell sort is considered an improvement over insertion sort as it compares elements separated by a gap of several positions. This enables the element to take bigger steps towards its expected position.
  • In Shell sort, elements are sorted in multiple passes and in each pass, data are taken with smaller and smaller gap sizes.

Radix Sort

  • The idea is to consider the key one character at a time and to divide the entries, not into two sub lists, but into as many sub lists as there are possibilities for the given character from the key.
  • If our keys, for example, are words or other alphabetic strings, then we divide the list into 26 sub lists at each stage.
  • That is, we set up a table of 26 lists and distribute the entries into the lists according to one of the characters in the key.