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(n2) time to sort n objects, and suited for sorting short lists.

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

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

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

There are other sorting techniques, such as Merge-Sort that take time O(nlogn) 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