January 2013 - Coding Bot

# Bubble Sort Algorithm And C Code

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists. Bubble sort is not a stable sort which means that if two same elements are there in the list, they may not get their same order with respect to each other.

### Step-by-step example:

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.
First Pass:
5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )

### Algorithm For Bubble Sort:

/* Double-Click To Select Code */

Step 1: Repeat Steps 2 and 3 for i=1 to 10

Step 2: Set j=1

Step 3: Repeat while j<=n

(A) if  a[i] < a[j]

Then interchange a[i] and a[j]

[End of if]

(B) Set j = j+1
[End of Inner Loop]

[End of Step 1 Outer Loop]

Step 4: Exit


Optimized Algorithm For Bubble Sort:

/* Double-Click To Select Code */

procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
swapped = true
end if
end for
n = n - 1
until not swapped
end procedure


## C Program For Bubble Sort:

/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>
void main()
{
int i,n,temp,j,arr;
clrscr();
printf("Enter the number of elements in the Array: ");
scanf("%d",&n);
printf("\nEnter the elements:\n\n");

for(i=0 ; i<n ; i++)
{
printf(" Array[%d] = ",i);
scanf("%d",&arr[i]);
}

for(i=0 ; i<n ; i++)
{
for(j=0 ; j<n-i-1 ; j++)
{
if(arr[j]>arr[j+1]) //Swapping Condition is Checked
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}

printf("\nThe Sorted Array is:\n\n");
for(i=0 ; i<n ; i++)
{
printf(" %4d",arr[i]);
}
getch();
}


## Output of Program:

Please Comment If You Liked This Post !!

# Quick Sort Algorithm And C Code

Quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items.  It was developed by Tony Hoare. Quicksort is faster in practice than other O(n log n) algorithms such as Bubble sort or Insertion Sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.
Quicksort is a comparison sort and is not a stable sort.

Its complexity is as follows:
Best Case - O(n log n)
Worst Case - O(n^2)
Average Case - O(n log n)

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.

### Algorithm/Pseudo-code For Quicksort:

/* Double-Click To Select Code */

function quicksort('array')
if length('array') ≤ 1
return 'array'  // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater'))
// two recursive calls

### Here is an Image depicting Quick Sort: In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.

### C Program For Quick Sort:

/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>

void quick_sort(int arr,int,int);

void main()
{
int arr,n,i;
clrscr();
printf("Enter the number of elements in the Array: ");
scanf("%d",&n);
printf("\nEnter %d elements:\n\n",n);

for(i=0 ; i<n ; i++)
{
printf(" Array[%d] = ",i);
scanf("%d",&arr[i]);
}

quick_sort(arr,0,n-1);
printf("\nThe Sorted Array is:\n\n");

for(i=0 ; i<n ; i++)
{
printf(" %4d",arr[i]);
}
getch();
}

void quick_sort(int arr,int low,int high)
{
int pivot,j,temp,i;
if(low<high)
{
pivot = low;
i = low;
j = high;

while(i<j)
{
while((arr[i]<=arr[pivot])&&(i<high))
{
i++;
}

while(arr[j]>arr[pivot])
{
j--;
}

if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}

temp=arr[pivot];
arr[pivot]=arr[j];
arr[j]=temp;
quick_sort(arr,low,j-1);
quick_sort(arr,j+1,high);
}
}


### Output of Program:

Please Comment If You Liked This Post !!

# Merge Sort Algorithm And C Code

Merge sort is a sorting technique, which is  based on comparison sorting algorithm, having complexity O(n log n). It is one of the types of stable sort, meaning, that in its implementation, input order of equal elements is preserved in the sorted output.  It was invented by John von Neumann in 1945. Merge sort is a divide and conquer algorithm.

The concept of Merge Sort is based on the following principle:

Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.

## Algorithm for Merge Sort:

/* Double-Click To Select Code */

function merge_sort(list m)
// if list size is 0 (empty) or 1, consider it sorted and return it
// (using less than or equal prevents infinite recursion for a zero length m)
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
for each x in m after or equal middle
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)

In this example, the merge function merges the Left and Right sublists.

/* Double-Click To Select Code */

function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result


## Here is the C Code for Merge Sort:

/* Double-Click To Select Code */

#include <stdio.h>
#include<conio.h>

void mergesort(int arr[], int l, int h);

void main(void)
{
int array,n,i = 0;
clrscr();
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
printf("\nEnter the elements to be sorted: \n");
for(i = 0 ; i < n ; i++ )
{
printf("\tArray[%d] = ",i);
scanf("%d",&array[i]);
}

printf("\nBefore Mergesort:");  //Array Before Mergesort
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");

mergesort(array, 0, n - 1);

printf("\nAfter Mergesort:");  //Array After Mergesort
for(i = 0; i < n; i++)
{
printf("%4d", array[i]);
}
printf("\n");
getch();
}

void mergesort(int arr[], int l, int h)
{
int i = 0;
int length = h - l + 1;
int pivot  = 0;
int merge1 = 0;
int merge2 = 0;
int temp;

if(l == h)
return;

pivot  = (l + h) / 2;

mergesort(arr, l, pivot);
mergesort(arr, pivot + 1, h);

for(i = 0; i < length; i++)
{
temp[i] = arr[l + i];
}

merge1 = 0;
merge2 = pivot - l + 1;

for(i = 0; i < length; i++)
{
if(merge2 <= h - l)
{
if(merge1 <= pivot - l)
{
if(temp[merge1] > temp[merge2])
{
arr[i + l] = temp[merge2++];
}

else
{
arr[i + l] = temp[merge1++];
}
}

else
{
arr[i + l] = temp[merge2++];
}
}

else
{
arr[i + l] = temp[merge1++];
}
}
}


### Output of Program:

Please Comment If You Liked This Post !!