1
\$\begingroup\$

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
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Check the Program with nums={5,4,3,2,1}, does not work. \$\endgroup\$
    – Daniel
    Oct 17, 2013 at 23:30
  • \$\begingroup\$ The program works. i-=1 would not work. \$\endgroup\$
    – BevynQ
    Oct 17, 2013 at 23:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – BevynQ
    Oct 17, 2013 at 23:40
  • \$\begingroup\$ Speaking of sorts, here is a nice visualization of sort algorithms youtube.com/watch?v=kPRA0W1kECg \$\endgroup\$
    – Max
    Dec 9, 2013 at 14:32

3 Answers 3

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You forgot my personal favorite; bogo sort. \$\endgroup\$
    – Max
    Dec 9, 2013 at 14:32
0
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ What if he wants to learn how to sort? \$\endgroup\$ Oct 17, 2013 at 23:32
  • \$\begingroup\$ I would definitely go with implementing a merge sort algorithm. en.wikipedia.org/wiki/Merge_sort worst case is O(n log n) \$\endgroup\$
    – Alex Goja
    Oct 17, 2013 at 23:36
  • \$\begingroup\$ @alex or quicksort - it's a classic. \$\endgroup\$
    – Bohemian
    Oct 17, 2013 at 23:48
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – scottb
    Oct 17, 2013 at 23:51
  • \$\begingroup\$ 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. :) \$\endgroup\$
    – Alex Goja
    Oct 17, 2013 at 23:54
-1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.