CODEWITHSUNDEEP
javaalgorithmmergemergesort
Chris V.
Chris V.

Reputation: 1143

Using Merge Sort on ArrayList and LinkedList : Java

I need to sort a list of 1000 ints with a merge sort; from what I can tell, my algorithm looks like it should work, but when I print out the 'sorted' list, it's still not sorted. I'm really stumped, and I was wondering if anybody could point me in the right direction. Here's my code:

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();
    }
}

Upvotes: 0

Views: 5675

Answers (4)

Peter Lawrey
Peter Lawrey

Reputation: 533530

I stepped through you code with a debugger and found one bug.

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

after that you have an issue there you need to handle one element correctly.

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));
}

Upvotes: 0

proactif
proactif

Reputation: 11721

I think you should replace

mergeSort(first);
mergeSort(second);

by

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

Upvotes: 2

Milan
Milan

Reputation: 15849

In mergeSort(ArrayList<Integer> list) when the list contains only 1 element, you ignore it and try to merge first and second arraylist which are empty.

If you check the size of the returned sorted arraylist, you should notice that it probably is missing some elements.

Upvotes: 1

Jordan
Jordan

Reputation: 5058

your mergeSort function doesn't do anything except return the list.

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

How do you expect it to sort?

Upvotes: 1

Related Questions