Сортировка подсчетом визуализатор на языке программирования Java

Таблица 3.4 – Содержимое класса AutoThread

 

Имя	Вид элемента	Тип	Спецификатор	Описание
1	2	3	4	5
Run	Метод	void	public	Запуск автоматического  режима выполнения

 

Весь исходный код программы  представлен в Приложении А.

3.2 Реализация алгоритма на языке Java

 

/**     

* @param a входной массив      

* @param K – максимальное значение для элементов A     

* @return отсортированный массив,     

*/    

 

private static Integer[] solve(int K, int[] a) {        

// Переменные циклов        

int s, i, j, m;        

// Количество предметов        

int N = M.length;        

// Вспомогательный массив  c[]        

int[] c = new int[K];        

// Выходной массив b[] 

int[] b = new int[N]; 

// Заполнение нулями массива  c[]  

for(int s = 0; s < K; s++)       

c[s] = 0;       

// Заполнение массива

c[] for (j = 0; j < N; j++) 

c[a[j] - 1] = c[a[j] – 1] + 1;

// Подсчет частичных сумм  c[]

for(i = 1; i < K; i++) 

c[i] = c[i] + c[i-1];

// Формирование выходного  массива b[]

for(m = N - 1; m >= 0; m--)

{ 

b[c[a[m]-1] = a[m];

    c[a[m] – 1] = c[a[m] – 1] – 1;

}  

 

В этой программе операции ввода/вывода не приведены, так как  их будет выполнять визуализатор.

 

3.3 Вычислительный эксперимент

 

1. Состояние 0. «Готов к работе», рисунок 3.1:

 

 

Рисунок 3.1 – Состояние 0

 

 

2. Состояние 1. «Заполнить нулями массив C», рисунок 3.2:

 

 

Рисунок 3.2 – Состояние 1

 

3. Состояние 2. «В массиве C увеличить на единицу A[j]-й элемент», рисунок 3.3:

 

 

Рисунок 3.3 – Состояние 2

 

4. Состояние 3. «В m-й элемент массива С записывается сумма m-го и m+1- го элементов», рисунок 3.4:

 

Рисунок 3.4 – Состояние 3

 

5. Состояние 4. «Найти значение в A[m]-го элемента массива C. Занести  А[m] на позицию с этим значением в выходной массив B», рисунок 3.5:

 

      

 

Рисунок 3.5 – Состояние 4

 

 

6. Состояние 5. «Массив отсортирован. Работа алгоритма завершена», рисунок 3.6:

 

       

Рисунок 3.6 – Состояние 6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

Для начала были приведены основные особенности языка программирования Java, преимущества и недостатки использования Java-апплетов, сравнение сред разработки Java и .NET. Далее производился алгоритмический анализ сортировки методом подсчета, где устанавливались постановка задачи, исходные данные к проекту, а также пошаговое описание алгоритма; после чего представляется программная реализация поставленной задачи, где можно увидеть структуру программного комплекса и вычислительный эксперимент.

Достоинством разработанной  программы является её понятный интерфейс, простота в использовании и возможность  наглядно, по шагам, отразить принцип  работы алгоритма сортировки методом подсчета.

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

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. Java-апплет/ Материал из Википедии ˗ свободной энциклопедии [Электронный ресурс]. ˗ Режим доступа: http://ru.wikipedia.org/wiki/Java-апплет ˗ Дата доступа: 25.11.2012.
2. Седжвик Р. Фундаментальные алгоритмы на C. Анализ структуры данных, сортировка, поиск. ˗ СПб.: ДиаСофтЮП, 2003. – 672с.

3. Кормен Т.,  Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. 4-е изд.  ˗ МЦНМО, 2001. ˗ 1296с.

4. Шилдт Г. Полный справочник по Java. 7-е изд. ˗ СПб.: Питер, 2007. – 1034с. 
5. Эккель Б.Философия Java. Библиотека программиста. 4-е изд. ˗ СПб.: Питер, 2009. – 640с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ А

(обязательное)

Текст программы на языке  Java

Класс CountSortApplet

import java.awt.*;

import java.awt.event.*;

import java.applet.*;

import java.util.*;

import java.text.MessageFormat;

 

//Класс апплета

public class CountSortApplet extends Applet{

CSControls controls;

CSCanvas canvas;

 

public void init(){

setLayout(new BorderLayout());

canvas = new CSCanvas();

add("Center", canvas);

add("South", controls = new CSControls(canvas));

canvas.init();

this.setSize(600,300);

}

 

public void destroy() {

remove(controls);

remove(canvas);

}

 

public void start() {

controls.setEnabled(true);

controls.start();

}

 

public void stop() {

controls.setEnabled(false);

controls.stop();

}

 

public void processEvent(AWTEvent e) {

if (e.getID() == Event.WINDOW_DESTROY) {

System.exit(0);

}

 

}

 

public static void main(String args[]) {

 

}

 

public String getAppletInfo() {

return "Count Sort visualisation Applet.";

}

}

 

Класс CSCanvas

 

import java.awt.*;

import java.awt.event.*;

import java.applet.*;

import java.util.*;

import java.text.MessageFormat;

 

//Класс, реализующий отрисовку

 

class CSCanvas extends Canvas {

int N = 20;

int K = 10;

int i0, i, j, m;

int a[], b[], c[];

int vis_stage;

int astep, bstep, cstep;

int state = 0;

String comment = "";

String comment2 = "";

String comment3 = "";

 

public void init(){

a = new int [N];

b = new int [N];

c = new int [K];

for(int step = 0; step < N; step++)

a[step] = (int)((K-1) * Math.random())+1;

for(int step = 0; step < N; step++)

b[step] = -1;

for(int step = 0; step < K; step++)

c[step] = 0;

vis_stage = 0;

astep = -1;

bstep = -1;

cstep = -1;

comment = "Готов к работе.";

comment2 = "";

comment3 = "";

}

 

public void restart(){

state = 0;

this.init();

this.repaint();

}

 

public void randomStart(){

a = new int[N];

for(int step = 0; step < N; step++)

a[step] = (int)((K-1) * Math.random())+1;

this.restart();

}

 

public void paint(Graphics g) {

int xi;

int boxh, boxw, x0, y0;

String str = "";

boxw = 20; boxh = 20;

Color activeColor = new Color(255, 140, 140);

Color activeColor2 = new Color(120, 255, 120);

Color mainColor = new Color(0, 0, 0);

g.setColor(mainColor);

Font font = new Font("Times New Roman", Font.PLAIN, 14);

g.setFont(font);

 

// Массив A:

 

x0 = 80; y0 = 40;

for(xi = 0; xi < N; xi++)

{

if (xi == astep)

{

g.setColor(activeColor);

g.fillRect(x0, y0, boxw, boxh);

g.setColor(mainColor);

}

g.drawRect(x0, y0, boxw, boxh);

str = Integer.toString(a[xi]);

g.drawString(str, x0 + boxw/2 - str.length()*font.getSize()/4,y0 + boxh/2 + font.getSize()/2 - 1);

x0 += boxw;

}

g.drawString("A:", 10, y0 + boxh/2 + font.getSize()/2 - 1);

 

// Массив C:

 

x0 = 80; y0 = 100;

for(xi = 0; xi < K; xi++)

{

if (xi == cstep)

{

g.setColor(activeColor2);

g.fillRect(x0, y0, boxw, boxh);

g.setColor(mainColor);

}

if (vis_stage == 1)

if (xi == (cstep-1))

{

g.setColor(activeColor);

g.fillRect(x0, y0, boxw, boxh);

g.setColor(mainColor);

}

g.drawRect(x0, y0, boxw, boxh);

if (state > 0)

{

str = Integer.toString(c[xi]);

g.drawString(str, x0 + boxw/2 - str.length()*font.getSize()/4,y0 + boxh/2 + font.getSize()/2 - 1);

}

x0 += boxw;

}

g.drawString("C:", 10, y0 + boxh/2 + font.getSize()/2 - 1);

 

// Массив B:

 

x0 = 80; y0 = 160;

for(xi = 0; xi < N; xi++)

{

if (xi == bstep)

{

g.setColor(activeColor);

g.fillRect(x0, y0, boxw, boxh);

g.setColor(mainColor);

}

g.drawRect(x0, y0, boxw, boxh);

if (b[xi] > 0)

{

str = Integer.toString(b[xi]);

g.drawString(str, x0 + boxw/2 - str.length()*font.getSize()/4,y0 + boxh/2 + font.getSize()/2 - 1);

}

x0 += boxw;

}

g.drawString("B:", 10, y0 + boxh/2 + font.getSize()/2 - 1);

Font fontLittle = new Font("Times New Roman", Font.PLAIN, 9);

g.setFont(fontLittle);

String sNum = "";

x0 = 80; y0 = 40;

for(xi = 0; xi < N; xi++){

sNum = str.valueOf(xi + 1);

g.drawString(sNum, x0 - 1 + boxw*xi + boxw/2, y0-3);

}

x0 = 80; y0 = 100;

for(xi = 0; xi < K; xi++){

sNum = str.valueOf(xi + 1);

g.drawString(sNum, x0 - 2 + boxw*xi + boxw/2, y0-3);

}

x0 = 80; y0 = 160;

for(xi = 0; xi < N; xi++){

sNum = str.valueOf(xi + 1);

g.drawString(sNum, x0 - 3 + boxw*xi + boxw/2, y0-3);

}

g.setFont(font);

g.drawString(comment, 60, 220);

g.drawString(comment2, 60, 260);

g.drawString(comment3, 60, 280);

}

 

public void MakeStep() {

 

// Автомат

 

switch (state)

{

case 0:

 

state = 1; i0 = 0;

for (int step = 0; step < N; step++)

b[step] = -1;

for (int step = 0; step < K; step++)

c[step] = 0;

break;

case 1:

for (i0 = 0; i0 < K; i0++)

c[i0] = 0;

comment = "Заполнить нулями массив C.";

state = 2; j = 0;

break;

case 2:

if (j < N)

{

c[a[j]-1] = c[a[j]-1] + 1;

j++;

}

else

{

state = 3;

i = 1;

}

break;

case 3:

if (i < K) {c[i] = c[i] + c[i-1]; i++; }

else {state = 4; m = N - 1; }

break;

case 4:

if (m >= 0) {b[c[a[m]-1]-1] = a[m]; c[a[m]-1] = c[a[m]-1] -

1; m--; }

else {state = 5;}

break;

case 5:

break;

}

 

//  Визуализация в состояниях автомата

 

switch (state)

{

case 0:

break;

case 1:

comment = "Заполнить нулями массив C.";

break;

case 2:

if (j < N)

{

astep = j;

cstep = a[j]-1;

bstep = -1;

String ss1 = Integer.toString(j+1);

String ss2 = Integer.toString(cstep+1);

comment = "В массиве C увеличить на единицу A[" + ss1+ "]-й элемент. (" + ss2 + "-й элемент).";

}

 

break;

case 3:

vis_stage = 1;

if (i < K)

{

astep = -1;

cstep = i;

bstep = -1;

if (i == 1)

comment = "Во " + Integer.toString(cstep+1) + "-й элемент массива С записать сумму " + Integer.toString(cstep) + "-го и " + Integer.toString(cstep+1) + "-го элементов.";

else

comment = "В " + Integer.toString(cstep+1) + "-й элемент массива С записать сумму " + Integer.toString(cstep) + "-го и " +  Integer.toString(cstep+1) + "-го элементов.";

}

else

comment = "Массив С сформирован.";

break;

case 4:

vis_stage = 2;

if (m >= 0)

{

astep = m;

cstep = a[m]-1;

bstep = c[a[m]-1]-1;

String ss1 = "Значение "+ Integer.toString(astep+1) + "-го элемента A равно " + Integer.toString(a[m]) + ". ";

String ss2 = "Найти значение " + Integer.toString(a[m]) + "-го элемента C.";

comment = ss1 + ss2;

comment2 = "Искомое значение равно " + Integer.toString(bstep+1) +".";

comment3 = "Записать " + Integer.toString(astep+1) +"-й элемент А на " + Integer.toString(bstep+1) + " позицию в выходной массив B.";

}

else

{

comment = "Массив отсортирован. Работа алгоритма завершена.";

comment2 = "";

comment3 = "";

}

break;

case 5:

break;

}

repaint();

} // Makestep

}

 

Класс CSControls

import java.awt.*;

import java.awt.event.*;

import java.applet.*;

import java.util.*;

import java.text.MessageFormat;

 

//Класс элементов управления

 

class CSControls extends Panel implements ActionListener {

CSCanvas canvas;

private boolean auto = false;

private Thread autoThread = new AutoThread();

private static final int INITIAL_DELAY = 4;

private static final int[] DELAYS = new int[]{100, 200, 250, 400, 500, 1000, 2000, 2500};

//private int delay = INITIAL_DELAY;

public int delay = INITIAL_DELAY;

Button buttonNext, buttonRestart, buttonAuto, buttonStop, buttonDelayUp, buttonDelayDown;

Button buttonRandomize;

Label labelDelay;

 

public CSControls(CSCanvas canvas) {

this.canvas = canvas;

buttonNext = new Button(" >> ");

buttonRestart = new Button("Рестарт");

buttonAuto = new Button("Авто");

buttonStop = new Button("Стоп");

buttonDelayDown = new Button("<");

buttonDelayUp = new Button(">");

labelDelay = new Label("Задержка: 500 ");

buttonRandomize = new Button("Cлучайно");

buttonNext.addActionListener(this);

buttonRestart.addActionListener(this);

buttonStop.addActionListener(this);

buttonAuto.addActionListener(this);

buttonDelayDown.addActionListener(this);

buttonDelayUp.addActionListener(this);

buttonRandomize.addActionListener(this);

buttonNext.setSize(50,20);

buttonStop.setEnabled(false);

add(buttonNext);

add(buttonRestart);

add(buttonRandomize);

add(buttonAuto);

add(buttonStop);

add(buttonDelayDown);

add(labelDelay);

add(buttonDelayUp);

}

 

public void start(){

autoThread.start();

}

 

public void stop(){

auto = false;

autoThread.interrupt();

}

 

public void actionPerformed(ActionEvent ev) {

Object source = ev.getSource();

String stLabel;

if (source == buttonNext){

canvas.MakeStep();

}

if (source == buttonAuto){

auto = true;

 

buttonStop.setEnabled(true);

buttonAuto.setEnabled(false);

buttonNext.setEnabled(false);

}

if (source == buttonStop){

auto = false;

buttonStop.setEnabled(false);

buttonAuto.setEnabled(true);

buttonNext.setEnabled(true);

}

if (source == buttonDelayDown){

if (delay == 7)

buttonDelayUp.setEnabled(true);

if (delay > 0)

delay--;

else

buttonDelayDown.setEnabled(false);

String str = "";

stLabel = "Задержка: " + str.valueOf(DELAYS[delay]);

labelDelay.setText(stLabel);

}

if (source == buttonDelayUp){

if (delay == 0)

buttonDelayDown.setEnabled(true);

if (delay < 7)

delay++;

else

buttonDelayUp.setEnabled(false);

String str = "";

stLabel = "Задержка: " + str.valueOf(DELAYS[delay]);

labelDelay.setText(stLabel);

}

if (source == buttonRestart) {

if (canvas.state == 5){

buttonAuto.setEnabled(true);

buttonNext.setEnabled(true);

}

canvas.restart();

}

if (source == buttonRandomize) {

if (canvas.state == 5){

buttonAuto.setEnabled(true);

buttonNext.setEnabled(true);

}

canvas.randomStart();

}

}

//Нить, в случае  автоматического режима через  определенные

// интервалы инициирующая  шаг визуализатора

Класс AutoThread

public class AutoThread extends Thread {

 

public AutoThread() {

super("Auto thread");

setDaemon(true);

}

 

public void run() {

while (true) {

if (auto) {

canvas.MakeStep();

if (canvas.state == 5) {

auto = false;

buttonStop.setEnabled(false);

buttonNext.setEnabled(false);

}

}

try {

sleep(DELAYS[delay]);

} catch (InterruptedException e) {}

}

}

}

}

ПРИЛОЖЕНИЕ Б

(обязательное)

Руководство пользователя

В верхней части визуализатора  представляется следующая информация:

• значения массивов А[], B[], C[];