Использование сортировки слиянием в ArrayList и LinkedList: Java - PullRequest
Новая
       11

Использование сортировки слиянием в ArrayList и LinkedList: Java

0 голосов
/ 04 мая 2011

Мне нужно отсортировать список из 1000 int с сортировкой слиянием; из того, что я могу сказать, мой алгоритм выглядит так, как будто он должен работать, но когда я распечатываю «отсортированный» список, он все равно не сортируется. Я действительно в замешательстве, и мне было интересно, кто-нибудь может указать мне в правильном направлении Вот мой код: 

package edu.neumont.csc250;

import java.util.Random;

import edu.neumont.csc250.LinkedList.Node;


public class Tester {

    ArrayList<Integer> arrayList1000;
    ArrayList<Integer> arrayList10000;
    ArrayList<Integer> arrayList100000;

    LinkedList<Integer> linkedList1000;
    LinkedList<Integer> linkedList10000;
    LinkedList<Integer> linkedList100000;

    public Tester(){}

    public void createLists(){
        arrayList1000 = new ArrayList<Integer>();
        arrayList1000 = populateRandoms(arrayList1000, 1000);
        arrayList10000 = new ArrayList<Integer>();
        arrayList10000 = populateRandoms(arrayList10000, 10000);
        arrayList100000 = new ArrayList<Integer>();
        arrayList100000 = populateRandoms(arrayList100000, 100000);

        linkedList1000 = new LinkedList<Integer>();
        linkedList1000 = populateRandoms(linkedList1000, 1000);
        linkedList10000 = new LinkedList<Integer>();
        linkedList10000 = populateRandoms(linkedList10000, 10000);
        linkedList100000 = new LinkedList<Integer>();
        linkedList100000 = populateRandoms(linkedList100000, 100000);
    }

    public ArrayList<Integer> populateRandoms(ArrayList<Integer> list, int size){
        Random r = new Random();

        for(int i = 0; i < size; i++){
            list.add(r.nextInt(1000) + 1);
            //System.out.println(list.get(i));
        }
        return list;
    }

    public LinkedList<Integer> populateRandoms(LinkedList<Integer> list, int size){
        Random r = new Random();

        for(int i = 0; i < size; i++){
            list.add(r.nextInt(1000) + 1);
            //System.out.println(list.get(i));
        }
        return list;
    }

    public void arraySearches(){
        System.out.println("STARTING SEARCH OF 1000 INTEGERS...");

        long startTime = System.nanoTime();
        long endTime;
        try {
            System.out.println(sequentialSearch(arrayList1000, 123));
            if(sequentialSearch(arrayList1000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList1000.get(sequentialSearch(arrayList1000, 123)));
            }
        } finally {
            endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 10000 INTEGERS...");

        long startTime2 = System.nanoTime();
        long endTime2;
        try {
            System.out.println(sequentialSearch(arrayList10000, 123));
            if(sequentialSearch(arrayList10000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList10000.get(sequentialSearch(arrayList10000, 123)));
            }
        } finally {
            endTime2 = System.nanoTime();
            long duration2 = endTime2 - startTime2;
            System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 100000 INTEGERS...");

        long startTime3 = System.nanoTime();
        long endTime3;
        try {
            System.out.println(sequentialSearch(arrayList100000, 123));
            if(sequentialSearch(arrayList100000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList100000.get(sequentialSearch(arrayList100000, 123)));
            }
        } finally {
          endTime3 = System.nanoTime();
            long duration3 = endTime3 - startTime3;
            System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }
    }

    public void linkedSearches(){
        System.out.println("STARTING SEARCH OF 1000 INTEGERS...");

        long startTime = System.nanoTime();
        long endTime;
        try{
            System.out.println(sequentialSearch(linkedList1000, 123));
            if(sequentialSearch(linkedList1000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList1000.get(sequentialSearch(linkedList1000, 123)));
            }
        } finally {
            endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 10000 INTEGERS...");

        long startTime2 = System.nanoTime();
        long endTime2;
        try{
            System.out.println(sequentialSearch(linkedList10000, 123));
            if(sequentialSearch(linkedList10000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList10000.get(sequentialSearch(linkedList10000, 123)));
            }
        } finally {
            endTime2 = System.nanoTime();
            long duration2 = endTime2 - startTime2;
            System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 100000 INTEGERS...");

        long startTime3 = System.nanoTime();
        long endTime3;
        try{
            System.out.println(sequentialSearch(linkedList100000, 123));
            if(sequentialSearch(linkedList100000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList100000.get(sequentialSearch(linkedList100000, 123)));
            }
        } finally {
            endTime3 = System.nanoTime();
            long duration3 = endTime3 - startTime3;
            System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }
    }

    public void arraySorts(){
        arrayList1000 = mergeSort(arrayList1000);
        for(int i = 0; i<1000; i++){
            System.out.println(arrayList1000.get(i));
        }
    }

    public void linkedSorts(){
//      linkedList1000 = mergeSort(linkedList1000);
//      for(int i = 0; i<1000; i++){
//          System.out.println(arrayList1000.get(i));
//      }
    }

    public ArrayList<Integer> mergeSort(ArrayList<Integer> list){
        ArrayList<Integer> first = new ArrayList<Integer>();
        ArrayList<Integer> second = new ArrayList<Integer>();
        ArrayList<Integer> sortedList = null;

        System.out.println("MERGE SORTING...");
        if(list.size() > 1){
            for(int i = 0; i<(list.size()/2); i++){
                first.add(list.get(i));
            }
            for(int j = list.size()/2; j<list.size(); j++){
                second.add(list.get(j));
            }
            mergeSort(first);
            mergeSort(second);
        }
        sortedList = merge(first, second);


        return sortedList;
    }

    public ArrayList<Integer> merge(ArrayList<Integer> first, ArrayList<Integer> second){
        ArrayList<Integer> newList = new ArrayList<Integer>();

        int i = 0;
        int j = 0;

        while(i<first.size() && j<second.size()){
            if(first.get(i) <= second.get(j)){
                newList.add(first.get(i));
                i++;
            }
            else{
                newList.add(second.get(j));
                j++;
            }
        }
        if(i==first.size()){
            for(int k = j; k<second.size(); k++){
                newList.add(second.get(k));
            }
        }
        else{
            for(int l = i; l<first.size(); l++){
                newList.add(first.get(l));
            }
        }
//      while(i<first.size()){
//          for(int i : first){
//              
//          }
//          newList.add()
//      }
//      while(j<second.size()){
//          
//      }

        return newList;
    }

    public List<Integer> mergeSort(LinkedList<Integer> list){
        return list;
    }

    public int sequentialSearch(ArrayList<Integer> list, int key){
        for(int i = 0; i < list.size()-1; i++){
            if(list.get(i).equals(key)){
                return i;
            }
        }
        return -1;
    }

    public int sequentialSearch(LinkedList<Integer> list, int key){
        Node current = list.head;
        for(int i = 0; i < list.size()-1; i++){
            if(current.content.equals(key)){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Tester t = new Tester();
        t.createLists();
        //t.arraySearches();
        //t.linkedSearches();
        t.arraySorts();
        //t.linkedSorts();
    }
}

Ответы [ 4 ]

2 голосов
/ 04 мая 2011

Я думаю, вы должны заменить 

mergeSort(first);
mergeSort(second);

от 

first = mergeSort(first);
second = mergeSort(second);
1 голос
/ 04 мая 2011

В mergeSort(ArrayList<Integer> list), когда список содержит только 1 элемент, вы игнорируете его и пытаетесь объединить пустые массивы first и second.

Если вы проверите размер возвращенного отсортированного массива, вы должны заметить, что в нем, возможно, отсутствуют некоторые элементы.

1 голос
/ 04 мая 2011

ваша mergeSort функция ничего не делает, кроме как возвращает список. 

public List mergeSort(LinkedList list) {
    return list;
}

Как вы ожидаете, что это отсортировать?

0 голосов
/ 04 мая 2011

Я прошел по вашему коду с помощью отладчика и обнаружил одну ошибку. 

first = mergeSort(first);
second = mergeSort(second);

После этого у вас возникла проблема, вам нужно правильно обработать один элемент. 

public ArrayList<Integer> mergeSort(ArrayList<Integer> list) {
    System.out.println("MERGE SORTING...");
    if (list.size() < 2)
        return new ArrayList<Integer>(list);

    ArrayList<Integer> first = new ArrayList<Integer>(list.subList(0, list.size() / 2));
    ArrayList<Integer> second = new ArrayList<Integer>(list.subList(list.size()/2, list.size()));

    return merge(mergeSort(first), mergeSort(second));
}
...