SORTING

The process of arranging the elements in ascending or descending order is called sorting.  There are several sorting algorithms. They differ in their efficiency and speed.

Bubble Sort:

            The bubble sort technique starts with comparing the first two data items of an array and swapping these two data items if they are not in a proper order i.e. in descending or ascending order. This process continues until all the data items in the array are compared or the end of an array is reached.

In general, where N is the number of items in an Array, there are N-1 comparisons on first pass, N-2 on second and so on, the formula for the sum of such a series is (n-1)+(n-2) …+1 = N*(N-1)/2 . The algorithm involves both swaps and comparisons are proportional to O (n²).

Procedure:

for I=0 to n-2 in step of 1 do             begin                  for j=1 to n-i in step of 1 do                         if aj-1 > aj then aj-1 ↔ aj             end endfor

for (int i=a.length;i>1;i--)             for (int j=0;j<i-1;j++)                     if (a[j].compareTo(a[j+1]) >0)                              {                                  t=a[j];                                  a[j]=a[j+1];                                  a[j+1]=t;                                }

Selection Sort:

            Selection sort is based on finding the smallest (or largest) element in the list and placing it at the first position. Then the next smallest (or largest) element is found and placed it at the second position, and so on this process continues till the array is sorted.

            The selection sort can be significant improvement for large records that must be physically moved around in memory, causing the swap time to be much more important than the comparison time.

 Therefore, the algorithm requires the list to be scanned n-1 times. When compare to bubble sort, it reduces the number of swaps i.e. O(n). The total number of comparisons are, (n-1) + (n-2) + (n-3) + … 1 = n(n-1)/2 . Thus, the complexity of this algorithm is O(n²).

Procedure:

for I=0 to n-2 in step of 1 do             begin                  k ←I                  for j=I+1 to n-1 in step of 1 do                         if ak > aj then  k ←j                  if k not = I then ak ↔ aI             end       end for

for (int i=list.length;i>1;i--) {             int j = max(list,i);             t = list[j];             list[j] = list[i-1];             list[i-1] = t; }

Insertion Sort:

            Insertion sort sorts data at the time of insertion. We are to insert a new element into a sorted array so that the result is also a sorted array.  The insertion may be beginning at the right end and successively moving array elements one position right until we find the location for new element.

            The complexity of the insertion sort algorithm to sort n numbers is O(n²). It is about twice as fast as the bubble sort and somewhat faster than the selection sort.  

Procedure:

Element inserting into an array read num j= p while  a[j]>num and j>=0 do              a[j+1] = a[j]               j=j-1;        end for a[j+1]=num p = p+1

// element ‘a’ insert into proper position ‘p’, initially p value is -1 for(j=p;j>=0 && a.compareTo(list[j]) < 0;j--)                 list[j+1] = list[j]; list[j+1] = e; p++;

Quick Sort (or partition exchange sort):

Quick sort was discovered by C.A.R. Hoare in 1962. Quick sort uses the “divide-and-conquer” method for sorting. This sorting technique sorts the elements of an array faster than any other sorting technique. The complexity of this sorting method is O(n log n). It does not support for sorting data in disk files.

            In this method the ‘N’ elements to be sorted are partitioned into three segments (or groups):

·        A left segment

·        A middle segment

·        A right segment

1. The middle segment contains exactly one element
2. The element in middle is called the “Pivot” or partitioning element
3. No element in left has a key larger than the key of the element in middle
4. No element in right has a key that is smaller than the key of the middle element
5. The elements in left and right can be sorted independently 

Procedure:

void QuickSort(int left, int right) {  if(right – left <= 0) return; else { int p = partition(left, right); QuickSort(left, p-1); QuickSort(p+1, right); } } int partition(int left, int right) {                 int leftPtr = left -1;                 int rightPtr = right;

Object pivot = list[right];                 Comparable p = (Comparable) pivot;                 while(true)                 {                 while( p.compareTo(list[++leftPtr]) > 0);                 while(rightPtr >0 &&         p.compareTo(list[--rightPtr]) < 0);                 if(leftPtr >= rightPtr) break;                 else                 swap(leftPtr, rightPtr);                 }                 swap(leftPtr, right);                 return leftPtr; }