Sorting in C





C and C++ Programs

Bubble Sort
void bsort (float x[], int size){
int i,j=0;
float temp;
for(i=0; i < size; i++)
for(j=0;  j < size-1;  j++)
if( x[j] > x[j+]){ // bubble - compare with the adjacent item
temp = x[j];
x[j] = x[j+1];
x[j+1] = temp;
}
}
Optimized Bubble Sort
void optbsort (float xx[], int size){
float temp;
int swapped=1;
for(j=1; j < size && swapped == 1; j++){
swapped = 0;
 /* i < size-j  ---> optimizes the algorithm */
for(i=0; i < size-j; i++){
if(xx[i] > xx[i+1]){
temp=xx[i];
xx[i] = xx[i+1];
xx[i+1] = temp;
swapped=1; // found disordered items
}
}
}
}
Selection Sort
viod selSort(duble x[], int n){
int left, least,i;
double temp;
for(left=1; left < size; left++){
for(least=left-1, i=left; i < size; i++){
if(x[i] < x[least]) least=i;
}
if(left-1 != least){ // found smaller element
temp = x[least];
x[least] = x[left-1];
x[left-1] = temp;
}
}
}
Insertion Sorting
void InsertionSort(float src[],float target[], int size){
int i,j;
for (trgt[0]=src[0],i=1; i < size-1; i++){
for (j = i; i > 0; j--){
if(trgt[j-1] > src[i])
target[j]=trgt[j-1];
else
break;
}
target[j]=src[i];
}


Quick Sort


//Quick Sort
void QuickSort(double xx[], int size);
    qsort(xx, 0, size);
}


void qsort(double xx[], int left, int right){
    int i, j;
    double pivot,temp;
    if (left > right) return;
    pivot = xx[left];
    i = left;
    j = right;
    while( i < j){
        while(xx[i] < pivot && i < right) i++;
        while(xx[j] > pivot && j > left) j--;
        if(i < j){ // exchange disorderd items
            temp = xx[i];
            xx[i] = xx[j];
            xx[j] = temp;
        }
    }
    //exchange smaller value than pivot
    xx[left] = xx[j];
    xx[j] = pivot;
    qsort(xx, left, j-1);
    qsort(xx, j+1, right);
}


/***Merge sort***/
/* return the number of elements in the result, 
      reuslt in array by reference*/
int mergerSort(double x[], double y[], double z[], int n1, int n2){
    int i, j, k;
    /* *
     * sort each list  and then merge them into one
     * */
    qsort(x,0,n1-1);
    qsort(y,0,n2-1);
    i=j=k=0;
    while(i < n1 &&; j < n2){
        if(x[i] < y[j])    z[k++]=x[i++];
        else   if(x[i] > y[j])  z[k++]=y[j++];
        else{/* x[i]==y[j] */
                z[k++]=x[i++];
                j++;  /* incremented all 3 subscripts*/
        }
    } 
    /* one list elements are copied */
    while( i < n1) z[k++] = x[i++];
    while( j < n2) z[k++] = y[j++];
    return k; /* post incremented k---> no of elements*/
}



/*** SHELL SORT by  D L Shell ***/
/* ***
 * the algorithm subdivides the list into interleaved groups
 * of h lists, and the subarray are sorted using bubble or insertion 
 * sort, the steps repeated with diminishing value of h until it reaches 1
 * ***/
void shellSort(double x[], int n){
    double temp;
    int i, j, h;
    /* height of groups*/
    for( h =1; h < n / 9; h = 3*h + 1);  
    for( ; h > 0; h /=3){
        for(i = h; i < n; i++){
            temp=x[i];
            for( j = i-h; j >= 0; j -=h){
                if(temp < x[j])
                    x[j+h] = x[j];
                else
                    break;
            }
            x[j+h] = temp;
        }
    }
}





/* **Heap sort**  O(n log n)** */


void heapSort(double x[], int n){
   buildheap(x,n); // makes the heap
   hSort(x,n); // sort the heap
}


/* ** 1 Build heap ** */
void buildheap(double x[], int n){
    int i, j, k;
    double temp;
    for(k=2; k < n; k++){ // repeat for k = 2,3,...
        i=k;
        j=k/2;   // parent of new element
        temp=x[i];
        while(i > 1 && temp > x[j]){ 
            x[i] = x[j]; // interchange elements
            i = j;
            j = i/2;
            if ( j < 1) j = 1;
        }
        x[i] = temp;
    }
}


* ** 2 sort the heap ** */
void hSort(double x[], int n){ // x is the heap 
    int i, j, k;
    double temp, value;
    for( k = size; k >= 2; k--){
        temp = x[1];
        x[1] = x[k];
        x[k] = temp;
        i = 1;
        value = x[1];
        j = 2;
        if ( j + 1 < k)
            if( x[j+1] > x[j]) j++;
        while( j <= k-1 &&  x[j] > value){
            x[i] = x[j];
            i = j;
            j = 2 * i;
            if ( j + 1 < k)
                if(x[j+1] > s[j])
                    j++;
                else
                    if(j > size)
                        j = size;
            x[i] = value;
       }
    }
}   




C++ Sample Program -- Demonstrating bubble sort



#include



void bSort(long *v, int size){
     int flag, i, j;
     long temp;
     for(j=0,flag=1; flag == 1; j++){
 for(flag=0,i=1; i < size-j; i++){
     if(v[i-1] > v[i]){
temp = v[i-1];
v[i-1] = v[i];
v[i] = temp;
flag = 1;
     }
 }
    }
}



class Array{
    private:
    long *v;
    int size, length;
    public:
      Array(){ size=0; v=NULL; }
      Array(int size);
      Array(long ar[], int count);
      void sort();      // sort the items  
      // int search(long key);// search for a key and returns the loc
      void display();
      void getValues(); //   void setValueAt(long v, int loc);
};
Array::Array(int size){
      this->size= size;
      this->v=new long[size];
}
Array::Array(long ar[], int count){
    size=count;
    v=new long[size];
    for(int i =0; i < count; i++)
       *(v+i) = *(ar+i); //same as  v[i] = ar[i];
}
void Array::display(){
   cout<<"\n\n\n";
   for(int i=0; i < this->size; i++)
      cout<<"  "<
}






void Array::sort(){  bSort(v, size);  }


void Array::getValues(){
    cout<<"\n Input "<
    for(int i = 0; i < size; i++)
       cin>>v[i];
}


main(){
   Array ar(5);
   ar.getValues();
   ar.display();
   ar.sort();
   ar.display();


   return 0;
}

Subscribe to: Posts (Atom)