Introduction to Sorting Algorithm

Introduction to Sorting Algorithms

As we are already familiar with the definition of data structures and their various types, it is now time to learn about the operations that are performed on data structures.

Four major operations are performed on data structures

• Sorting
• Searching
• Merging
• Insertion

These four operations also have various types under them. First and foremost we will start with Sorting and types of sorting.

SORTING

It is a technique to arrange the elements of the list in a particular order either in ascending or descending order. Efficient sorting is important to optimize the use of other algorithms such as search & merge that need a sorted list to work correctly.

Internal Sorting

It refers to a data sorting process that happens entirely within the main memory of a computer. This is possible only when data to be sorted is small enough to fit in the main memory. For sorting large data, the main memory can hold only a part of the data at a time and stores the rest of the data on a larger but slower medium like hard disks. Few types of internal sorting methods are:

• Selection Sort
• Bubble Sort
• Insertion Sort
• Quick Sort
• Heap Sort

External Sorting

Algorithms of this sorting class can hold massive data. External sorting is done when the main memory of the computing device is unable to hold the size of the data, generally RAM.

A classic example of using external sort is when data to be sorted is as big as the GPA of students and is to be sorted in increasing order. The problem here is how we sort 1 GB of data on 1 MB of RAM.

Merge Sort is an example of external sorting.