Sorting Programs

Bubble Sort

Bubble sort is the simplest sorting technique . Unfortunately, the slowest also :).

Here is the sample source code for bubble sort


void bubbleSort(int numbers[], int array_size)
{
int i, j, temp;

for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++) { if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}



Insertion Sort

As name suggest , it inserts each item into its proper place in the final list, not suitable for larger lists

void insertionSort(int numbers[], int array_size)
{
int i, j, index;

for (i=1; i < index =" numbers[i];" j =" i;">while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}

Heap Sort
Slowest but recommended sorting technique for larger volumes of data
void heapSort(int numbers[], int array_size)
{
int i, temp;

for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);

for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}


void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;

done = 0;
while ((root*2 <= bottom) &&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; (!done)) { if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if (numbers[root] < temp =" numbers[root];" root =" maxChild;">else
done = 1;
}
}

Merge Sort
Splits the list into two ,sorts recursively and merged back final sorted list Faster than Heap Sort but required double the memory of Heap sort becoz of its 2nd array

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;

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; } }


Quick Sort

Quick sort algorithm is simple in theory,but very difficult to put into code.

Very fast Sorting Technique but Complex Algorithm Have a look
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left <>while ((numbers[right] >= pivot) && (left <>if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left <>if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left <>if (right > pivot)
q_sort(numbers, pivot+1, right);
}

Selection Sort

simple and easy to implement but not recommended for larger lists

void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;

for (i = 0; i < min =" i;">for (j = i+1; j <>if (numbers[j] < min =" j;" temp ="