Lifecode

On my last post about sorting algorithm, I made a pretty bad coding mistake on the merge function. The thing is, it doesn’t really demonstrate that algorithm. Also, it never worked on Visual Studio, for some weird reasons.

I spent few hours, and now I am finished reconstructing the whole program and making the merge algorithm really work. I built a class for it, and I’m pretty sure this will work on any situation. Here are the source codes.

//MergeClass.h

#pragma once
#include "stdafx.h"
class MergeClass {
public:
    double xarr[ASIZE], brr[ASIZE];
    void msort(double a[], int x) {
        for(int i = 0; i < ASIZE; i++) {
            xarr[i] = a[i];
        }
        mergesort(0, x - 1);
        for(int i = 0; i < ASIZE; i++) {
            a[i] = xarr[i];
        }
    }
    void mergesort(int a, int b) {
        int c;
        if(a < b) {
            c = (a + b) / 2;
            mergesort(a, c);
            mergesort(c + 1, b);
            domerge(a, b, c);
        }
    }
    void domerge(int a, int b, int c) {
        int i, j, k;
        for(i = a; i <= b; i++) {
            brr[i] = xarr[i];
        }
        i = a;
        j = a;
        k = c + 1;
        while((i <= c) && (k <= b)) {
            if(brr[i] <= brr[k]) {
                xarr[j++] = brr[i++];
            } else {
                xarr[j++] = brr[k++];
            }
        }
        while(i <= c) {
            xarr[j++] = brr[i++];    
        }
    }
};

// stdafx.h

#pragma once
#include "targetver.h"
#include <iostream>
#define ASIZE 6            //Size of the array you are to sort. This is very much used in this program.

using namespace::std;

// SortingAlgorithm.cpp

#include "stdafx.h"
#include "MergeClass.h"


void pH();                                            //function for my header
void pVal(double arr[], char *sor, int len);        //Outputs the inputted array
void bubbleS(double arr[], int len, bool out);        //Bubble Sort
void insertS(double arr[], int len, bool out);        //Insertion Sort
void selectS(double arr[], int len, bool out);        //Selection Sort
void mergeS(double arr[], int len, bool out);        //Merge Sort (initializer)

int main() {
    bool lp = true;
    int ch;
    double sArray[ASIZE] = {86.49, 201.35, 55.67, 1942.46, 291.64, 193.14};
    pH();
    pVal(sArray, "None", ASIZE);
    cout << "Please enter the sorting algorithm you want to use:" << endl << endl;
    cout << "\t[1] Bubble Sort" << endl;
    cout << "\t[2] Insertion Sort" << endl;
    cout << "\t[3] Selection Sort" << endl;
    cout << "\t[4] Merge Sort" << endl;
    cout << "\t[5] None (Exit)" << endl;
    while (lp) {
        cout << endl << "Choice: ";
        cin >> ch;
        cin.ignore();
        switch(ch) {
            case 1:
                bubbleS(sArray, ASIZE, true);
                lp = false;
                break;
            case 2:
                insertS(sArray, ASIZE, true);
                lp = false;
                break;
            case 3:
                selectS(sArray, ASIZE, true);
                lp = false;
                break;
            case 4:
                mergeS(sArray, ASIZE, true);
                lp = false;
                break;
            case 5:
                lp = false;
                break;
            default:
                cout << "(Invalid Choice)" << endl;
        }
    }
    cin.get();
    return 0;
}

void pH() {
    cout << "(c) Ruel Pagayon 2010 - http://ruel.me" << endl;
}

void pVal(double arr[], char *sor, int len) {
    cout << endl << "Sorting Algorithm:\t" << sor << endl << endl;
    for(int i = 0; i < len; i++) {
        cout << "\t[" << i << "]\t=>\t" << arr[i] << endl;
    }
    cout << endl;
}

void bubbleS(double arr[], int len, bool out) {
    double h;
    for (int p = 0; p < len - 1; p++) {
        for(int i = 0; i < len - 1; i++) {
            if(arr[i] > arr[i + 1]) {
                h = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = h;
            }
        }
    }
    if(out) {
        pVal(arr, "Bubble Sort", len);
    }
}

void insertS(double arr[], int len, bool out) {
    double tb;
    for(int j, i = 0; i < len; i++) {
        tb = arr[i];
        j = i - 1;
        while ((tb < arr[j]) && (j >= 0)) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tb;
    }
    if(out) {
        pVal(arr, "Insert Sort", len);
    }
}

void selectS(double arr[], int len, bool out) {
    double mV;
    for (int mI, i = 0; i < len - 1; i++) {
        mV = arr[i];
        mI = i;
        for(int j = i + 1; j < len; j++) {
            if(arr[j] < mV) {
                mV = arr[j];
                mI = j;
            }
        }
        arr[mI] = arr[i];
        arr[i] = mV;
    }
    if(out) {
        pVal(arr, "Selection Sort", len);
    }
}

void mergeS(double arr[], int len, bool out) {
    MergeClass mx;
    mx.msort(arr, len);
    if(out) {
        pVal(arr, "Merge Sort", len);
    }
}

There we go. If you face problems regarding the code, please feel free to comment. By the way, the code was coded, compiled, and built on Visual C++.

Several hours ago in our Data Structures class, we had an exercise about the different Sorting Algorithms in C++ arrays. It was a painful 1 and a half hour coding, since the editor we are using is Turbo C++, and the window is too small, I can only view 50 lines at a time, I think. I have nearly finished the exercise, if it wasn’t for that merge sort, I have to be honest, I didn’t get it at first. So what are these sorting algorithms anyway?