Counting Operations of Merge Sort and Selection Sort

Question

I want to compare count of operations of the sorting algorithms Merge Sort and Selection Sort, but I have some problems figuring out which operations to count and which not..

Here are my implementations. I think I'm counting the operations of Selection Sort in the right way, but I don't know about Merge Sort:

Selection Sort:

public class SelectionSort {
private int exchanges, comparisons;

public void selectionSort(int[] x) {    
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) 
            {
                //... Exchange elements
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                exchanges++;
            }
            comparisons++;
        }
    }
    System.out.println("SelSort_Exchanges: "+exchanges);
    System.out.println("SelSort_Comparisons: "+comparisons);
    System.out.println("SelSort_Operations: "+(exchanges+comparisons));
}
}

If I put in an array of 10 int I get:

SelSort_Comparisons: 45
SelSort_Exchanges: 27
SelSort_Operations: 72

Seems right to me, but now for Merge Sort:

public class Mergesort {
private int[] numbers;
private int[] helper;

private int number;
private int comparisons, exchanges;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
    System.out.println("MerSort_Comparisons "+comparisons);
    System.out.println("MerSort_Exchanges "+exchanges);
    System.out.println("MerSort_Operations "+(comparisons+exchanges));
    System.out.println();
}

private void mergesort(int low, int high) {
    // Check if low is smaller then high, if not then the array is sorted
    if (low < high) 
    {
        // Get the index of the element which is in the middle
        int middle = (low + high) / 2;
        // Sort the left side of the array
        mergesort(low, middle);
        // Sort the right side of the array
        mergesort(middle + 1, high);
        // Combine them both
        merge(low, middle, high);
    }
}

private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
        exchanges++;
    }
    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
            exchanges++;
        } else {
            numbers[k] = helper[j];
            j++;
            exchanges++;
        }
        k++;
        comparisons++;

    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
        numbers[k] = helper[i];
        exchanges++;
        k++;
        i++;
    }
}   
}

now I get

MerSort_Comparisons 22
MerSort_Exchanges 61
MerSort_Operations 83

as a result but I don't know if its right. Result of Comparisons seems right to me, but if I take an array of 20 for example it doesnt seem right anymore.

Could anyone help me with this and tell me where exactly I have to put my comparison and exchange increments?

thanks in advance! :)

An array with 10 elements will hardly give good indication on algorithm performance. To get a better feeling of how they perform under different inputs, try comparing larger arrays (say, 1000) elements, in various flavors: randomized, already sorted, reversed, etc. — vgru
– vgru, Commented Jun 19, 2012 at 14:28

vgru · Accepted Answer · 2012-06-19 11:09:16Z

1

Simplest way would be to create two methods, Compare and Swap, and increase counter inside of them. Whatever sorting algorithm you implement, it should only interact with the array using these methods.

Also, this page can help you analyze different sorting algorithms visually.

answered Jun 19, 2012 at 11:09

vgru

51.5k17 gold badges127 silver badges214 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Counting Operations of Merge Sort and Selection Sort

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related