Sorting integer array

Question

Please check this program that sorts an integer array. It doesn't look very efficient. Please tell me how to correct this.

int temp;
for(int i=0;i<nums.length-1;i++)
{
 if(nums[i]>nums[i+1])// if this is true, swap the value
 {
 temp=nums[i];
 nums[i]=nums[i+1];
 nums[i+1]=temp;
 i=-1;//If there is swap happen, loop will start again from 0th element
 }
}

• Daniel: Check the Program with nums={5,4,3,2,1}, does not work.
• BevynQ: The program works. i-=1 would not work.
• BevynQ: Welcome to the wonderful world of code analysis. Which is outside the realm of stackoverflow. Efficiency depends on your expected input. If you expect sorted data then this is the best. If you expect unsorted data then it is close to being the worst.
• Max: Speaking of sorts, here is a nice visualization of sort algorithms youtube.com/watch?v=kPRA0W1kECg

Answer 1

Here are some links to sorting techniques: bubble sort , insertion sort, merge sortWhat you're doing in your code isn't efficient. In the worst case scenario where the array is totally unsorted it'll take quite sometime to sort it the way you're doing it.

• Max: You forgot my personal favorite; bogo sort.

Answer 2

Ok, you might not be aware, but you will be now, Arrays has its own sort method you can use if you want to. Look at the Arrays java documentation! And in terms of efficiency I think java has that covered for you.

• Jeroen Vannevel: What if he wants to learn how to sort?
• Alex Goja: I would definitely go with implementing a merge sort algorithm. en.wikipedia.org/wiki/Merge_sort worst case is O(n log n)
• Bohemian: @alex or quicksort - it's a classic.
• scottb: @AlexGoja: For small numbers of elements (where n is, say, less than a few hundred) it is not wrong to view the time complexity is O(n log n) + V where V represents the algorithm overhead. For small values of n, it can be as performant (or even more performant) to utilize simpler sorting algorithms. For large n, as you've pointed out, V becomes insignificant and the complexity is O(n log n).
• Alex Goja: Correct. I should have mentioned perhaps that I choose the algorithm that always has the best running time in the worst case situation since he hinted he wanted a more efficient way of doing sorting. However, I see the worst case for quick sort is rarely the case so you could go with quick sort, too. :)

Answer 3

Your algorithm does not look like a viable array sorting algorithm. Perhaps there are some data sets that it would be able to yield a correct result on, but I do not think it would yield correct results for arbitrary data sets. Maybe it's alright ... without working through it all I can say is that it's an unusual solution.

Following is the pseudo-code for a conceptually very simple sorting algorithm called the "Delayed Replacement Sort" (or, perhaps more commonly, the "Selection Sort"):

Begin DELAYEDSORT
 For ITEM=1 to maximum number of items in list-1
 LOWEST=ITEM
 For N=ITEM+1 to maximum number of items in list
 Is entry at position N lower than entry at position LOWEST?
 If so, LOWEST=N
 Next N
 Is ITEM different from LOWEST
 If so, swap entry at LOWEST with entry in ITEM
 Next ITEM
End DELAYEDSORT

You should be able to easily adapt this pseudo-code into a Java method. Note that this algorithm has two loops:

• the outer loop is finished when the whole array has been sorted
• the inner loop finds the "lowest" element in the portion of the array that is still unsorted.

After the inner loop, a check is made to see if a swap needs to be made. It is this step that gives the algorithm its name; swapping is only done if it needs to be done to order the element indicated by the index of the outer loop.

Good luck.