not able to get the sorted array

Question

cannot able to identify my error, checked a-lot pls go through it it does not produce the correct output, the code is implementation of quick sort through java. this code produces the same output as input, as i am new to java and algorithms I am not able to figure it out.

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int a[]=new int[5];
        Scanner s=new Scanner(System.in);

        for(int i=0;i<5;i++)
            a[i]=s.nextInt();

        quick(a,0,4);

        for(int i=0;i<5;i++)
            System.out.print(a[i]+" ");
    }

    public static void quick(int a[],int s,int l)
    {
        if(s<l)
        {
            System.out.println("in quick");

            int pi=part(a,s,l);

            quick(a,s,pi-1);
            quick(a,pi+1,l);

        }
    }

    public static int part(int a[],int s,int l)
    {
        System.out.println("in part");
        int pivot=a[l];
        int pin=s;

        for(int i=s;i<l;i++)
        {
            if(a[i]<=pivot)
            {
                swap(a[i],a[pin]);
                pin++;
            }
        }

        swap(a[pin],a[l]);
        System.out.println(pin);

        return pin;     
    }

    public static void swap(int a,int b)
    {
        System.out.println("in swap");
        int t;
        t=a;
        a=b;
        b=t;
    }
}

hugo · Answer 1 · 2019-08-09T19:47:55.147

2

Your swap function doesn't work, that's why quick leaves your array untouched.

This addresses exactly your issue: Java: Why does this swap method not work? -- those are fundamental concepts and it more than pays to understand them.

Anyway, since you're working on an array, you could go about it like this:

/** Swap array[i] and array[j] */
public static void swap(int[] array, int i, int j)
{
    int t = array[i];
    array[i] = array[j];
    array[j] = t;
}

Note: I haven't delved into the logic of your sorting -- you may be able to figure it out once this is fixed.

edited Aug 09 '19 at 19:47

answered Aug 09 '19 at 19:38

hugo

3,067
2
12
22

when I just replace my function call with the code it works perfectly but when I pass the array to the swap function as mentioned by you it somehow generates array index out of bounds exception. – Vortex Aug 09 '19 at 20:16

score 1 · Accepted Answer · answered Aug 09 '19 at 19:40

You're not actually swapping array elements when calling swap. All the method is doing is swapping the parameters.

You could either pass the array into the swap method along with the indices, or more practically, just copy your swap code into your part method

score 0 · Answer 3 · answered Nov 17 '20 at 16:14

I have no idea whether you are learning QuickSort, but if you want a quick way to sort a list of numbers, I'd suggest you to use an ArrayList, which is basically declared like this:

ArrayList<Integer> yourArrayList = new ArrayList<Integer>();

Among the diamond operator (<>) insert the data type, in this case is Integer, but you could also insert Double, to obtain a decimal result.

After you declared it, you have to add your numbers:

yourArrayList.add(1)
 yourArrayList.add(3);

etc...

When you are done use Collections.sort(yourArrayList);

I hope I was clear, this is the code to use it:

   ArrayList<Integer> yourArrayList = new ArrayList<Integer>();
 
   yourArrayList.add(10);
   yourArrayList.add(3);
   yourArrayList.add(7);
   yourArrayList.add(-3);
   
   Collections.sort(yourArrayList);
   System.out.println(yourArrayList);

not able to get the sorted array

3 Answers3