Archive

Posts Tagged ‘C language’

A Generic Quicksort Implementation in C

April 7th, 2008 bodom_lx No comments

As assignment for Data Structures and Algorithms course, we had to work with a modified version of the quicksort algorithm. It came obvious that for modifying a qsort you need to implement it :-)

It is difficult to find a clear quicksort algorithm implemented, so I wrote it.

Here is the generic C implementation of the Quicksort Algorithm, which sorts an array in place, following the Divide And Conquer design.

Download: quicksort qsort in C language

Interesting methods (look at the source code for comments):

int partition( int A[], int left, int right) {
        int pivot;
        pivot = A[right];                                                                      
        while(1){
                while( A[right] > pivot){
                        right–;
                }
                while( A[left] < pivot){       
                        left++;                                
                }
                if( left < right ){                                                            
                        swap(A,left,right);
                }else{
                        return left;                                   
                }
        }
}

void quicksort( int A[], int left, int right){
        int m;
        if( left < right ) {                           
                m = partition( A, left, right);        
                quicksort( A, left, m-1);              
                quicksort( A, m+1, right);
        }       
}
 

As you see, there is nothing optimized in this implementation. It just looks elegant and easy to be understood.
If you would like to have a more optimized version of this algorithm, take a look at this one.

Related posts

Sorting array elements with C language

February 23rd, 2008 bodom_lx 3 comments

UPDATE 17:19: it seems that the program I implemented today uses a kind of Bubble Sort algorithm, give it a try, it’s quite interesting!

After 3 long days studying C, I think I’ve assimilated a good knowledge base for the incoming semester.
So there is a tiny C program that sorts the elements of a given integer array, using pointers:

Download the source code (well commented)

#include <stdio.h>
void sortArray(int *firstElement, int *lastElement);
void swapArrayElements(int *firstElement, int *secondElement);
void printArray(int array[], int arraySize);

void sortArray(int *firstElement, int *lastElement){
        int *currentElement = firstElement;
        while (firstElement != lastElement){
                while(currentElement != lastElement){
                        if(*currentElement < *firstElement){
                                swapArrayElements(currentElement,firstElement);
                        }
                        currentElement++;
                }
                firstElement++;
                currentElement = firstElement;
        }
}

void swapArrayElements(int *firstElement, int *secondElement){
        int tmp;
        tmp = *firstElement;
        *firstElement = *secondElement;
        *secondElement = tmp;
}

void printArray(int array[], int arraySize){
        int counter = 0;
        while(counter<arraySize){
                printf("%d\n",array[counter]);
                counter++;
        }
}

int main (int argc, char *argv[]){
        int array[] = {2929393,1,23239,-66,15,4,3,0,112,45,3,1000,19};
        int arraySize = sizeof(array)/sizeof(array[0]);
        int *firstElement = &array[0];
        int *lastElement = firstElement + arraySize;
        printf("————————————————-\n");
        printf("Elements of the array:\n");
        printf("————————————————-\n");
        printArray(array,arraySize);
        printf("————————————————-\n");
        sortArray(firstElement,lastElement);
        printf("Elements sorted:\n");
        printf("————————————————-\n");
        printArray(array,arraySize);
        printf("————————————————-\n");
}

 

A better program should ask the user to input the array elements, and a better algorithm should not scan every array element n times, where n is the number of the elements.
But I wrote it just for fun and for learning C pointers. I will learn to do better in the Data Structures and Algorithms course in the next semester ;)

Related posts

Reflecting while studying C language

February 20th, 2008 bodom_lx 7 comments

Run the following C program

#include <stdio.h>
#include <string.h>
int main (int argc, char const *argv[]){
        if(!argv[1]) return 0;
        int i = strlen(argv[1]);
        while(i > -1){
                printf("%c",argv[1][i]);
                i–;
        }
        printf("\n");
}
 

Using this string as first program parameter:

"..eromyna ti ekat t'nac I ?nwod edispu semit ynam os dlrow eht si yhW"

Related posts

Categories: Programming Tags: , ,