CODEWITHSUNDEEP
javaalgorithmsortingmergesort
malifa
malifa

Reputation: 8165

Counting Operations of Merge Sort and Selection Sort

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! :)

Upvotes: 1

Views: 6740

Answers (1)

vgru
vgru

Reputation: 51274

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.

Upvotes: 1

Related Questions