3
\$\begingroup\$

I recently started to do some of the exercises in CodeChef and I did the TurboSort challenge here is it's description. It works fine with smaller arrays but can't pass some of the tests due to the fact it's \$O(n^2)\$, so I need a faster way to sort them.

import java.util.Scanner;


public class TurboSort {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int arrSize = scan.nextInt();
        int[] nums = new int[arrSize];
        for(int i = 0; i < arrSize; i++ ){
            nums[i] = scan.nextInt();
        }

        for(int j = 0; j < arrSize; j++){
            for(int a = j; a < arrSize; a++){
                if(nums[j] > nums[a]){
                    int swap = nums[j];
                    nums[j] = nums[a];
                    nums[a] = swap;
                }
            }
        }
    for(int p = 0; p < arrSize; p++){
        System.out.println(nums[p]);
    }
    }

}

How can I improve it so it can run fast even with bigger arrays?

\$\endgroup\$
1
\$\begingroup\$

It looks like you're using an algorithm that checks every element of an array above a given value, and every time it finds a smaller one it swaps them. This is very inefficient (very similar to bubblesort in its time complexity) This website contains a very helpful list of various sorting algorithms and there time/space complexities, try implementing one of them (I'd go for quicksort) for a faster result.

As for your code, it looks good. The only thing I noticed was that there was no real need to use 4 variables as loop counters; you only really need 2. I actually disagree with Phrancis's point about renaming the variables, I think that for loop counters (ONLY loop counters, mind you), single letter variable names are okay, and his suggested changes actually make the code even harder to read.

\$\endgroup\$
2
\$\begingroup\$

Looking at your code, I'm not sure how to improve performance, but I think readability could be improved.

Naming things

Here are some variables you use:

for(int i = 0; i < arrSize; i++ ){
// snip
for(int j = 0; j < arrSize; j++){
    for(int a = j; a < arrSize; a++){
//snip
for(int p = 0; p < arrSize; p++){

i, j, a and p carry no meaning. Perhaps it would be better to use names that describe what the variables represent. An example, adapt as needed:

for(int arrayNumScan = 0; arrayNumScan < arrSize; arrayNumScan++ ){
// snip
for(int arrayIndex = 0; arrayIndex < arrSize; arrayIndex++){
     for(int arrayIndexNum = arrayIndex; arrayIndexNum < arrSize; arrayIndexNum++){
// snip
for(int printArrayData = 0; printArrayData < arrSize; printArrayData++){
\$\endgroup\$
  • \$\begingroup\$ You may check it now :) \$\endgroup\$ – nitheism Mar 22 '15 at 0:36
  • \$\begingroup\$ Please see this post. I rolled back your post edits for this reason. \$\endgroup\$ – Phrancis Mar 22 '15 at 0:47
  • \$\begingroup\$ okey thanks then I will have in mind the namin next time :) \$\endgroup\$ – nitheism Mar 22 '15 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.