Thursday 6 March 2014
Program of Exchange Sort
// C Program to shuffle a given array
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// A utility function to swap to integers
void swap (int *a, int
*b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// A utility function to print an array
void printArray (int arr[], int
n)
{
for (int i = 0; i < n; i++)
printf("%d
", arr[i]);
printf("\n");
}
// A function to generate a random
permutation of arr[]
void randomize ( int arr[], int
n )
{
// Use a different
seed value so that we don't get same
// result each time
we run this program
srand ( time(NULL) );
// Start from the
last element and swap one by one. We don't
// need to run for
the first element that's why i > 0
for (int i = n-1; i > 0; i--)
{
//
Pick a random index from 0 to i
int j = rand() % (i+1);
//
Swap arr[i] with the element at random index
swap(&arr[i],
&arr[j]);
}
}
// Driver program to test above function.
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = sizeof(arr)/ sizeof(arr[0]);
randomize (arr, n);
printArray(arr, n);
return 0;
Program of Cocktail Sort
|
void shaker(char *items, int
count)
|
|||
|
{
|
|||
|
08
|
register int
a;
|
|
|
09
|
int exchange;
|
|
|
10
|
char t;
|
|
|
11
|
|
|
|
12
|
do {
|
|
|
13
|
exchange
= 0;
|
|
|
14
|
for(a=count-1;
a > 0; --a) {
|
|
|
15
|
if(items[a-1]
> items[a]) {
|
|
|
16
|
t
= items[a-1];
|
|
|
17
|
items[a-1]
= items[a];
|
|
|
18
|
items[a]
= t;
|
|
19
|
exchange
= 1;
|
|
20
|
}
|
|
|
21
|
}
|
|
|
22
|
|
|
|
23
|
for(a=1;
a < count; ++a) {
|
|
|
24
|
if(items[a-1]
> items[a]) {
|
|
|
25
|
t
= items[a-1];
|
|
|
26
|
items[a-1]
= items[a];
|
|
|
27
|
items[a]
= t;
|
|
|
28
|
exchange
= 1;
|
|
|
29
|
}
|
|
|
30
|
}
|
|
|
31
|
} while(exchange);
/* sort until no exchanges take place */
|
|
|
32
|
}
|
|
|
33
|
|
|
|
34
|
int main(void)
|
|
|
35
|
{
|
|
|
36
|
|
|
|
37
|
char s[255];
|
|
|
38
|
|
|
|
39
|
printf("Enter
a string:");
|
|
|
40
|
gets(s);
|
|
|
41
|
shaker(s,
strlen(s));
|
|
|
42
|
printf("The
sorted string is: %s.\n", s);
|
|
|
43
|
|
|
|
44
|
return 0;
|
|
|
45
|
}
|
|
Program of Selection Sort
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for ( c = 0 ; c < n ; c++ )
scanf("%d", &array[c]);
for ( c = 0 ; c < ( n - 1 ) ; c++ )
{
position = c;
for ( d = c + 1 ; d < n ; d++ )
{
if ( array[position] > array[d] )
position = d;
}
if ( position != c )
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
printf("Sorted list in ascending order:\n");
for ( c = 0 ; c < n ; c++ )
{
printf("%d\n", array[c]);
return 0;
}
Program of RadixSort
void radixSort(vector<int>& a, int base)
{
int const MAX = 10;
static vector<int> buckets[MAX];
int pow = 1;
for (int i = 0; i < MAX; ++i)
{
buckets[i].resize(a.size());
buckets[i][0] = 0;
}
for (int i = 0; i < base; ++i, pow *= 10)
{
for (int j = 0; j < MAX; ++j)
{
buckets[j][0] = 0;
}
for (int j = 0; j < a.size(); ++j)
{
int index = (a[j] / pow) % 10;
buckets[index][++buckets[index][0]] = a[j];
}
int cnt = 0;
for (int j = 0; j < MAX; ++j)
{
for (int k = 0; k < buckets[j][0]; ++k)
{
a[cnt++] = buckets[j][k + 1];
}
}
}
}
void RadixSort(int A[], int size)
{
int d = 1;
for(int i = 0; i < size; ++i)
{
int digits_temp;
digits_temp=(int)log10(abs(A[i]!=0 ? abs(A[i]) : 1)) +1;
if(digits_temp > d)
d = digits_temp;
}
d += 1;
*rest of the implementation*
{
{
int const MAX = 10;
static vector<int> buckets[MAX];
int pow = 1;
for (int i = 0; i < MAX; ++i)
{
buckets[i].resize(a.size());
buckets[i][0] = 0;
}
for (int i = 0; i < base; ++i, pow *= 10)
{
for (int j = 0; j < MAX; ++j)
{
buckets[j][0] = 0;
}
for (int j = 0; j < a.size(); ++j)
{
int index = (a[j] / pow) % 10;
buckets[index][++buckets[index][0]] = a[j];
}
int cnt = 0;
for (int j = 0; j < MAX; ++j)
{
for (int k = 0; k < buckets[j][0]; ++k)
{
a[cnt++] = buckets[j][k + 1];
}
}
}
}
void RadixSort(int A[], int size)
{
int d = 1;
for(int i = 0; i < size; ++i)
{
int digits_temp;
digits_temp=(int)log10(abs(A[i]!=0 ? abs(A[i]) : 1)) +1;
if(digits_temp > d)
d = digits_temp;
}
d += 1;
*rest of the implementation*
{
program of Quick Sort
#include<stdio.h>
#include<conio.h>
void
qsort(int, int, int) ; //Prototype
int main( )
{
int arr[30];
int i, size ;
printf("Enter total number of
Elements: ") ;
scanf("%d", &size);
printf("Enter the Elements: \n")
for(i=0; i<size; i++)
scanf("%d", &arr[i]) ;
qsort(arr, 0, size-1) ; //calling
printf("Quick Sorted elements are
as: \n") ;
for(i=0; i<size; i++)
printf("%d\t",arr[i]);
return 0;
}
void qsort(int
arr[20], int frst, int last)
//definition
{
int i, j, pivot, tmp;
if(frst<last)
{
pivot=frst ;
i=frst ;
j=last;
while(i<j)
{
while(arr[i]<=arr[pivot]
&& i<last)
i++ ;
while(arr[j]>arr[pivot])
j-- ;
if(i<j)
{
tmp=arr[i];
arr[i]=arr[j] ;
arr[j]=tmp;
}
} //end of while loop
tmp=arr[pivot] ;
arr[pivot]= arr[j];
arr[j]=tmp ;
qsort(arr,frst,j=1) ;
qsort(arr, j+1, last) ;
} //end of if statement
}
Program of MergeSort
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
m_sort(numbers, temp, 0, array_size - 1);
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right >
left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
Program of Cycle Sort
#include
<stdio.h>
#define
MAX 8
void cycle_sort(int
*);
void main()
{
int a[MAX],i;
printf("enter
the elements into array :");
for (i = 0;i <
MAX; i++)
{
scanf("%d", &a[i]);
}
cycle_sort(a);
printf("sorted elements are :\n");
for (i = 0;i <
MAX; i++)
{
printf("%d", a[i]);
}
}
/* sorts elements using cycle sort algorithm */
void cycle_sort(int * a)
{
int temp, item,
pos, i, j, k;
for (i = 0;i <
MAX; i++)
{
item = a[i];
pos = i;
do
{
k = 0;
for (j =
0;j < MAX;j++)
{
if
(pos != j && a[j] < item)
{
k++;
}
}
if (pos !=
k)
{
while
(pos != k && item == a[k])
{
k++;
}
temp =
a[k];
a[k] =
item;
item =
temp;
pos =
k;
}
}while (pos !=
i);
}
}
Subscribe to:
Posts (Atom)