CODEWITHSUNDEEP
c#arraysloopssorting
c-shark
c-shark

Reputation: 87

Adding a break to a bubble sort in case the array is already sorted

I currently have a (somewhat messy) bubble sort of an object array called "sorted", the code is as follows

object storage = 0;
for (int i = 0; i < sorted.Length; i++)
{
    for (int c = 0; c < sorted.Length - 1; c++)
    {
        if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0)
        {
            storage = sorted[c + 1];
            sorted[c + 1] = sorted[c];
            sorted[c] = storage;
        }
    }
    return sorted;

Problem is that this function always loops through the array , no matter what. Hypothetically speaking the "sorted" array could be a large array and just so happen to be sorted already, in which case the function would still scan the array and work for some time, which I want to prevent. So the question is, how do I stop the loop properly in case the array is sorted already?

Upvotes: -1

Views: 2247

Answers (4)

Saumya Soni
Saumya Soni

Reputation: 1

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 5};
        bubbleSort(sortedArray);
        for (int num : sortedArray) {
            System.out.print(num + " ");
     }
   }
}

Upvotes: -1

Ronald
Ronald

Reputation: 2882

A bubble sort bubbles the largest (smallest) element of an array towards the end of an array. This is what your inner loop does.

First of all you can take advantage of the knowledge that after n iterations, the last n elements are sorted already, which means that your inner loop doesn't need to check the last n elements in the (n+1)th iteration.

Secondly, if the inner loop doesn't change anything, the elements must be in sequence already, which is a good point for a break of the outer loop.

Since you're doing this as a practising exercise, I'll leave the coding up to you :-)

Upvotes: 3

Enigmativity
Enigmativity

Reputation: 117144

Try this:

object storage = 0;
for (int i = 0; i < sorted.Length; i++)
{
    bool swapped = false;
    for (int c = 0; c < sorted.Length - 1; c++)
    {
        if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0)
        {
            storage = sorted[c + 1];
            sorted[c + 1] = sorted[c];
            sorted[c] = storage;
            swapped = true;
        }
    }
    if (!swapped)
    {
        break;
    }
}

If it gets through a pass without swapping then the array is ordered so it will break.

Upvotes: -2

Ashkan Mobayen Khiabani
Ashkan Mobayen Khiabani

Reputation: 34180

Why don't you use OrderBy instead of sorting it yourself?

sorted = sorted.OrderBy(s=> s).ToArray();

If you insist to use the bubble sort, you can do this:

bool changed;
for (int i = 0; i < sorted.Length; i++)
{
    changed = false;
    for (int c = 0; c < sorted.Length - 1; c++)
    {
        if (sorted[c].ToString().CompareTo(sorted[c + 1].ToString()) > 0)
        {
            changed = true;
            storage = sorted[c + 1];
            sorted[c + 1] = sorted[c];
            sorted[c] = storage;
        }
        if(!changed) break;
    }

I'm setting changed to false each time in the first loop. If there was no changes to the end, then the array is already sorted.

Upvotes: 0

Related Questions