CODEWITHSUNDEEP
java
user1186807
user1186807

Reputation: 31

How to check if an array of integers is sorted?

Would you have code that just sorts it for you and after its done sorting see if there's any changes. Would you use a certain type of sort like insertion sort, selections or something along those lines

int[] arr = {4,1,3,8,9,2,7,0,5,6};
System.out.println(Arrays.toString(arr));
selectionSort(arr);

public static void selectionSort (int []arr) {
    for(int i = 0; i < arr.length; i ++) {
        //find the ith element
        int smallest = i;
        for (int j = i + 1; j <arr.length; j++) {
            //find the smallest unsorted element 
            if(arr[j] < arr[smallest]) {
                smallest = j;

So I think im on the right track but I dont know how to compare the ints to see if there all in the right order.

What do i need to add?

Upvotes: 2

Views: 9476

Answers (4)

Petar Ivanov
Petar Ivanov

Reputation: 93030

It's much simpler than that - just iterate over the array and see if each element is smaller than the next.

int[] checkarray = ....;

boolean sorted = true;
for(int i = 1; i < checkarray.length; i++) {
    if(checkarray[i-1] > checkarray[i]){
          sorted = false;
          break;
    }
}

System.out.println("Sorted: " + sorted);

Upvotes: 9

Rami Sharaiyri
Rami Sharaiyri

Reputation: 546

//def ArrayList listOfItemsForSorting = ["a", "B", "c"];
//def String sortOrder = "ASC" or "DESC"

def boolean sortItemsWithCollator(ArrayList listOfItemsForSorting, String sortOrder) {
    Collator myCollator = Collator.getInstance();
    // check if the array itself is less than 2 items if so, it's clearly no need for sorting.
    if (listOfItemsForSorting.size() < 2) {
        return true;
    }
    else if (sortOrder.equals("ASC")){
        for (def i = 0; i < listOfItemsForSorting.size() - 1; i++) {
              if (myCollator.compare(listOfItemsForSorting[i], listOfItemsForSorting[i + 1]) > 0) {
                return false;
            }
        }
    }
    else{
        for (def i = 0; i < listOfItemsForSorting.size() - 1; i++) {
              if (myCollator.compare(listOfItemsForSorting[i], listOfItemsForSorting[i +1]) < 0) {
                return false;
            }
        }
    }
    return true;
}

This method return s boolean.

Upvotes: 1

rajibdotnet
rajibdotnet

Reputation: 1596

Selection sort is the simplest sorting technique, which uses linear search to scan a list or array, but a better way to sort and highly recommended is Quick sort. Quick sort is based on the theory of Divide and Conquer, where we keep dividing a list into various smaller sub lists and in turn sorting them all. Please read about Quick sort in Wikipedia. Also important to know is how various sorting techniques perform based on the occurrences of typical data such as All Identical data, and so on.

Upvotes: -1

Cratylus
Cratylus

Reputation: 54074

Would you have code that just sorts it for you and after its done sorting see if there's any changes

If you are in a method that take as input an array that you expect to be sorted but are not sure if it is, you could apply insert sort since this (otherwise inefficient algorithm on large input) has linear complexity for nearly sorted input.

Just to be clear.

The answer of @Petar would be the way to go since it is the most simple and straightforward.

I mention this answer also for completeness since it is not absurd to sort something if you are not sure if it is sorted or not at a specific time in your program.

After all if it is not sorted completely you have already done a O(N) scan for no benefit and you will have the extra complexity of sort on the top O(NlogN).

This actually is the reason that most of the algorithmic analysis on sorting algorithms mention their performance on sorted input as it occurs more frequent than we expect.
Your case is an example.

Upvotes: 1

Related Questions