Selection Sort
Selection Sort Example- The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
- The algorithm maintains two subarrays in a given array: (a).The subarray which is already sorted. (b). Remaining subarray which is unsorted.
- In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
- It is very simple to implement but it does not go well with large number of inputs.
- In the above example we have a list of five numbers.
- In each iteration we will find the smallest element from the unsorted list and exchange it with the first element of unsorted list.
- In the first iteration, whole list is unsorted, we will find the smallest element, which is 2. Then we will put this smallest number (2) in the first position of unsorted list i.e we will exchange the position of 9 and 2. After the 1st iteration, we will have 2 subarrays: sorted array with one element i.e 2 and unsorted array with 9, 8, 12, 7.
- In the second iteration we will find the smallest number from the unsorted array (which is 7) and exchange it the first element of unsorted array i.e 9. After the 2nd iteration, sorted array will have 2, 7 and unsorted array will have 8, 12, 9.
- In the third iteration, we will again find the smallest number, in this case the smallest number (which is 8) is at the first position of unsorted array, so exchange is not required. After the 3rd iteration, sorted array will have 2, 7, 8 and unsorted array will have 12, 9.
- After the fourth iteration 9 will be exchanged with 12, and the size of unsorted array will become 1. At this point our list is sorted.
Insertion Sort
- Insertion sort works by comparing values at index with all its prior elements.
- All items to the left must be smaller. Since the first element does not have any prior element, so we can say its sorted.
- We will take second element, and then compare it with the prior element (that's the first one), if the 2nd one of less, we will swap it with 1st one.
- Lets take an example, we have a list of four numbers 7, 3, 1, 6.
- 7 is already sorted, we will take the 2nd number which is 3. We will compare 3 with the previous number (7), since 3 is less than we will interchange their positions, so now our list has 3,7,1,6.
- Now we will take the 3rd number (which is 1), compare it with the previous one (that's 7). Since 1 is less than 7, we will interchange their positions, so now our list has 3,1,7,6. Now there is one more element prior to 1 (which is 3), so we will compare them. SInce 1 is less than 3, so now our list has 1,3,7,6.
- Now we will take the 4th number and the last number (which is 6), compare it with the previous one (that's 7). 6 is less than 7, so now our list has 1,3,6,7. We will compare 6 with the previous number (3), since 3 is less than 6, we don't need to interchange their positions.
Bubble Sort
- Each element of the array is compared with its adjacent element. If the element on left is greater than element on the right, we need to swap them.We need do this recursively,each iteration places next larger value to its correct place.After every iteration, the largest element will be placed at the end of the list.
- The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting.
Write an Algorithm to merge two sorted lists?
- Lets say we have 2 lists A and B, both are sorted and now we want to merge them.
- Let's say the merged list is C. Size of C=size of A + size of B
- For merging, we need to maintain three pointers. i will point to the first element of A, j will point to the first element of B and k is for C.
- Now we will compare A[i] with B[j].
- If A[i] < B[j], we will copy A[i] at C[k], then we will increment i and k.
- If A[i] > B[j] or A[i]=B[j], we will copy B[j] at C[k], then we will increment j and k.
- At the end, elements of one the list will be finished, after that just copy the remaining elements of other list to list C.
- In the same way, we can merge n number of sorted lists.
Merge Sort
- There are two types of merge sorts, first one is '2-way merge sort' and second one is just 'merge sort'. The former is a iterative procedure, where are the later is recursive.
- This sort follows divide and conquer approach, in which we divide the problem into small parts, solve each part and then combine all the parts.
- Let's say you have an array and we want to sort it using merge sort. Since we have only one Array (lets say the size is 9), we will assume we have 9 arrays each having only one element. Since, each array has a single element, so it's already sorted. Now we will merge these 9 array list (with a single sorted element) into one list.
- We will start grouping 2 lists into one, since we have 9 lists after grouping we will have 4 lists (each with 2 elements) and one list with one element. While grouping we will sort them.
- Then again we will group 4 lists (each with 2 elements) into 2 (each with 4 elements in sorted order). Also, we will have one list with one element.
- Again, we will group 2 lists (each with 4 elements) into one list (with 8 elements in sorted order). Also, we will have one list with one element. Now we will merge these two lists.
MergeSort Example In Java
public class MergeSort {
public static void main(String a[]) {
int[] A = { 1, 10, 3, 9, 3, 4, 2, 8, 6, 0, -1};
System.out.println("Printing A...");
for (int x : A) {
System.out.print(x + " ");
}
System.out.println();
int[] mergedArray=mergeSort(A);
System.out.println("Printing mergSortedArray...");
for (int x : mergedArray) {
System.out.print(x + " ");
}
}
public static int[] mergeSort(int[] A)
{
int length =A.length;
if(length < =1)
return A;
int midpoint=length/2;
int[] left= new int[midpoint];
int[] right;
//if the array has even number of elements
if(length % 2==0)
right=new int[midpoint];
//if the array has odd number of elements
else
right=new int[midpoint+1];
for (int i=0;i
{
left[i]=A[i];
}
for (int j=0;j
{
right[j]=A[midpoint+j];
}
left=mergeSort(left);
right=mergeSort(right);
return merge(left, right);
}
public static int[] merge(int[] A, int[] B) {
int aSize = A.length;
int bSize = B.length;
int[] C = new int[aSize + bSize];
int i = 0, j = 0, k = 0;
while (i < aSize && j < bSize) {
if (A[i] < B[j])
C[k++] = A[i++];
else
C[k++] = B[j++];
}
// Copy the remaining elements-if present
for (; i < aSize; i++) {
C[k++] = A[i];
}
for (; j < bSize; j++) {
C[k++] = B[j];
}
return C;
}
}
Output:
Printing A...
1 10 3 9 3 4 2 8 6 0 -1
Printing mergSortedArray...
-1 0 1 2 3 3 4 6 8 9 10
What is Quick Sort?
A quick sort work on a idea, that an element is in sorted position if all the elements at the left have value lesser than that element and all the elements in the right have value greater than that element.
Let's take a couple of examples:
a). 10,80,90,60,30,20
Sorted Element: 10
b). 6,3,5,4,2,1,9
Sorted Element: 9
c). 4,6,7,10,16,12,13,14
Sorted Element: 10
- Like Merge Sort, QuickSort is a Divide and Conquer algorithm.
- A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
- Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays.
- There are many different versions of quickSort that pick pivot in different ways: (a). Always pick first element as pivot. (b). Always pick last element as pivot. (c). Pick a random element as pivot. (d). Pick median as pivot.
public class QuickSort {
public static void main(String args[]) {
int A[] = {10,7,11,7,0};
int n = A.length;
System.out.println("Input array");
printArray(A);
quickSort(A, 0, n-1);
System.out.println("sorted array");
printArray(A);
}
static void printArray(int A[]) {
for (int i = 0; i < A.length; ++i)
System.out.print(A[i] + " ");
System.out.println();
}
public static void quickSort(int[] A, int low, int high){
if (low < high){
int j=partition(A, low, high);
quickSort(A, low, j);
quickSort(A, j+1, high);
}
}
public static int partition(int A[], int low, int high) {
int pivot = A[low];
int i=low, j=high;
while(i < =j){
while (A[i] < pivot){
i++;
}
while (A[j] > pivot){
j--;
}
if (i < =j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
}
int temp = A[low];
A[low] = A[j];
A[j] = temp;
return j;
}
Time Complexity comparison of Sorting Algorithms
What is the best sorting algorithm for an almost sorted array?
Insertion sort is best suited for the almost sorted array. The time complexity of an insertion sort is O(n) for almost sorted data.
-K Himaanshu Shuklaa..
No comments:
Post a Comment