jeudi 22 mars 2018

One QuickSort algorithm, many ways to choose a pivot and as many problems with it

I got a task to implement a QuickSort algorithm on an ArrayList which can use as a pivot:

  1. Last item of an ArrayList.
  2. Random item of an ArrayList.
  3. Median value of the first one, the last one and the middle value of the ArrayList.

The problem is that only the first way works 100% properly and the rest is making some weird mistakes and I can not find the mistake. Maybe one of you will be able to do it.

import java.io.*;
import java.util.Random;
import java.util.ArrayList;
import java.util.Scanner;
public class Sortowanie {

    ArrayList<Integer> data;

    public Sortowanie(String File) {
        data=new ArrayList<Integer>();
        BufferedReader reader=null;

        try {
            reader = new BufferedReader(new FileReader(File));
            String wiersz = null;
            while((wiersz = reader.readLine()) != null) {
                String [] liczby = wiersz.split(",");
                wiersz.trim();
                for(int i=0; i<liczby.length; i++) {
                    int liczba= Integer.parseInt(liczby[i]);
                    data.add(liczba);
                }
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    public void quicksort( int x, int y, int v) {

        int i,j,temp;

        i=x;
        j=y;
        int pivot=0;
        switch(v) {
        case 0: {
            pivot = y;
            break;
        }
        case 1: {
            Random r=new Random();
            pivot = (r.nextInt(y-x+1))+x;
            break;
        }
        case 2: {
            int naj=x;
            if(data.get((x+y)/2)>data.get(naj)) naj=((x+y)/2);
            if(data.get(y)>data.get(naj)) naj=y;
            pivot=naj;
            break;
            }
        }

        do {
            while (data.get(i)<data.get(pivot))
                i++;
            while (data.get(pivot)<data.get(j))
                j--;
            if (i<=j) {
                temp=data.get(i);
                data.set( i, data.get(j));
                data.set(j, temp);
                i++;
                j--;
            }
        }while (i<=j); 

            if (x<j) {
                quicksort(x,j, v);
            //  System.out.println("while(x<j)");
            }
            if (i<y)
            {
                quicksort(i,y, v);
                //System.out.println("while(i<y)");
            }
        }




Aucun commentaire:

Enregistrer un commentaire