Manually Sorting an Array in Ascending Order

I have a homework assignment to sort an array in ascending order. Obviously, this is to be done manually without using any kind of sort() function.

I figured to do it, I would need two for loops: the first one will loop through the existing array and create a temporary value with the value and index of the array. The second loop will compare the temporary values to the existing values and sort them. I keep trying to write the code, but I just can’t seem to get it right. Here is the latest method I came up with:

public int[] sortArray (int[] inArray) { //Construct the array we're using here int[] newArray = inArray; for(int x = 0; x < a.length; x++) //a.length = # of indices in the array { int tempValue = a[x]; int tempIndex = x; for(int y = 0; y < a.length; y++) { if(tempValue < a[y]) { newArray[x] = tempValue; } } } return newArray; } 

I’m pretty sure this is incorrect, but if someone could push me in the right direction it would be very appreciated!

6 Answers

You have a nearly OK version of the Selection Sorter. You need to start your y at x+1, not at 0. Otherwise you're re-scanning the sorted portion of the array. You should also note that selection sort is an in-place algorithm; if you are looking to make a copy of the array, you should use Arrays.copy method, otherwise int[] newArray = inArray; is creating an alias, not a copy. Finally, the if statement in the nested loop should swap a[x] and a[y], not simply put tempValue in:

if(newArray[x] < newArray [y]) { int tempValue = newArray[y]; newArray[y] = newArray[x]; newArray[x] = tempValue; } 

int minval = input[0]; int temp=0; for(int i = 0; i< input.length; i++) { for(int j = 0; j< input.length-1; j++) { if(input[j+1]<input[j]) { temp=input[j+1]; input[j+1]=input[j]; input[j]=temp; } } } 

Instead of trying to invent your own sorting algorithm, I'd urge you to study what already exists. There's a ton of prior art on this.

Take a look at the Wikipedia article: Sorting algorithm.

Bubble sort is very easy to implement, but has quadratic complexity (the same as your current attempt).

Quicksort isn't too hard to implement either, and has better average complexity.

The sorting you are trying to achieve is called Bubble sort - the wikipedia entry is pretty good you should read it. Though, it's never really used because there is better alternative - Insertion sort (An example is Timsort in Python which is a hybrid of Merge sort and Insertion sort). These two are the basic algorithms that fits your idea with two loops, hence O(n²) complexity.

You should also consider different algorithms for your assignment or, at least, be aware of:

• Merge sort
• Quicksort

Hope it helps.

int arr[] = new int[]{10, 20, 5, 6, 30, 1, 2}; boolean bool = true; int t = 0; while (bool) { for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { int c = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = c; t++; } } if (t == 0) { bool = false; } t = 0; } for (int y : arr) { System.out.println(y); } 

int[] number = { 1,2,1,3,5,4 }; int temp; for (int i = 0; i < number.length; i++) { for (int j = i + 1; j < number.length; j++) { if (number[i] > number[j]) { temp = number[i]; number[i] = number[j]; number[j] = temp; } } } for (int i = 0; i <number.length; ++i) System.out.println(number[i]); }