20 July 2010

Bubble Sort, Selection Sort and Insertion Sort

Here's sample implementations in C for Bubble, selection and insertion sorts:

#include <stdio.h>

void bubble_sort(int[], int);
void selection_sort(int[], int);
void insertion_sort(int[], int);

void print(int[], int);

int main(void)
{
int arr[]={15, 10, 3, 8, 1, 58, 2};
print(arr, sizeof(arr)/sizeof(int));
//bubble_sort(arr, sizeof(arr)/sizeof(int));
//selection_sort(arr, sizeof(arr)/sizeof(int));
insertion_sort(arr, sizeof(arr)/sizeof(int));
print(arr, sizeof(arr)/sizeof(int));

return 0;
}

void bubble_sort(int arr[], int length)
{
int outter, inner;

for (outter=length-1; outter>=1; outter--)
{
for (inner=0; inner<length-1; inner++)
{
if (arr[inner] > arr[inner+1])
{
int tmp = arr[inner];
arr[inner] = arr[inner+1];
arr[inner+1] = tmp;
}
//print(arr, length);
}
}
}

void selection_sort(int arr[], int length)
{
int outter, inner;

for (outter=0; outter<=length-1; outter++)
{
int min = outter;
for (inner=outter+1; inner<=length-1; inner++)
{
if (arr[inner] < arr[min])
min = inner;
}
if (min != outter)
{
int tmp= arr[min];
arr[min]= arr[outter];
arr[outter] = tmp;
}
//print(arr, length);
}
}

void insertion_sort(int arr[], int length)
{
int outter, inner, tmp;
for (outter=1; outter<=length-1; outter++)
{
inner = outter;
while (inner>0 && arr[inner-1]>arr[inner])
{
//print(arr, length);
tmp = arr[inner];
arr[inner] = arr[inner-1];
arr[inner-1] = tmp;
inner--;
}
}
}

void print(int arr[], int length)
{
int i=0;
for (;i<length; i++)
{
printf("%i ", arr[i]);
}
printf("\n");
}

No comments: