Sorting in C

We will look at three sorting algorithms – selection sort, bubble sort, and insertion sort.

In selection sort, the list is divided into two lists, one of which is sorted and the other is unsorted. We then find the smallest element from the unsorted list and swap it with the element at the beginning of the unsorted data; this is known as a sort pass. This sorting algorithm requires as many sort passes as there are elements, minus one. Each time a sort pass is accomplished, the sorted list grows by one element and the unsorted list shrinks by one element.

#include <stdio.h>

void switchSmallest(int array[], int current, int last){
    
    int i;
    int smallest;
    int tempData;
    smallest = current;
    
    
    //find smallest value remaining in array
    for(i = current + 1; i < last; i++){
        if(array[i] < array[smallest]){
            smallest = i;
        }
    }
    
    //swap out the values
    if(smallest!=current){
        printf("\nSwitching %d and %d\n", array[current], array[smallest]);
        tempData = array[current];
        //store smallest value we found 
        //in the current element.
        array[current] = array[smallest];
        //store value formerly in current element
        //where smallest value was
        array[smallest] = tempData;
    }    
    
} //end switchSmallest

void printList(int array[], int demarcation, int last){
    int i;
    for(i=0; i < last; i++){
        if(i==demarcation){
            printf("[sorted]\t");
        }
        printf("%d\t", array[i]);
    }
} //end printList

int main(void){
    
    const int Array_Length = 9;
    
    int array[] = {47, 80, 42, 1138, 8088, 256, 1946, 404, 1024};
    
    
    int i,j;
    
    printf("Array before sorting: \n");
    printList(array, 0, Array_Length);
    putchar('\n');
    
    for(i = 0; i < Array_Length; i++){
        switchSmallest(array, i, Array_Length);
        printf("\nSort Pass %d\n", i+1);
        printList(array, i+1, Array_Length);
        printf("\n");
    }
    
}

At the start of the process, the sorted array has zero elements, and the unsorted array is, in essence, the array itself. We then take the first element in the array, at index 0, and compare it with every single element in the remainder of the array. If we find an element smaller than the element stored at index 0, we switch those two elements out and the sorted array gains one element, since we know for sure that at least that element is indeed the smallest of the bunch.

Note that every time we wish to move data, we must use a temporary storage area.

Next,, let’s take a gander at bubble sort. In bubble sort, the list is divided into two sublists, sorted and unsorted. Unlike selection sort, bubble sort will often exchange more than one set of elements per sort pass.

#include <stdio.h>

void printArray(int array[], int last){
    int i;
    for(i=0; i < last; i++){
        printf("%d ", array[i]);
    }
    putchar('\n');
}

void bubbleUp(int array[], int first, int last){
    int i;
    int temp;
    for(i=first; i < last; i++){
        //with adjoining elements
        //if element is greater than the next
        //switch them
        if(array[i] > array[i+1]){
            printf("%d > %d\t", array[i], array[i+1]);
            temp = array[i];
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }    
}

void bubbleSort(int array[], int last){
    int i;
    for(i=0; i < last; i++){
        printf("\nPass %d:\n", i+1);
        printArray(array, last);
        bubbleUp(array, i, last);
    }
}

int main(void){
    const int Num_Elements = 10;
    
    int array[Num_Elements] = {208, 57, 416, 117, 361, 57, 1, 248, 141, 118};
    bubbleSort(array, Num_Elements);
    return 0;
}

The advantage to bubble sort is that while in the worst case scenario it takes as many iterations as selection sort, in can, in most circumstances, actually finish with fewer loops. Our first bubbleSort() function would still go through the array element by element even though the data being sorted was already in sequence. With a few modifications, we can end the sort early if all elements are already in sequence.

#include <stdio.h>

void printArray(int array[], int last){
    int i;
    putchar('\n');
    for(i=0; i < last; i++){
        printf("%d ", array[i]);
    }
    putchar('\n');
}

void switchElements(int array[], int first, int second){
    printf("Switching %d and %d\t", array[first], array[second]);
    int temp = array[second];
    array[second] = array[first];
    array[first] = temp;
}

//this version is made up of nested for loops
//first loop using int i for a counter
//second loop using int j for a counter
void bubbleSort(int array[], int last){
    int i, j, marker;
    for(i = 0; i < last; i++){
        printf("\nSort Pass %d\n", i+1);
        //marker set to zero
        //if no elements are switched
        //marker will still be zero after end
        //of inner loop
        marker = 0;
        
        //last-2 as we are counting from zero
        for(j=last-2; j >= 0; j--){
            if(array[j] > array[j+1]){
                switchElements(array, j, j+1);
                marker++;
            }
        } //end inner for loop
        
        //if marker still 0
        //then array already sorted
        //sorting is finished!
        if(marker==0){
            printf("\nArray sorted!\n");
            break;
        } else {
            printArray(array, last);
        }
    }//end outer for loop
}


int main(void){
    const int Num_Elements = 10;
    int array[Num_Elements] = {9651, 2529, 131, 55, 9, 364, 11640, 758, 51408, 2059};
    
    printArray(array, Num_Elements);
    
    bubbleSort(array, Num_Elements);
    
    printArray(array, Num_Elements);
    return 0;
}

Our final sort function is insertion sort. Unlike bubble and selection sort, we can sometimes see insertion sort actually implemented in the real world. Insertion sort is a subfunction of the popular Quicksort.

#include <stdio.h>

void insertionSort(int array[], int last);
void insertElement(int array[], int selected);

void printArrayWithSelected(int array[], int selected, int last);
void printArray(int array[], int last);

int main(void){
    const int Array_Size = 11;
    
    int array[Array_Size] = {34, 89, 30, 98, 79, 99, 3, 73, 49, 37, 32};
    insertionSort(array, Array_Size);
    
    printArray(array, Array_Size);
    
} //end main

void insertionSort(int array[], int last){
    int selected;
    //note index begins at one
    for(selected = 1; selected < last; selected++){
        printArrayWithSelected(array, selected, last);
        insertElement(array, selected);
    }
} //end insertionSort

void insertElement(int array[], int selected){
    int i, found;
    int temp;
    
    //give found Boolean value
    //of false AKA 0
    found = 0;
    //assign current element in array to temp value
    temp = array[selected];
    for(i = selected - 1; i >= 0 && !found; i){
        //move every element greater than 
        //the selected value down one
        if(temp < array[i]){
            printf("\t[%d] < %d\n", temp, array[i]);
            //move element down the list one
            array[i+1] = array[i];
            i--;
        } else {
            found = 1;
        }
    } //end for loop
    
    //place the selected value
    //back into the array
    array[i+1] = temp;
} //end insertElement



void printArrayWithSelected(int array[], int selected, int last){
    int i;
    putchar('\n');
    for(i = 0; i < last; i++){
        if(i!=selected){
            printf(" %d ", array[i]);
        } else {
            printf(" [%d] ", array[i]);
        }
    }
    putchar('\n');
} //end printArrayWithSelected

void printArray(int array[], int last){
    int i;
    putchar('\n');
    for(i = 0; i < last; i++){
        printf(" %d ", array[i]);
    }
    putchar('\n');
    
}//end printArray

If you’re interested in learning more about C, buy a copy of my book for the Amazon Kindle and Amazon Kindle app. The book includes over 100 example programs and for those viewing it from your Kindle Cloud browser or on a tablet the code is in color.

http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/