using merge sort for string sorting from text file

Question

I am going to write a code for sorting string from text file by mergesort method.

if (l.get(0) <= r.get(0))

at this part appearing a redline. I know it is only for primitive, I tried to use compareTo but can't finish it properly.

enter image description here

private static ArrayList<String> mergeSort(ArrayList<String> lines) {
        if (lines.size() <= 1) {
            return lines;
        }
        ArrayList<String> left = new ArrayList<String>();
        ArrayList<String> right = new ArrayList<String>();
        for (String x : lines) {
            if (lines.indexOf(x) < (lines.size()) / 2)
                left.add(x);
            else {
                right.add(x);
            }
        }
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    private static ArrayList<String> merge(ArrayList<String> l, ArrayList<String> r) {
        ArrayList<String> result = new ArrayList<String>();
        while (l.size() > 0 && r.size() > 0) {
            if (l.get(0) <= r.get(0)) {
                result.add(l.get(0));
                l.remove(0);
            }
            else {
                result.add(r.get(0));
                r.remove(0);
            }
        }
        while (l.size() > 0) {
            result.add(l.get(0));
            l.remove(0);
        }
        while (r.size() > 0) {
            result.add(r.get(0));
            r.remove(0);
        }
        return result;
    }

score 1 · Accepted Answer · 2022-03-20 08:22:04Z

String.compareTo()

The Java String class compareTo() method compares the given string with the current string lexicographically. It returns a positive number, negative number, or 0. It compares strings on the basis of the Unicode value of each character in the strings. If the first string is lexicographically greater than the second string, it returns a positive number (difference of character value). If the first string is less than the second string lexicographically, it returns a negative number, and if the first string is lexicographically equal to the second string, it returns 0.

Note:
if string1 > string2, it returns positive number

if string1 < string2, it returns negative number

if string1 == string2, it returns 0

qutoes from gfg.

use compareTo method of String because java doesn't support < & > operators for strings comparisions.

 while (l.size() > 0 && r.size() > 0) {
            if (l.get(0).compareTo(r.get(0))<=0) {
                result.add(l.get(0));
                l.remove(0);
            }
            else {
                result.add(r.get(0));
                r.remove(0);
            }
        }

You are getting SO Excepetion because of indexOf if suppose list has {"A", "A", "C", "A"} then indexOf("A") will return 0 ever time you call it.

if (lines.indexOf(x) < (lines.size()) / 2)
                left.add(x);
            else {
                right.add(x);
            }

code

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;


public class MergeSort{
        final static PrintStream out = System.out;


        private static ArrayList<String> mergeSort(ArrayList<String> lines) {
                if (lines.size() <= 1) {
                        return lines;
                }
                ArrayList<String> left = new ArrayList<String>(lines.subList(0, lines.size()/2));
                ArrayList<String> right = new ArrayList<String>(lines.subList(lines.size()/2, lines.size()));

                /*for (String x : lines) {
                        if (lines.indexOf(x) < (lines.size()) / 2)
                                left.add(x);
                        else {
                                right.add(x);
                        }
                }*/
                /*for(int i =0 ;i<lines.size()/2;i++)
                        left.add(lines.get(i));
                for(int i = lines.size()/2;i<lines.size();i++)
                        right.add(lines.get(i));*/
                left = mergeSort(left);
                right = mergeSort(right);
                return merge(left, right);
        }

        private static ArrayList<String> merge(ArrayList<String> l, ArrayList<String> r) {
                ArrayList<String> result = new ArrayList<String>();
                while (l.size() > 0 && r.size() > 0) {
                        if (l.get(0).compareTo(r.get(0)) <= 0) {
                                result.add(l.get(0));
                                l.remove(0);
                        }
                        else {
                                result.add(r.get(0));
                                r.remove(0);
                        }
                }
                while (l.size() > 0) {
                        result.add(l.get(0));
                        l.remove(0);
                }
                while (r.size() > 0) {
                        result.add(r.get(0));
                        r.remove(0);
                }
                return result;
        }
        //Main
        public static void main(String ... $){
                out.println(mergeSort(new ArrayList<>(Arrays.asList("G", "P",
                                                        "A", "A", "O"))));
        }
}

Output:

$ javac MergeSort.java  && java MergeSort
[A, A, G, O, P]

I changed it thank you. But when I run there is an overflow error like this: Exception in thread "main" java.lang.StackOverflowError at test/test.SortTextFile.mergeSort(SortTextFile.java:99) left = mergeSort(left);
@서비로브자보키르 it shouldn't! could you please show us what is the input?
Dev Parzival thank you! It sorting a little bit slowly, maybe I chose unproper algorithm. Anyway I think it worked

Collectives™ on Stack Overflow

using merge sort for string sorting from text file

1 Answer 1

String.compareTo()

code

Output:

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

String.compareTo()

code

Output:

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related