Файл: Разработка в среде Open Source Разработка объектноориентированной программы на Java.docx

ФГБОУ ВО

ННГАСУ

Кафедра информационных систем и технологий

Расчётно-графическая работа по дисциплине

«Разработка в среде Open Source»

Разработка объектно-ориентированной программы на Java

Вариант 4

Выполнил студент 3 курса гр. ИС-29:

Гордеев Н.С.___________________

^{(подпись)}

Проверил преподаватель:

Лахов А. Я.______________________

^{(подпись)}

Нижний Новгород

2023 г.

Оглавление

Задание

1. 
   Выполнение сортировки значений массива методом слияния
   
2. 
   Выполнение поиска заданного значения int Key методом линейного поиска
   

Разработать консольное приложение на Java, генерирующее файл Data.txt со случайными целыми числами.

Разработать графическое приложение на Java, реализующее функции:

а) чтение содержания файла Data.txt и запись значений в массив

б) выполнение сортировки значений массива заданным методом

в) выполнение поиска заданного значения int Key заданным методом.

Алгоритм метода сортировки

Сортировка слиянием (merge sort) – это алгоритм сортировки, который использует принцип "разделяй и властвуй". Он состоит из двух основных шагов: разделения и слияния.

Шаг 1: Разделение Алгоритм слияния начинается с разделения исходного массива на две равные части. Затем каждая из этих частей рекурсивно разбивается на две части, и так далее, пока каждая часть не будет содержать только один элемент. Этот процесс называется "разделением" или "делением на подмассивы".

Шаг 2: Слияние После того, как массив разделен на подмассивы, начинается процесс "слияния". Два подмассива, полученных на предыдущем шаге, сравниваются между собой и объединяются в один отсортированный массив. Этот процесс продолжается, пока не будет получен отсортированный массив, содержащий все элементы исходного массива.

---

Сортировка слиянием имеет эффективность O(n log n), что является одним из лучших результатов среди алгоритмов сортировки. Это означает, что время выполнения алгоритма растет не так быстро, как у других алгоритмов сортировки при увеличении размера входных данных.

Алгоритм слияния использует принцип "разделяй и властвуй", который позволяет разбивать задачу на более мелкие подзадачи и решать их рекурсивно. Это позволяет уменьшить время выполнения алгоритма, так как каждая подзадача обрабатывается отдельно и не зависит от других.

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

Алгоритм метода поиска

Линейный поиск - это простой, но в то же время элегантный алгоритм, который позволяет найти нужное значение в массиве, перебирая его элементы последовательно. Он как бы просматривает каждый элемент массива, пока не найдет нужный, и возвращает его индекс.

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

Хотя линейный поиск может быть не самым быстрым алгоритмом поиска, его простота и надежность делают его незаменимым во многих задачах. Иногда простота - это красота.

Эффективность линейного поиска зависит от размера массива, в котором производится поиск. В худшем случае, когда искомый элемент находится в конце массива, алгоритм должен пройти через все элементы, что занимает O(n) времени, где n - это размер массива.

Таким образом, эффективность линейного поиска зависит от размера списка и требований к поиску. Если список небольшой, то линейный поиск может быть достаточно эффективным и простым в реализации. Однако, если список очень большой, то лучше использовать более эффективные алгоритмы поиска (например, бинарный поиск).

---

Кода на языке Java

RGROpenSource.java

import javax.swing.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class RGROpenSource extends JFrame{
private JPanel panel1;
private JTextField fileTextField;
private JButton openFileButton;
private JButton sortButton;
private JTextField fineTextField;
private JButton findButton;
private JTable table1;
private JTable table2;
private File selectedFile = null;
private final MergeArray mergeArray = new MergeArray(100);
public RGROpenSource() {
this.setTitle("РГР.ОпенСурс.Гордеев");
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setContentPane(this.panel1);
openFileButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
JFileChooser fileChooser = new JFileChooser();
int returnValue = fileChooser.showOpenDialog(null);
if (returnValue != JFileChooser.APPROVE_OPTION) {
return;
}
File file = fileChooser.getSelectedFile();
if (!file.getName().endsWith(".txt")){
JOptionPane.showMessageDialog(
null,
"Файл должен быть формата .txt",
"Выбор файла",
JOptionPane.ERROR_MESSAGE
);
return;
}
selectedFile = fileChooser.getSelectedFile();
fileTextField.setText(selectedFile.getName());
try (BufferedReader br = new BufferedReader(new FileReader(selectedFile.getAbsolutePath()))) {
String line;
int i = 0;
while ((line = br.readLine()) != null) {
try {
mergeArray.insert(Long.parseLong(line));
table1.setValueAt(line, i, 0);
}
catch (NumberFormatException exp) {
continue;
}
finally {
i++;
}
}
} catch (IOException exp) {
exp.printStackTrace();
}
}
});
sortButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (mergeArray.getNElems() <= 0) {
JOptionPane.showMessageDialog(
null,
"Значений нет",
"Сортировка",
JOptionPane.ERROR_MESSAGE
);
return;
}
long[] sortedValues = mergeArray.mergeSort();
for (int i = 0; i < 10; i++) {
table2.setValueAt(String.valueOf(sortedValues[i]), i, 0);
}
}
});
findButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
String value = fineTextField.getText();
try {
long longValue = Long.parseLong(value);
Integer findKey = mergeArray.find(longValue);
if (findKey != null) {
JOptionPane.showMessageDialog(
null,
"Индекс полученного числа: " + findKey,
"Поиск значения",
JOptionPane.INFORMATION_MESSAGE
);
table1.setRowSelectionInterval(findKey, findKey);
}
else {
JOptionPane.showMessageDialog(
null,
"Значение не найдено",
"Поиск значения",
JOptionPane.ERROR_MESSAGE
);
}
}
catch (NumberFormatException exp) {
JOptionPane.showMessageDialog(
null,
"Неверный формат данных",
"Поиск значения",
JOptionPane.ERROR_MESSAGE
);
}
}
});
this.pack();
this.setVisible(true);
}
public static void main(String[] args) {
new RGROpenSource();
}
private void createUIComponents() {
String[] tableColumns = {""};
String[][] rawData = new String[10][1];
for (int i = 0; i < rawData.length; i++) {
rawData[i][0] = "";
}
String[] tableColumns1 = {""};
String[][] rawData1 = new String[10][1];
for (int i = 0; i < rawData1.length; i++) {
rawData1[i][0] = "";
}
table1 = new JTable(rawData, tableColumns);
table2 = new JTable(rawData1, tableColumns1);
}
}

MergeArray.java

public class MergeArray {

private final long[] arr;
private final long[] sortedArr;
private int nElems;

public MergeArray(int maxElems) {
arr = new long[maxElems];
sortedArr = new long[maxElems];
nElems = 0;
}

---

public void insert(long value) {
arr[nElems] = value;
sortedArr[nElems] = value;
nElems++;
}
public void display() {
for (int j = 0; j < nElems; j++)
System.out.print(arr[j] + " ");
System.out.println();
}
public int getNElems() {
return this.nElems;
}
public Integer find(long searchKey) {
for (int i = 0; i < this.nElems; i++) {
if (this.arr[i] == searchKey) {
return i;
}
}
return null;
}
public long[] mergeSort() {
long[] workSpace = new long[nElems];
recMergeSort(workSpace, 0, nElems - 1);
return this.sortedArr;
}
private void recMergeSort(long[] workSpace, int lowerBound,
int upperBound) {
if (lowerBound == upperBound) {
return;
}
int mid = (lowerBound + upperBound) / 2;
recMergeSort(workSpace, lowerBound, mid);
recMergeSort(workSpace, mid + 1, upperBound);
merge(workSpace, lowerBound, mid + 1, upperBound);
}
private void merge(long[] workSpace, int lowPtr,
int highPtr, int upperBound) {
int j = 0;
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1;
while (lowPtr <= mid && highPtr <= upperBound) {
if (sortedArr[lowPtr] < sortedArr[highPtr]) {
workSpace[j++] = sortedArr[lowPtr++];
} else {
workSpace[j++] = sortedArr[highPtr++];
}
}
while (lowPtr <= mid) {
workSpace[j++] = sortedArr[lowPtr++];
}
while (highPtr <= upperBound) {
workSpace[j++] = sortedArr[highPtr++];
}
for (j = 0; j < n; j++) {
sortedArr[lowerBound + j] = workSpace[j];
}
}
public static void main(String[] args) {
MergeArray arr = new MergeArray(100);
arr.insert(64);
arr.insert(21);
arr.insert(33);
arr.insert(70);
arr.insert(12);
arr.insert(85);
arr.insert(44);
arr.display();
arr.mergeSort();
arr.display();
}
}

RandomDataGen.java

(Запись рандомных значений в Data.txt)

import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

public class RandomDataGen {

public static void generateData(int valuesCount, String fileName){
Random random = new Random();
try {
FileWriter writer = new FileWriter(fileName);
for (int i = 0; i < valuesCount; i++) {
int randomValue = random.nextInt(100);
System.out.printf("[%s/%s] val: %s %n", i + 1, valuesCount, randomValue);
writer.write(randomValue + "\n");
}
writer.close();
System.out.println("Successfully wrote values to file.");
} catch (IOException e) {
System.out.println("An error occurred.");
e.printStackTrace();
}
}
public static void generateData() {
generateData(10, "Data.txt");
}
public static void main(String[] args) {
generateData();
}
}

Сеанс работы с приложением

Основное окно

Выбор файла

Сортировка

Поиск элемента

---