Sorting:

Sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order.

Sorting algorithm classification:

Computaional complexcity.

Memory utilization

Stability-Maintaining relative order of records with equal keys.

No.of comparisions

Methods applied like insertion,exchange, selection,merging etc.

Sorting is a process of linear ordering of list of objects

Sorting techniques are categoried into:

1. Internal sorting

2. External sorting

Internal sorting:

It takes the place in the main memory of a computer.

                 Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc

External sorting:

It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory.

                Eg:Merge sort,Multiway Merge,Polyphase merge.

Quick Sort:

Qiuck sort is the most efficient internal sorting technique.It posseses a very good average case behaviour among all the sorting techniques.It is also called partioning sort which uses divide and conquer techniques.
       
Definition:

Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

• Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.
• Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

Analysis of the quick sort:

• Worest case performance O(n2)
• Best case performance O(n log n)
• Average case performance O(n log n)

Advantages of quick sort:

• It is faster than other O(N log N) algorims.
• It has better cache performance and high speed.

Limitation:

 Requires More Memory space.

Algorithm steps:

• Pick an element, called a pivot, from the list.

• Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

• Recursively sort the sub-list of lesser elements and the sub-list of greater elements.