• ,

level06.lesson11.bonus03

Выводит всё правильно, но проверку не проходит. В чем может быть причина?
/* Задача по алгоритмам
Задача: Написать программу, которая вводит с клавиатуры 5 чисел и выводит их в возрастающем порядке.
Пример ввода:
3
2
15
6
17
Пример вывода:
2
3
6
15
17
*/

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader  = new BufferedReader(new InputStreamReader(System.in));

        ArrayList<Integer> i = new ArrayList<Integer>();
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        for(int b = 0; b < 5; b++){
            i.add(Integer.parseInt(rd.readLine()));}

        for(int g = i.size() -1; g >= 2; g--)
        {
             boolean check = true;
            for(int j = 0; j < g; j++)
            {

                if(i.get(j) > i.get(j + 1))
                {
                    int temp = i.get(j);
                    i.set(j, i.get(j+1));
                    i.set(j+1, temp);
                    check = false;

                }



            }
            if(check)
                break;


        }
         for(int h = 0; h <=4;h++)
            System.out.println(i.get(h));


    }

}

level13.lesson11.bonus01

Ребята, гляньте пожалуйста, по какой причине система не принимает решение?

/* Сортировка четных чисел из файла
1. Ввести имя файла с консоли.
2. Прочитать из него набор чисел.
3. Вывести на консоль только четные, отсортированные по возрастанию.
Пример ввода:
5
8
11
3
2
10
Пример вывода:
2
8
10
*/

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Solution
{
    public static void main(String[] args) throws IOException
    {
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println("Input file name:");
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        String name = file.readLine();
        BufferedReader reader = new BufferedReader(new FileReader("D:\\" + name + ".txt"));
        String line;
        while ((line = reader.readLine()) != null)
        {
            if (Integer.parseInt(line) % 2 == 0)
                list.add(Integer.parseInt(line));
        }
            Collections.sort(list);
            for (int i : list)
                System.out.println(i);
    }
}
  • ,

Собери мысли в кучу, или зарядка для ума.

Привет, коллеги! Дойдя до 10 лвл, и не много затянув с оплатой дальнейшего обучения, по причине не больших финансовых трудностей, решил зря время не терять и разобрать наиболее популярные алгоритмы сортировки. Если кому-то будет интересно, чуть позже могу сделать не большой обзор с полезными плюшками.
Так вот, дойдя до сортировки кучей (двоичной) или, как ее еще называют пирамидальной сортировкой (HeapSort), столкнулся с тем, что хотел найти код, описывающий весь алгоритм в одном методе, а не как на WiKi, состоящий из кучи методов. Плюс ко всему код должен был быть понятен и максимально прост. Нашел уже было алгоритм на другом ресурсе, более менее приемлемый, который все-равно пришлось бы чуть подшаманить, но тут наткнулся на видео:
1ч.: www.youtube.com/watch?v=cT5K1wPZfrg
2ч.: www.youtube.com/watch?v=_9er7Vtm8BY
Вот его код в txt: www.dropbox.com/s/btzxx20dpjx1qp2/Heap%20Sort.txt

Фишка в том, что парень написал код (HeapSort), но там есть баг. Он знает об этом, но решения проблемы найти не смог. Мне стало интересно, и я решил расколдовать загадку тени от хрена. В общем, спустя примерно 4 часа мозгового штурма, попутно разбираясь в каждом шаге алгоритма (т.к. изначально я не понимал, как он работает), и отвлекаясь на домашние дела, я победил этот трабл. Код, конечно, я сделал более компактным, и истребил косяки. В итоге все отлично функционирует и сортируется. Рабочий код пока выкладывать не буду, чтобы никого не смущать вариантом быстрого решения задачи. :)

Если вам будет интересно разобраться в этом алгоритме и его баге — Welcome! Задачка интересная. :)
Всем успехов!

Сортировка двумермерного массива

Решаемая задача:
Написать программу, которая генерирует двумерный массив, а затем сортирует его в
порядке возрастания суммы элементов строк.

Код:
public class ThirdQue
{
    public static void main(String[] args){
        int numElem =3;
        int[][] x = new int[numElem][numElem];
        int[][] result = new int[numElem][numElem];
        Random r = new Random();

        int rowCount=0;

        //fill the array
        for(int i =0; i<numElem; i++)
        {
            for(int j = 0; j<numElem; j++)
            {
                x[i][j] = r.nextInt(100);
            }
        }

        //print our array
        System.out.println("Неотсортированный массив:");
        for(int i = 0; i<numElem; i++)
        {
            for(int j = 0; j<numElem; j++)
            {
                System.out.print(x[i][j]+ " ");
            }
            System.out.println();
        }

        int rowCount1;


        //make a dictionary - key - index from array, value - sum of its elements
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < x.length;i++){
            rowCount1=0;
            for (int j = 0; j < x.length;j++){
                 rowCount1+=x[i][j];
            }

            map.put(i,rowCount1);
        }

        Set set = map.entrySet();
        Iterator i = set.iterator();


        //print our dictionary
        while(i.hasNext()){

            Map.Entry me = (Map.Entry)i.next();

            System.out.println(me.getKey() + " : " + me.getValue() );

        }

        int value;
        int min;
        int minIndex;


        //make a result array
        for (int j = 0 ; j < numElem;j ++){
            min = map.get(0);
            minIndex=0;

            //find the lowest sum of arrays row
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){

                  value = entry.getValue();

                 if (value < min){
                     min = value;
                     minIndex=entry.getKey();
                 }
            }

            //remove this row from dictionary
            map.remove(minIndex);
            //write elements in result array
            for (int j1=0; j1<numElem;j1++)    {
                result[j][j1]=x[minIndex][j1];
            }

        }
        //print result
        System.out.println("Отсортированный массив:");
        for(int i2 = 0; i2<numElem; i2++)
        {
            for(int j = 0; j<numElem; j++)
            {
                System.out.print(result[i2][j]+ " ");
            }
            System.out.println();
        }

    }
}


И оно работает, но 50 на 50. 1 раз корректно, в след раз получаем Exception in thread «main» java.lang.NullPointerException с указанием на строку
min = map.get(0);


Если смотреть через дебаг, то проскакивает Disconnected from the target VM, address: '127.0.0.1:52832', transport: 'socket'

Помогите разобраться с чем связано. Какие либо ошибки в коде или что вызывает такие проблемы
  • ,

Обзор и тестирование методов сортировки. Часть I

На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» — метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble (пузырьковая), insertion (вставками), selection (выбором), shell (алгоритм Шелла).
Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы.
  • ,

level07.lesson12.bonus03 Вопрос по сортировке массива.

Добрый день!

Написал такой метод для сортировки по убыванию. Но он не работает. И не могу понять почему. Уже написал другой рабочий, но голову сломал на вопросе, что не так в этом коде.

for(int i = 0; i < array.length; i++){
            for(int j = 1; j < array.length; j++){

                if(array[j] > array[i]){
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }

package com.javarush.test.level08.lesson11.home08;

В чем тут ошибка (программа не компилируется, если алгоритм корректно выдает 5 наибольших чисел?



package com.javarush.test.level08.lesson11.home08;

import SortingAlgo.InsertionSort;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/* Пять наибольших чисел
Создать массив на 20 чисел. Заполнить его числами с клавиатуры. Вывести пять наибольших чисел.
*/

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] array = new int[20];
        for (int i = 0; i < array.length; i++)
        {
            array[i] = Integer.parseInt(reader.readLine());
        }
        sort(array);
        System.out.println(array[0]);
        System.out.println(array[1]);
        System.out.println(array[2]);
        System.out.println(array[3]);
        System.out.println(array[4]);
    }

    public static void sort(int[] array) //insertion sort alg
    {
        for (int i = 1; i<array.length; i++)
        {
            int key = array[i];
            int j = i-1;
            while (j >=0 && array[j] < key)
            {
                array[j + 1] = array[j];
                array[j] = key;
                j--;
            }
        }
    }
}
  • ,

level08.lesson11.bonus03


package com.javarush.test.level08.lesson11.bonus03;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/* Задача по алгоритмам
Задача: Введи с клавиатуры 20 слов и выведи их в алфавитном порядке.
*/

public class Solution
{
public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] array = new String[20];
for (int i = 0; i < array.length; i++)
{
array[i] = reader.readLine();
}

sort(array);

for (String x : array)
{
System.out.println(x);
}
}

public static void sort(String[] array)
{
//Напишите тут ваш код
int start = 0;
int end = array.length - 1;
doSort(array, start, end);
}

private static void doSort(String[] array, int start, int end){
if (start >= end)
return;
int i = start;
int j = end;
int cur = i - (i - j) / 2;
while (i < j)
{
while (i < cur && isGreaterThen(array[cur], array[i]))
{
i++;
}
while (j > cur && isGreaterThen(array[j], array[cur]))
{
j--;
}
if (i < j)
{
String temp = array[i];
array[i] = array[j];
array[j] = temp;

if (i == cur)
cur = j;
else if (j == cur)
cur = i;

}
}
doSort(array, start, cur);
doSort(array, cur + 1, end);
}

//Метод для сравнения строк: 'а' больше чем 'b'
public static boolean isGreaterThen(String a, String b)
{
return a.compareTo(b) > 0;
}
}


Вопрос такой — Решил задачу быстрой сортировкой. Выдало ошибку — программа на сервере выполнялась слишком долго. Переписал пузырьковой, все прошло. Почему так?

Как правильно делать сортировку в Java

Анализируя исходные коды многих opensource Java-проектов, я обнаружил, что большинство разработчиков осуществляют сортировку всего двумя разными способами. Один из них основан на применении метода sort() классов Collections или Arrays, а другой на использовании самосортирующихся структур данных, таких как TreeMap и TreeSet.
  • ,

level09.lesson11.bonus03

она работает но тестирование не проходит,
может быть дело не в идеальном сортировщике карт по значениям, изъян найти не могу все сортирует
как можно еще отсортировать карты,

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String> list = new ArrayList<String>();
        while (true)
        {
            String s = reader.readLine();
            if (s.isEmpty()) break;
            list.add(s);
        }

        String[] array = list.toArray(new String[list.size()]);

        sort(array);
      //  System.out.println("Length" + array.length);

        for(String ar : array)
        {
            System.out.println(ar);

        }
    }

    public static void sort(String[] array)
    {
        //Напишите тут ваш код


        Map<Integer, Integer> mapi = new HashMap<Integer, Integer>();
        Map<Integer, String> mapstr = new HashMap<Integer, String>();
        for(int i = 0; i < array.length; i++)
            if (isNumber(array[i]))
            {

                mapi.put(i, Integer.parseInt(array[i]));
            }
            else
            {
                mapstr.put(i, array[i]);
            }


       
        Iterator<Map.Entry<Integer, Integer>> iterator = mapi.entrySet().iterator();
        while(iterator.hasNext())
        {
          
            Map.Entry<Integer, Integer> pair = iterator.next();
            Iterator<Map.Entry<Integer, Integer>> iterator1 = mapi.entrySet().iterator();
            while(iterator1.hasNext())
            {
                Map.Entry<Integer, Integer> pair1 = iterator1.next();

                if(pair1.getValue() < pair.getValue())
                {
                    int vr = pair1.getValue();
                    mapi.put(pair1.getKey(), pair.getValue());
                    mapi.put(pair.getKey(), vr);
                }
            }
        }



      
        Iterator<Map.Entry<Integer, String>> iterator2 = mapstr.entrySet().iterator();
        while(iterator2.hasNext())
        {
            Map.Entry<Integer, String> pair2 = iterator2.next();
            Iterator<Map.Entry<Integer, String>> iterator3 = mapstr.entrySet().iterator();
            
    //        Iterator<Map.Entry<Integer, String>> iterator3 = iterator2;
            while(iterator3.hasNext())
            {
                Map.Entry<Integer, String> pair3 = iterator3.next();
              

                if(isGreaterThen(pair3.getValue(), pair2.getValue()))
                {
                    String vr = pair3.getValue();
                    mapstr.put(pair3.getKey(), pair2.getValue());
                    mapstr.put(pair2.getKey(), vr);
                }
            }
        }



        Iterator<Map.Entry<Integer, Integer>> iterator5 = mapi.entrySet().iterator();
        while(iterator5.hasNext())
        {
            Map.Entry<Integer, Integer> pair = iterator5.next();
            array[pair.getKey()] = String.valueOf(pair.getValue());
 //          System.out.println(pair.getKey() + "   " + pair.getValue());
        }


        Iterator<Map.Entry<Integer, String>> iterator6 = mapstr.entrySet().iterator();
        while(iterator6.hasNext())
        {
            Map.Entry<Integer, String> pair = iterator6.next();
            array[pair.getKey()] = pair.getValue();
   //         System.out.println(pair.getKey() + "   " + pair.getValue());

        }
    }

    //Метод для сравнения строк: 'а' больше чем 'b'
    public static boolean isGreaterThen(String a, String b)
    {
        return a.compareTo(b) > 0;
    }


    //строка - это на самом деле число?
    public static boolean isNumber(String s)
    {
        if (s.length() == 0) return false;

        for (char c : s.toCharArray())
        {
            if (!Character.isDigit© && c != '-') return false;
        }
        return true;
    }
}
  • ,

level08.lesson11.bonus03

Сортировка работает, но тестирование не проходит

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] array = new String[10];
        for (int i = 0; i < array.length; i++)
        {
            array[i] = reader.readLine();
        }

        sort(array);

        for (String x : array)
        {
            System.out.println(x);
        }
    }

    public static void sort(String[] array)
    {
        //Напишите тут ваш код
        for(int i = 0; i < array.length; i++)
        {

            for(int j = i + 1; j < array.length; j++)
            {
                int ch1 = (int) (array[i].charAt(0));
                int ch2 = (int) (array[j].charAt(0));

                if(ch2 >= 0  && ch2 < 10)
                {
                    String e = array[i];
                    array[i] = array[j];
                    array[j] = e;
                }

                for(int q = 0; q < array[i].length() && q < array[j].length(); q++)
                {
                    if(ch1 == ch2)
                    {
                        ch1 = (int) (array[i].charAt(q));
                        ch2 = (int) (array[j].charAt(q));
                    }
                        else break;
                }

                if(ch1 == ch2 && array[i].length() > array[j].length())
                {
                    String e = array[i];
                    array[i] = array[j];
                    array[j] = e;
                }

                else if(ch1 == ch2 && array[i].length() < array[j].length())
                    break;

                if(array[i].compareTo(array[j]) > 0 && array[i].compareTo(array[j]) < 32)
                {
                    if((ch1 > 96 && ch1 < 123 && ch2 > 64 && ch2 < 91) || (ch1 > 1071 && ch1 < 1104 && ch2 > 1039 && ch2 < 1072))
                    {}
                    else
                    {
                    String e = array[i];
                    array[i] = array[j];
                    array[j] = e;
                    }
                }

                else if(array[i].compareTo(array[j]) > -32 && array[i].compareTo(array[j]) < 0 && ((ch1 > 64 && ch1 < 91 && ch2 > 96 && ch2 < 123) || (ch1 > 1039 && ch1 < 1072 && ch2 > 1071 && ch2 < 1104)))
                {
                        String e = array[i];
                        array[i] = array[j];
                        array[j] = e;
                }

                else if(array[i].compareTo(array[j]) > 32 && ((ch1 > 96 & ch1 < 123 && ch2 > 64 && ch2 < 91) ||  (ch1 > 1071 && ch1 < 1104 && ch2 > 1039 && ch2 < 1072)))
                {
                        String e = array[i];
                        array[i] = array[j];
                        array[j] = e;
                }
                else if(array[i].compareTo(array[j]) == 32 || array[i].compareTo(array[j]) == -32 )
                {

                    for(int q = 1; q < array[i].length() && q < array[j].length() && (ch1 - ch2 == 32 || ch1 - ch2 == -32); q++ )
                    {
                        ch1 = (int) (array[i].charAt(q));
                        ch2 = (int) (array[j].charAt(q));

                    }

                    if(ch1 - ch2 > -32 && ch1 - ch2 < -6 || ch1 - ch2 > 32 || array[i].length() > array[j].length())
                    {
                        String e = array[i];
                        array[i] = array[j];
                        array[j] = e;
                    }
                    }
                }
            }
        }




    //Метод для сравнения строк: 'dа' больше чем 'b'
    public static boolean isGreaterThen(String a, String b)
    {
        return a.compareTo(b) > 0;
    }
}