Merge Sort

 First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.


Efficiency

• Worst case performance     O(n log n)
• Best case performance   O(n log n)
• Average case performance     O(n log n)

Insertion Sort Method

This method sorts the data by inserting value into its proper poistion.

The steps used in this method are

Step 1: A1 itself is sorted.

Step 2: Compare A2 with A1

• In case of ascending order ,  

  A2 <= A1 if yes then x = A2 ; A2 = A1 ; A1 = x

                             if no 'No Change'

• In case of descending order

    A2 >= A1 if yes then x = A2 ; A2 = A1 ; A1 = x

                             if no 'No Change'

Step 3: Compare A3 with A1 and A2

• In case of ascending order ,  

  A3 <= A1  or A3<= A2  

  then insert A3 in that postion where the condition holds true (first) , 

          otherwise 'No Change'

• In case of descending order

   A3 >= A1  or A3>= A2  

  then insert A3 in that postion where the condition holds true (first) , 

          otherwise 'No Change'

.

.

.

.

Step n : Compare An with A1, A2, A3 ... An-1 

• In case of ascending order ,  

  An <= A1  or An<= A2  or ... An <= An-1 

  then insert An in that postion where the condition holds true (first) , 

          otherwise 'No Change'

• In case of descending order

    An >= A1  or An>= A2  or ... An >= An-1 

  then insert An in that postion where the condition holds true (first) , 

          otherwise 'No Change'

Complexity 

• Worst Case : n(n-1)/2 = o(n²)
• Average Case : n(n-1)/4 = o(n²)

Algorithm

1. For step= 1 to n
    Set temp=a[step]
    Set i=step-1
    while temp=0)
            Set a[i+]=a[i]
    end while
    Set a[i+1]=temp
   End For
2. Print Sorted Data
3. Exit

Quick Sort Method

Quick Sort Method

Description: 
Also known as Partition Exchange Method because it sorts data by partitioning the the array / list into two sub arrays / lists. Each partition is in turn sorted recursively. In each step, the goal is
to place a particular data known as key in its final position. In general, key element is the first data of an array / list and rest of the data grouped into  such that

i. One partition contains data smaller than the key value.

ii. Another partition contains data larger the key value.

Example:

Consider following elements, the quick sort
method to sort data in ascending order is

44,33,11,55,77,90,40,60,99,22,88,66

Step 1: Key is 44.
The First step is as follows

i. Scan: Right to Left

• stop when find first number less than key, 44
• 22
• Data after interchange: 22,
  33,11,55,77,90,40,60,99,44,88,66

ii. Left to Right

• stop when find first number greater than key, 44
• 55
• Data after interchange:: 22,33,11,44,77,90,40,60,99,55,88,66

iii. Right to Left

• stop when find first number less than key, 44
• 40
• Data after interchange:: 22, 33,11,40,77,90,44,60,99,55,88,66

iii. Left to Right

• stop when find first number greater than key, 44
• 77
• Data after interchange:: 22,33,11,40,44,90,77,60,99,55,88,66

so the list can be partitioned into two sub list

Sub Part 1: 22,33,11,40. 

Sub Part 2: 90,77,60,99,55,88,66.  

Step 2: Repeat
same steps on Sub Part1 with
key as 22

Step 3: Repeat
same steps on Sub Part2 with
key as 99

and so on

Efficiency:

• Worst Case:: O(n²) 
• Best case performance    O(n log n)  
• Average case performance    O(n log n)

Algorithm

Quicksort (int data[],int left,int right) 

{

int mid,tmp,i,j;

i = left;

j = right;

mid = data[(left + right)/2];

do 

{

     while(data[i] < mid)

         i++;

      while(mid < data[j])

         j--;

      if (i <= j) 

     {

            tmp = data[i];

            data[i] = data[j];

            data[j] = tmp;

            i++;

            j--;

     }

} while (i <= j);

   

if (left < j) Quicksort(data,left,j);

if (i < right) Quicksort(data,i,right);

}

Bubble Sort Method

In bubble sort element, each element is compared with its adjacent element  and if first element is greater than second element  then elements are interchanged otherwise no change. This process is repeated for all the elements in the list.

Compelxity

• Worst Case: n(n-1)/2 = o(n²)
• Best case performance     O(n)
•  Average case performance     o(n²) 

Algorithm:  Given array A of N elements.


1. Repeat thru step 2 for STEP=1 to N
2. [Compare adajanct elements]     Repeat for i=1 to N-1
         if a[i]>a[i+1]
         then swap
3. Print Sorted data
4. Exit

Selection Sort Method

The steps to sort data using selection sort method are

Consider A is an list / array of n elements

Step 1:  Find the postion of smallest element from A1 to An and then interchage the element of that location  with A1. 

Step 2: Find the postion of smallest element from A2 to An and then interchage the element of that location  with  A2.

Step 3: Find the postion of smallest element from A3 to An and then interchage the element of that location  with  A3.

.

.

.

Step n: Find the postion of smallest element from An to An and then interchage the element of that location  with  An.

Complexity

• Worst Case: n(n-1)/2 = o(n²)
  
• Average Case: n(n-1)/2 = o(n²)
• Best Case: n(n-1)/2 = o(n²) 

Algorithm: Given A is an array of N elements. POS denoted the position of smallest element

1. Repeat thru step 4 for STEP=1 to N
2. POS=STEP
3. [for Asce order find position of smallest element]
    Repeat for i=STEP+1 to n
       if A[i]       then POS=i
4. [Swap]
     if POS<> step
     then  temp=a[setp]
              a[step]=a[POS]
              a[POS]=temp
5. Print Sorted Data
6. Exit