current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

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
    }
}
share|improve this question

migrated from stackoverflow.com Nov 4 '13 at 0:03

This question came from our site for professional and enthusiast programmers.
    
Check the Program with nums={5,4,3,2,1}, does not work. –  Daniel Oct 17 '13 at 23:30
    
The program works. i-=1 would not work. –  BevynQ Oct 17 '13 at 23:35
    
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. –  BevynQ Oct 17 '13 at 23:40
    
Speaking of sorts, here is a nice visualization of sort algorithms youtube.com/watch?v=kPRA0W1kECg –  Max Dec 9 '13 at 14:32

3 Answers 3

up vote 1 down vote

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.

share|improve this answer
1  
You forgot my personal favorite; bogo sort. –  Max Dec 9 '13 at 14:32
up vote 0 down vote

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.

share|improve this answer
    
What if he wants to learn how to sort? –  Jeroen Vannevel Oct 17 '13 at 23:32
    
I would definitely go with implementing a merge sort algorithm. en.wikipedia.org/wiki/Merge_sort worst case is O(n log n) –  Alex Goja Oct 17 '13 at 23:36
    
@alex or quicksort - it's a classic. –  Bohemian Oct 17 '13 at 23:48
1  
@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). –  scottb Oct 17 '13 at 23:51
    
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. :) –  Alex Goja Oct 17 '13 at 23:54
up vote -1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.