Sorting Techniques.

There are different types of sorting techniques available they are:-


A)Internal Sorting b) External Sorting (Sorting algorithms that use external memory)


***********************
PART-1
***********************
1)Selection sort
2)Bubble sort
3)Insertion sort
4)Quick sort - (Divide and Conquer)
5)Merge sort - (Divide and Conquer)
6)Heap sort - (Not divide and conquer)
***********************
PART- 2(Linear Sorting Algorithms)
***********************
in earllier sections we have seen many examples on comparison based sorting algorithms. among them the best comparison- based sorting has the complexity O(nLogn). This linear sorting algorithms improve time complexity of these sorting algorithms. We can improve the complexity up to O(n). Few examples of Linear sorting algorithms are shown below.

1)Counting sort
2)Bucket sort
3)Radix sort

************************



Good resource for comparing complexities:

http://bigocheatsheet.com/

-----------------------------------------------------------------------------------------


PART -1
-->>Sorting — arranging items in order — is the most fundamental task in computation. Sorting enables efficient searching algorithms such as binary search.

-->>Selection, insertion and bubble sort are easily understandable and also similar to each other, but they are less efficient than merge sort or quick sort. The basic ideas are as below:

• Selection sort: repeatedly pick the smallest element to append to the result.
• Bubble sort: repeatedly compare neighbor pairs and swap if necessary.
• Insertion sort: repeatedly add new element to the sorted result.

For Insertion Sort refer:http://cforbeginners.com/insertionsort.html

Quick Riview of complexities of above sorting techniques:----
***********************
SELECTION SORT:

Suppose the input array has n elements. The outer loop runs n-1 rounds, roughly one for each position. Inside each outer loop, the inner loop goes through the unsorted part of the array. On average, each inner loop scans through n/2 elements. The total time is roughly t(n) = (n – 1) * (n/2) *k = O(n^2), where k denotes the number of basic operations inside each inner loop; the constants are absorbed in the big-Oh notion. Note that in the big-Oh notion, we only care about the dominating factor (which is n^2 in this case).

Code:

for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(a[i]>a[j])
{
swap(a[i],a[j]);
}
}
}


************************
BUBBLE SORT:

Bubble sort repetitively compares adjacent pairs of elements and swaps if necessary.

Scan the array, swapping adjacent pair of elements if they are not in relative order. This bubbles up the largest element to the end.
Scan the array again, bubbling up the second largest element.
Repeat until all elements are in order.
The following bubbleSort() method implements bubble sort. It uses a nested loop to repetitively swap elements and bubble up the largest elements one by one.

code:

public static void bubbleSort (int[] data)
{
for (int i = data.length - 1; i >= 0; i--)
{
// bubble up
for (int j = 0; j <= i - 1; j++)
{
if (data[j] > data[j + 1])
swap(data, j, j + 1);
}
}
}
Suppose the array length is n. The outer loop runs roughly n times, and the inner loop on average runs n/2 times. The total time is about t(n) = n * (n/2) = O(n^2). In terms of the efficiency, this is the same as selection sort and insertion sort.
************************
INSERTION SORT:
Insertion sort maintains a sorted sub-array, and repetitively inserts new elements into it. The process is as following:
Take the first element as a sorted sub-array.
Insert the second element into the sorted sub-array (shift elements if needed).
Insert the third element into the sorted sub-array.
Repeat until all elements are inserted.
The following insertionSort() method implements insertion sort. It uses a nested loop to repetitively insert elements into the sorted sub-array.

code:

void insertion_sort (int arr[], int length){
int j, temp;

for (int i = 0; i < length; i++){
j = i;

while (j > 0 && arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
}
Suppose the array length is n. The outer loop runs roughly n times, and the inner loop on average runs n/2 times. The total time is about t(n) = n * (n/2) = O(n^2). In terms of the efficiency, this is the same as selection sort.
PRACTICALLY INSERTION SORT IS MORE EFFICIENT THAN SELECTION AND BUBBLE SORTS EVEN TOUGH ALL OF THEM HAVE SAME O(N^2) COMPLEXITIES.


*************************