Sorting Basics

Sorting allows an efficient arrangement of elements within a given data structure. It is a way in which the elements are organized systematically for some purpose. For example, a dictionary in which words are arranged in alphabetical order and telephone director in which the subscriber names are listed in alphabetical order. There are many sorting techniques out of which we study the following:

• Bubble sort 
• Quick sort 
• Selection sort  
• Heapsort

Sorting refers to the operation of arranging data in some given order, such as increasing or decreasing with numerical data or alphabetically with character data.

COMMON SORTING STRATEGIES:

One way of organizing the various sorting algorithms is by classifying the underlying idea, or `strategy'. Some of the key strategies are:

• Enumeration sorting: Consider all items. If we know that there are N items which are smaller than the one we are currently considering, then its the final position will be a number N + 1.
• Exchange Sorting If two items are found to be out of order, exchange them. Repeat till all items are in order. TYPE: Bubble Sort 
• Selection Sorting Find the smallest item, put it in the first position, nd the smallest of the remaining items put it in the second position.  TYPE: Selection sort, Heap Sort.
• Insertion Sorting Take the items one at a time and insert them into an initially empty data structure such that the data structure continues to be sorted at each stage.  TYPE: Insertion sort
• Divide and Conquer Recursively split the problem into smaller sub-problems till you just have single items that are trivial to sort. Then put the sorted `parts' back together in a way that preserves the sorting.  TYPE: Merge Sort.

All these strategies are based on comparing items and then rearranging them accordingly. These are known as comparison-based sorting algorithms.