SORTING TECHNIQUES

SORTING ALGORITHMS

Sorting is the process that organizes the collection of data either in ascending or descending order.

there will be two sorting process.They are

   1.Internal sorting
   2.External sorting

Internal sorting:
  Internal sorting is the process in which sorting is to be done within the computer's memory.
  External sorting needs externa memory such as HardDisks for sorting process.

There are many sorting algorithms:

  1.Insertion sort
  2.Selection sort
  3.Bubble sort
  4.Merge sort
  5.Quick sort

Selection sort:
In the list is divided into two sublists, sorted and unsorted.

We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data.

Each time we move one element from the unsorted sublist to the sorted sublist, we say that we have completed a sort pass.

A list of n elements requires n-1 passes to completely rearrange the data.

A list of n elements require n-1 passes to arranging the data. 

Bubble sort:

In the list is divided into two sublists, sorted and unsorted.

The smallest element is bubbled from the unsorted list and move the element at the beginning of the sorted sublist.

Each time we move one element from the unsorted list to the sorted sublist, we say that we have completed a sort pass.

A list of n elements requires n-1 passes to completely rearrange the data.

A list of n elements require n-1 passes to arranging the data. 

 

comparision:

Selection sort:
Worst scenario: O(n2);
Average scenario: O(n2);
Best scenario: O(n2);

Bubble sort:
Worst scenario: O(n2);
Average scenario: O(n2);
Best scenario: O(n2);

Modified Bubble sort:

Worst scenario: O(n2);
Average scenario: O(n);
Best scenario: O(n);

The selection sort and bubble sort performance wise both are same.But the method of sorting is different with each other.

The difference between the bubble sort and modified bubble sort is modified bubble sor tis decreasing the number of steps used for sorted process.

Insertion sort.

In this method, sorting is done by inserting elements into an existing sorted list.
Initially, the sorted list has only one element.
Other elements are gradually added into the list in the proper position.

Merge Sort:

Merge sort is one of the Sorting Technique which is based on divide and conquer mechanism.

In this method,initially then given  elements are partially divided,and again they divided using recursive method.

After partioning of elements the first half and second half of the elements sorted seperatedly and then they have merged together.

Application of Merge Sort:

1.It can handle large amount of data and process it quickly.

2.It is also used to merge the two sorted lists.

Quick sort:

Quick sort is a most efficient algorithm as compared to selection or bubble sort.

It works by first of all by partitioning the array around a pivot value and then dealing with the 2 smaller partitions separately.

 

Partitioning is the most complex part of quick sort.

The simplest thing is to use the first value in the array,  as the pivot.

After the partitioning, all values to the left of the pivot are <= pivot

and all values to the right are > pivot.This gives better performance.

The approach of Quick sort is called Depth fast approach.

Best case running time of quick sot is O(n log2 n).

Worst case is O(n2).