Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
81 / 37 / 10
Регистрация: 21.11.2010
Сообщений: 177

k-way merge sort

08.05.2012, 13:35. Показов 1825. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть код, который сортирует файл. В процессе написания кодаБ а также повторного прочтения задания и теории по теме запуталась, какую сортьировку я реализовала - простую или к-путевую?
Предупрежу - код немного кривой, хотя и компилируется.
Буду признательна за помощь в разрешении описанного выше затруднения и рекомендации по исправлению кривости кода.
Не судите строго, но комментарии писала на английском - ибо переключения раскладки во время кодинга нервируют.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import java.io.*;
import java.util.Scanner;
 
public class ExternalSort {
 
    static long N = 4194320 * 1024 + 100; // maxsize of the file in disk
    static long M = 10 * 1024 * 1024; // max items the memory buffer can hold
    static String[] buf;
    public static void externalSort(String fileName) {
        String tfile = "temp-file-";
 
        try {
 
            FileReader fr = new FileReader(fileName);
            BufferedReader br = new BufferedReader(fr);
            int slices = (int) Math.ceil((double) N / M);
            /*
             * Returns the smallest (closest to negative infinity) double value
             * that is greater than or equal to the argument and is equal to a
             * mathematical integer.
             */
            
            int i, j;
            // Iterate through the elements in the file
            for (i = 0; i < slices; i++) {
                int l = 0;
 
                // Read M-element chunk at a time from the file
                for (j = 0; j < (M < N ? M : N); j++) {
                    String t = br.readLine();
                    if (t != null) {
                        buf[j] = t;
                        l++;
                    } else {
                        break;
                    }
                }
                // Sort M elements
                mSort(buf, 0, l);
 
                // Write the sorted numbers to temp file
                FileWriter fw = new FileWriter(tfile + i + ".txt");
                PrintWriter pw = new PrintWriter(fw);
                for (int k = 0; k < j; k++) {
                    pw.println(buf[k]);
                }
 
                pw.close();
                fw.close();
            }
 
            br.close();
            fr.close();
 
            // Now open each file and merge them, then write back to disk
            String[] topNums = new String[slices];
            BufferedReader[] brs = new BufferedReader[slices];
 
            for (i = 0; i < slices; i++) {
                brs[i] = new BufferedReader(new FileReader(tfile + i + ".txt"));
                String t = brs[i].readLine();
                if (t != null) {
                    topNums[i] = t;
                } else {
                    continue;
                }
            }
 
            FileWriter fw = new FileWriter("E:\\test\\external-sorted.txt");
            PrintWriter pw = new PrintWriter(fw);
 
            for (i = 0; i < N; i++) {
                String min = topNums[0];
                int minFile = 0;
 
                for (j = 0; j < slices; j++) {
                    if ((min.compareTo(topNums[j])) < 0) {
                        min = topNums[j];
                        minFile = j;
                    }
                }
 
                pw.println(min);
                String t = brs[minFile].readLine();
                if (t != null) {
                    topNums[minFile] = t;
                } else {
                    continue;
                }
 
            }
            for (i = 0; i < slices; i++) {
                brs[i].close();
            }
 
            pw.close();
            fw.close();
        } catch (FileNotFoundException e) {
            System.out.println("File Not Found!");
        } catch (IOException e1) {
            System.out.println("Problems with temp files!");
        }
    }
 
// method checks rightness of sorting.
    public static void checking() {
        String a1;
        String a2;
        try {
            Scanner sc = new Scanner(new File("G:/file.txt"));
            a1 = sc.nextLine();
            while (sc.hasNext()) {
                a2 = sc.nextLine();
                if ((a1.compareTo(a2)) >= 0) {
                    continue;
                } else {
                    System.out.println("File is not sorted!");
                    break;
                }
            }
            System.out.println("File is sorted right!");
            sc.close();
        } catch (FileNotFoundException e) {
            System.out.println("File not found!");
        }
    }
    
    public static String[] mSort(String[] A, int l, int r) {
        int low = l;
        int high = r;
        int middle = (high + low) / 2;
        mSort(A, low, middle);
        mSort(A, middle, high);
        int end_low = middle;
        int start_high = middle + 1;
        while ((low <= end_low) && (start_high <= high)) {
            if (A[low].compareTo(A[start_high]) > 0) {
                low++;
            } else {
                String t = A[start_high];
                for (int k = start_high - 1; k >= low; k--) {
                    A[k + 1] = A[k];
                }
                A[low] = t;
                low++;
                end_low++;
                start_high++;
            }
        }
        return A;
    }
}
Кстати, вот конкретная часть задания:
........................................ ..............
3. Написать программу для сортировки этого файла по строкам в лексикографическом порядке. Использовать внешнюю сортировку слиянием.
4. Измерить время сортировки.
5. (необязательно) Реализовать k-путевое слияние (k-way merge).
........................................ .............
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
08.05.2012, 13:35
Ответы с готовыми решениями:

Merge sort
Здравствуйте, пытаюсь написать сортировку по методу слияния (merge). не получается, подскажите пожалуйста в чем ошибка? void...

Merge sort
Было 100500 раз, знаю. Видел коды, но всеравно не понимаю. У меня есть класс Array. class Array { private: int *arr; public: ...

Merge Sort
написал реализацию Merge Sort но что то не так получилось))) помогите найти ошибку ) using namespace std; void Merge(int ,int ,int...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
08.05.2012, 13:35
Помогаю со студенческими работами здесь

Реализация merge sort на C++14
Помогите найти (или покажите сами) профессиональную реализацию merge sort с использованием 14-го стандарта. Интернет завален только сишными...

Не работает merge sort
Пытаюсь реализовать merge sort, но она не работает. Где ошибка?: Array = def merge_sort(A, p, r): if r &gt; p: ...

Слияние массивов. Merge sort
Пытаюсь сделать сортировку больших обьемов данных. В моем случае файл с double числом в каждой новой строчке. Файл примерно весит 1гб....

Сортировка слиянием (Merge sort)
Пожалуйста, помогите сортировать лист в C++ только надо именно слиянием отсортировать

Merge Sort - Ошибка в коде
Всем привет, написал алгоритм сортировки слиянием, но работает он неправильно. Помогите найти ошибку в коде. Спасибо. К примеру при...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при создании или изменении элементов справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru