# Sorting and searching in data structure

# What is Sorting?

Sorting is the process of ordering a list of objects, according to some linear order, such as £ for numbers.

Sorting can be divided into two types i.e. **internal** and **external**.

**Internal** sorting takes place in main memory of the computer, where we can make use of its random access nature.

**External** sorting is necessary when the number of objects to be sorted is too large to fit in the main memory.

For external sorting, the bottleneck is usually the data movement between the secondary storage and the main memory.

Data movement is efficient if it is moved in the form of large blocks.

However, moving large blocks of data is efficient only if it is physically located in contiguous locations.

The simplest algorithms usually take *O(n**2**)* time to sort *n* objects, and suited for sorting short lists.

Insertion sort takes *O(n**2**) but *if the input is pre-sorted running time takes O(N) time.

One of the most popular algorithms is Quick-Sort takes *O(**n*log*n**)* time on average.

Quick-Sort works for most common applications, although in worst case it can take time *O(n**2**)* .

There are other sorting techniques, such as Merge-Sort that take time *O(**n*log*n**)* in worst case.

Merge-Sort however, is well suited for external sorting.

- sorted sub files are combined into a single larger file!

There are other algorithms such as “bucket” and “radix” sort when the keys are integers of known range. They take time O(n).

The sorting problem is to arrange a sequence of records so that the values of their key fields form a ascending/descending sequence.

The records may NOT have distinct values, and can appear in any order.

There are many criterion to evaluate the running time, as follows:

- Number of algorithm steps.
- Number comparisons between the keys (for expensive comparisons).
- The number of times a record is moved (for large records).

Related links

Single link list Stack AVL Trees Binary search Counting Sort

Doubly link list Queue Graphs Bubble Sort Radix sort

Circular link list Binary search tree Hashing Insertion Sort Bucket Sort

Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort

## At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses #Finalyearproject