Method to sort an array in Java

Question

I've been working on a method that sorts an array from lowest to highest number. I came up with the code below but, as you probably guessed, it doesn't do what I expected.

The logic I wished to apply goes as follows:

Given I have an array, for example array {4,3,1,2,5} The code would compare, for example, array[0] (which would be four in this case) with each element in the array,

array[0]>array[0] (4>4=false), 
array[0]>array[1] (4>3)= +1counter, 
array[0]>array[2] (4>1)= +1counter, 
array[0]>array[3] (4>2)= +1counter,
array[0]>array[4] (4>5=false)

counter = 3

So since the counter value its now 3, in the new array (array2, or arrayOrdered) number 4 would be in the third index.

How should I fix it? Any help its more than appreciated!

public static int[] OrderArray(int[] array)
{

    int[] array2=new int[array.length];

    for (int i=0; i<array.length; i++)
    {
        int place=0;
        for (int j=0; j<array.length;j++)
        {
            if (array[i]> array[j])
            {
                place = place+1;
            }
            array2[place] = array[i];
        }

    }
    return array2;
}

Answer 1

int place=0;
        for (int j=0; j<array.length;j++)
        {
            if (array[i]> array[j])
            {
                place = place+1;
            }
            array2[place] = array[i];
        }

You updated array2[place] every time, whereas it should be updated after you looped through the array. Thus array2[place] = array[i]; This shoud be outside the second for loop

int place=0;
        for (int j=0; j<array.length;j++)
        {
            if (array[i]> array[j])
            {
                place = place+1;
            }

        }
array2[place] = array[i];

Answer 2

Using Java 8.

import java.util.Arrays;

public class Test {
    public static void main( String[] args ) {
        int[] array = { 2, 1, 3, 5, 4 };
        System.out.println( Arrays.toString( array ) );

        int[] orderedArray = Arrays.stream( array )
            .sorted()
            .toArray();
        System.out.println( Arrays.toString( orderedArray ) );
    }
}

Answer 3

What you are looking to do is called sorting, and there are many known sorting algorithms with different characteristics you can use to accomplish what you want.

You can read about many of the different sorting algorithms here: https://en.wikipedia.org/wiki/Sorting_algorithm

Java itself has built in sorting functionality, and you can sort an array using the Arrays.sort method, which uses a very fast and well known Quicksort algorithm for arrays of ints.

As other commentators have discussed, your sorting algorithm appears flawed, and overall appears to be closest to an Insertion Sort algorithm, which you may want to look at for some ideas: https://en.wikipedia.org/wiki/Insertion_sort

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Pseudocode from the above link:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Answer 4

I did not check all corner case to assure your logic is correct but for sure the line:

array2[place] = array[i];

should be outside of the second for block. Your code overwrites all good inserts in array2 currently.

Working implementation:

public static int[] OrderArray(int[] array){

  int[] array2=new int[array.length];
  for (int i=0; i<array.length; i++)
  {
      int place=0;
      for (int j=0; j<array.length;j++)
      {
          if (array[i]> array[j])
          {
              place = place+1;
          }
      }
      array2[place] = array[i];
  }
  return array2;
}

Answer 5

When you are ready to make the decision where to place it. You should do it outside of the loop where it determines the position for an element

public static int[] OrderArray(int[] array)
{

    int[] array2=new int[array.length];

    for (int i=0; i<array.length; i++)
    {
        int place=0;
        for (int j=0; j<array.length;j++)
        {
            if (array[i]> array[j])
            {
                place = place+1;
            }
        }
      array2[place] = array[i];
    }
    return array2;
}

I made a simple test for your algorithm and it fails in 1\3 out of 100 test cases. Mostly because test case has
1) Duplicates
2) Zero

   public static void main(String[] args) {
        int failed = 0;
        int succeeded = 0;
        for (int i = 0; i < 100; i++) {
            //"Unordered array"
            int[] unOrdArr = new int[10];
            for (int j = 0; j < unOrdArr.length; j++) {
                int val = (int) Math.ceil(Math.random() * 100);
                unOrdArr[j] = val;
            }
            //Sorted by suggested algorithm
            int [] ordArr = orderArray(unOrdArr);
            //Sorted by internal lib
            int [] intrnSortArr = Arrays.copyOf(unOrdArr, unOrdArr.length);
            Arrays.sort(intrnSortArr);
            if(Arrays.equals(ordArr, intrnSortArr)) {
                succeeded++;
            } else {
                failed++;
                System.out.println("Failed");
                System.out.println(Arrays.toString(unOrdArr));
                System.out.println(Arrays.toString(ordArr));
                System.out.println("---------");
            };
        }
        System.out.println("Successfully sorted: " + succeeded);
        System.out.println("Failed to sort: " + failed);
    }

Answer 6

Note that heap sort, merge sort, or quick sort are faster than the type of sort used in the question.

I updated vmarinescu's code with a third array used to handle duplicates. Note this is a slow method.

public static int[] OrderArray(int[] array){
    int[] array2=new int[array.length];
    int[] stored=new int[array.length];     // used to handle duplicates
    for (int i=0; i<array.length; i++)
    {
        int place=0;
        for (int j=0; j<array.length;j++)
        {
            if (array[i]> array[j])
                place = place+1;
        }
        while(stored[place] != 0)           // skip duplicates
            place += 1;
        array2[place] = array[i];
        stored[place] = 1;
    }
    return array2;
}

---

As an alternative, cycle sort is similar, but sorts in place (it doesn't need a second array).

https://en.wikipedia.org/wiki/Cycle_sort

public static void cyclesort(int a[])
{
int n = a.length;
int i, j, p;                            // used for indexing
int e, t;                               // used to hold array elements
    for (j = 0; j < n - 1; j++) {
        e = a[j];                       // e = 1st element of a cycle
        p = j;                          // p = position to store e
        for(i = j+1; i < n; i++){       // advance p to 1st element >= e
            if(a[i] < e)
                p += 1;
        }
        if(p == j)                      // if p not changed, e is in place
            continue;                   //   continue with next element
        while(e == a[p])                // skip any duplicates
            p += 1;
        t = a[p];                       // swap(e, a[p])
        a[p] = e;
        e = t;                          //   e = next element in this cycle
        while(p != j){                  // continue this cycle
            p = j;
            for(i = j+1; i < n; i++){   //   advance p to 1st element >= e
                if(a[i] < e)
                    p += 1;
            }
            while(e == a[p])            //   skip any duplicates
                p += 1;
            t = a[p];                   //   swap(e, a[p])
            a[p] = e;
            e = t;                      //     e = next element in this cycle
        }
    }
}  

Answer 7

I made a video on youtube look at hawaiideveloper's solution:

package SortingArrayFun;

import java.util.Arrays;

public class SortAnArrayAscending {

public static void main(String[] args) {
    int [] originalArray = {13, 54, 60, 33, 20, 1, 4, 2, 5, 6, 9, 10, 23}; // The original Array
    int totalOfElements = originalArray.length; // Counts the amount of elements in this array which should be 13
    System.out.println("The amount of elements in this array is: " + originalArray.length);
    

    for(int outerLoopCounter = 0; outerLoopCounter <= totalOfElements;  outerLoopCounter++) { // we need this to cycle the same amount of times
        //as the totalOfElements
            for(int leftIndexer = 0;  leftIndexer < (totalOfElements -1);  leftIndexer++) { // this does the action of moving the index to the left
                int rightIndexer = leftIndexer + 1; // this will make the index go right
                int positionA = originalArray[leftIndexer]; // store the output of each element that comes from the left pointer aka left index
                int positionB = originalArray[rightIndexer]; // store the output of each element that comes from the right pointer aka right index
                
                        //Control Flow aka Decision Maker if position B is less than position A... please swap them
                                if(positionB < positionA) { // control flow 
                                        originalArray[leftIndexer] = positionB; // then swap them and make position on the right go to position on left
                                        originalArray[rightIndexer] = positionA; // do the opposite of what position B does
                }
        }
}
    
    System.out.println(Arrays.toString(originalArray));  //prints the array on one line
    
}

}