What is Sorting and its types and explanation of each type Bubble Insertion Selection Quik Merge Heap


#1

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
Class
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.

Types of Sorting Techniques

There are many types of Sorting techniques, differentiated by their efficiency and space requirements. Following are some sorting techniques which we will be covering in next sections.

Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort


#2

Bubble sort:

7 5 4 2 9
compare adjacent,swap if a[i] > a[i + 1],basically finding maximum element.
7 > 5 (swap)

5 7 4 2 9
7>4 ( Swap)

5 4 7 2 9
(7 > 2) swap

5 4 2 7 9
(7 <9) dont swap

so after 1 iteration

5 4 2 7 9
now 9 is at its correct position,we have found the maximum,now repeat the procedure for n - 1 elements.

Complexity : 0 (n^2).

Insertion Sort

7 5 4 2 9

start from 5 ,compare to the element to its left.
5 <7 (swap)

5 7 4 2 9

4<7 (swap)

5 4 7 2 9

compare 4 and 5 ,4 < 5 swap

4 5 7 2 9

compare 2 with 7 ,swap.

4 5 2 7 9

compare 2 with 5 swap

4 2 5 7 9

compare 2 with 4 swap

2 4 5 7 9

compare 9 with 7 ,no swap needed and there is no need to check with 5 4 2,because the array on the left at any point is sorted (Proof ?)

Best case complexity of Insertion sort??
Best case sample example??

Merge Sort:

7 5 4 2 9

array is divided into 2 sub arrays

7 5 4
2 9

7 5 4 further divided into

7
5 4

5 4 will be further divided into 2 array
5
4

when there is only one element left start comparing,compare 4 with 5

new array will be
4 5

now we have two array
7
4 5

like previous compare

new array 4 5 7

2 9
divided into
2
9

new array 2 9

finally have two arrays

4 5 7
2 9 (both sorted)

final array-> 2 4 5 7 9


#3

Sorting is a method of organizing data in a particular order which may be increasing or decreasing.
There are several types of sorting:

  1. Bubble sort
  2. Insertion sort
  3. Selection sort
  4. Radix sort
  5. Counting sort
  6. Merge sort
  7. Quick sort