Learneroo

Sorting Algorithms Comments

Comments

Bolke
Jul 30, 3:57 PM

I utterly & completely do not understand how to deal with the input here.
Could one please see an example in code?
I notice my comments haven't been answered, lately, but I really would like this one answered, because I can't move on. Thanks.
Learneroo
Jul 31, 5:26 PM

Here's a simple solution to this problem: my code. You just need to print the sum of each list of numbers.
Bolke
Jul 31, 5:56 PM

Well it's not actually the solution I was after, but the input method. It says:

The input for these challenges will follow the format summarized in the sidebar.
cont...
Then in the sidebar I see:

Input Format for standard Sorting Challenges:

t - the number of test cases s - the size of the array ar - the list of integers

But on the other hand:
Each test case will contain 2 lines:
N - the number of elements in a list.
N numbers will follow.

Should we construct a Scanner object and take input from that? I really don't follow.
David
Jun 18, 3:02 PM

Dear Admin,

As what i can see from the "Your Output" it is the same as "Correct Output", however the last array is not displayed so im not sure if im getting "Incorrect" due to the last array or something else.

cont...
Could the ''Your Output' output be increased to all results? I want to make sure i'm not getting "Incorrect" due to the last array.

Thanks
Learneroo
Jun 18, 3:09 PM

@David, it displays all the output. Make sure you're printing the final steps too.
David
Jun 18, 4:12 PM

Thanks Admin, i noticed just now... double checking on my end needs to be improved.
Rod
Nov 17, 2:29 PM

Received this runtime error.
Exception in thread "main" java.util.InputMismatchException
at java.util.Scanner.throwFor(Scanner.java:909)
at java.util.Scanner.next(Scanner.java:1530)
cont...
at java.util.Scanner.nextInt(Scanner.java:2160) at java.util.Scanner.nextInt(Scanner.java:2119) at Main.main(Main.java:25)

Main is only scanning for integers but the input includes strings.
Learneroo
Nov 18, 12:37 PM

@Rod, sorry, new code to scan the input has been added. You can click "Reset Code" to load it.

mike

public static void doStuff(Blob[] ar){
    String[] result = countingSort(ar);
    for(int i=0; i<result.length;i++){
    System.out.print(result[i] + " ");

cont...

    }
    System.out.println();
}

public static String[] countingSort(Blob[] ar){
    int[] counts = new int[100];

    for(int i = 0; i < ar.length; i++){
      counts[ar[i].num]++;
    }
    int[] locations = new int[100];
    locations[0] = counts[0];
    for(int i = 1; i < counts.length ; i++){
      locations[i] = counts[i] + locations[i-1];
    }

    String[] output = new String[ar.length];
    for(int i = 0; i < ar.length; i++){
      int count = counts[ar[i].num];
      int location = locations[ar[i].num];
      int actualLocation = location - count;
      output[actualLocation] = ar[i].string;
      counts[ar[i].num]--;
    }

    return output;
}

Rod
Nov 18, 1:41 PM

Your output partitions about the value at the LEFT of the array, not the RIGHT as specified in the challenge description

Viktor Ayadi

Aug 7, 8:51 AM

Can anyone tell me what is the problem with the code:

static void doStuff(int[] ar){
    int pivotValue, storeIndex;
    int left = 0; int right = ar.length - 1;

cont...

    pivotValue = ar[left];
    storeIndex = left;

    for (int i = left + 1; i <= right; i++) {
        if (ar[i] < pivotValue) {
            storeIndex++;
            swap(ar, i, storeIndex);
        }
    }

    swap(ar, left, storeIndex);
    printAr(ar);        
}

For the first input it gives back the following output:
1 3 4 9 5
I think this is also correct... Am I right?

Learneroo
Aug 7, 10:41 AM

In this challenge, note the elements should otherwise remain in the same order (see correct output).
Viktor Ayadi
Aug 8, 7:46 AM

Thank you for your answer. Can you give me a hint, howto modify the code to keep the lower and higher elements in such order?

Viktor Ayadi

Aug 8, 8:07 AM

I've solved it, but in a not too efficient way:

static void doStuff(int[] ar){
    int pivotValue;

    int left = 0; int right = ar.length - 1;

cont...

    int[] tmp = new int[ar.length];
    int i = left + 1, j = 0;

    pivotValue = ar[left];

    for (int i = left + 1; i <= right; i++) 
        if (ar[i] < pivotValue) {
            tmp[j] = ar[i];
            j++;
        }

    tmp[j] = pivotValue; j++;


    for (int i = left + 1; i <= right; i++) 
        if (ar[i] >= pivotValue) {
            tmp[j] = ar[i];
            j++;
        }

    ar = tmp;

    printAr(ar);        
}

I think the previous algorithm is much more efficient.

Learneroo
Aug 8, 10:04 AM

After getting it correct, you can view the featured answer(s) for a possible solution:
http://www.learneroo.com/modules/4/nodes/44/featured-submissions

(The sort only becomes efficient in Quick-Sort Advanced.)

Ankit

Mar 16, 7:46 PM

correct answer for the first input should be 3 1 4 9 5

public static int partition(int[] a, int lo, int hi) {
    int i = lo + 1;
    int j = hi;

cont...

    while(i < j) {
        while(a[i] < a[lo]) i++;
        while(a[j] > a[lo]) j--;
        if(i < j) {
          swap(a, i, j);
        }
    }
    swap(a, lo, j);
    return j;
}

public static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void doStuff(int[] ar){
    int j = partition(ar, 0, ar.length - 1);
    for(int elem: ar) {
        System.out.print(elem + " ");
    }
    System.out.println();
}

Learneroo
Mar 16, 7:50 PM

Since this is just the first step in quicksort, the array should otherwise remain in the same order. So since the 5 is before the 9 in the input, it should be before the 9 in the output.

mike

Aug 31, 3:23 PM

static void doStuff(int[] ar){
    int pivot = ar[0];
    int pivotLocation = 0;
    for(int i = 1; i < ar.length; i++){
        int curr = ar[i];
        if(curr < pivot){

cont...

            for(int j = i; j > pivotLocation; j--){
                ar[j] =ar[j-1];
            }
            ar[pivotLocation] = curr;
            pivotLocation++;
        }
    }
    for (int i=0; i<ar.length; i++){
        System.out.print(ar[i] + " ");
    }
    System.out.println();
}

mike

Aug 31, 3:22 PM

static void doStuff(int[] ar){
    int pivot = ar[0];
    int pivotLocation = 0;
    for(int i = 1; i < ar.length; i++){
        int curr = ar[i];
        if(curr < pivot){

cont...

            for(int j = i; j > pivotLocation; j--){
                ar[j] =ar[j-1];
            }
            ar[pivotLocation] = curr;
            pivotLocation++;
        }
    }
    for (int i=0; i<ar.length; i++){
        System.out.print(ar[i] + " ");
    }
    System.out.println();
}

mike

Aug 31, 4:20 PM

static void doStuff(int[] ar){
partition(ar, 0, ar.length - 1);
}

static void partition(int[] ar, int min, int max){
    int pivot = ar[min];

cont...

    int pivotLocation = min;

    for (int i = min; i <= max; i++){
      int curr = ar[i];
      if(curr < pivot){
        for(int j = i; j > pivotLocation; j--){
          ar[j] =ar[j-1];
        }
        ar[pivotLocation] = curr;
        pivotLocation++;
      }
    }

    if (pivotLocation > min + 1){
      partition(ar, min, pivotLocation-1);
    }

    if ((max - pivotLocation) > 1){
      partition(ar, pivotLocation+1, max);
    }
    printArray(ar, min, max);
}

static void printArray(int[] ar, int min, int max){
    for(int i = min; i <= max; i++){
        System.out.print(ar[i] + " ");
    }

    System.out.println();
}

Kendall Ponder
Jun 23, 6:52 PM

Shouldn't the correct output on the first line be 1 3 2 5 9 8 7? The 8 comes before the 7 in the input.
Learneroo
Jun 23, 7:41 PM

@Kendall, in this version of Quicksort, you don't move numbers that are already in their correct half. Since 7 > 5 (the pivot value), it stays where it is.
Kendall Ponder
Jun 24, 9:44 AM

Got it. Is this method faster than using nested for loops and finding the smallest number in the inner loop and then switching it with the left most element (the outer loop moves where the left most element is)?
Learneroo
Jun 24, 9:57 AM

Quicksort is among the fastest sorts in the average case. Technically, it runs in O(n log n) time (see the next Node for a brief look at it's running time). I'm not sure what you're describing, but it sounds like a Selection Sort which would have a O(n²⁾ running time (like Insertion Sort).

cont...
Example:

You have 1M numbers to sort. Quicksort takes ~ O(n log n) time which is 1M*log(1M) =~ 20M operations.
Insertion or Selection Sort would take O(n²⁾ time which is 1M² or 10¹² operations.
Kendall Ponder
Jun 24, 1:21 PM

Thanks. The way I have sorted before is:
for(I=0 to end)
min=array(I)
minIndex=i
for(j=I to end)
if(array(I)<min)
Switch array(I) & min and save minIndex
end if
end for
end for
Kendall Ponder
Jun 24, 1:22 PM

Thanks!