-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge_sort.py
114 lines (95 loc) · 3.96 KB
/
merge_sort.py
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
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 10 02:00:03 2023
@author: kamma
"""
import csv
import numpy as np
import sys
import math
import os
# Lendo o arquivo original
with open('data''.csv', 'r') as read_obj:
csv_reader = csv.reader(read_obj)
list_of_csv = list(csv_reader)
print(list_of_csv)
bit_size = 1000 #byte tamanho nos queremos em cada "buffer"
# Aqui aproximando que cada objecto tem mais ou menos o mesmo tamanho
N = math.ceil(sys.getsizeof(list_of_csv)/bit_size)
list_size = np.shape(list_of_csv)[0]/N #Numeros de objetos em cada "buffer"
#Criando e salvando arquvos, onde cada um contêm um parte das dados.
start = 0
filename = 0
for i in np.arange(1,N+1):
data_buf = list_of_csv[start: int(i*list_size)]
start = int(i*list_size)
np.savetxt("buffer" + str(filename) + ".csv",data_buf, delimiter =",", fmt ='% s')
filename += 1
def mergeSort(myList):
if len(myList) > 1:
#Criando seperacão de dados
left = myList[:len(myList) // 2]
right = myList[len(myList) // 2:]
#recucão
mergeSort(left)
mergeSort(right)
merge(myList, left,right)
#combinar
def merge(myList, left,right):
i = 0 #array esquerta
j = 0 #array direta
k = 0 #array novo
while i < len(left) and j < len(right): #tem mais dados em ambos left e right
if int(left[i][0]) < int(right[j][0]):
myList[k] = left[i]
i+=1
else:
myList[k] = right[j]
j+=1
k+=1
#Só tem mais dodos em left
while i < len(left):
myList[k] = left[i]
i+=1
k+=1
#Só tem mais dados em right
while j < len(right):
myList[k] = right[j]
j+=1
k+=1
#Agora nos vamos fazer a ordanacao para cada buffer
for i in np.arange(0,N):
with open('buffer' + str(i) + '.csv', 'r') as read_obj:
csv_reader = csv.reader(read_obj)
list_of_csv = list(csv_reader)
mergeSort(list_of_csv)
#salvamos os aquivos ordenado como "sorteret"
np.savetxt("sorteret" + str(i) + ".csv",list_of_csv, delimiter =",", fmt ='% s')
read_obj.close()
os.remove('buffer' + str(i) + '.csv') #aqui nos deletamos os buffers que não estava ordenados.
#Aqui nos combinamos os arquivos
merge_nr = 0
while merge_nr <=np.ceil(np.log(9)): #o numero de vezes nos precisamos combinar todos os arquivos dois e dois
for i in np.arange(0,np.ceil(N/2)): #Metade do numero de arquivos
#Ler arquivo numero 2*i e 2*i+1
with open('sorteret' + str(int(i*2)) + '.csv', 'r') as read_obj_1:
csv_reader_1 = csv.reader(read_obj_1)
list_of_csv_1 = list(csv_reader_1)
if i*2+1 < N:
with open('sorteret' + str(int(i*2+1)) + '.csv', 'r') as read_obj_2:
csv_reader_2 = csv.reader(read_obj_2)
list_of_csv_2 = list(csv_reader_2)
#Criar uma nova lista onde a combinacão dos dois listas vai ser salvado
myList = [None]*(len(list_of_csv_1) + len(list_of_csv_2))
merge(myList, list_of_csv_1,list_of_csv_2) #fazer o merge
os.remove('sorteret' + str(int(i*2+1)) + '.csv') #deletar os dois arquivos já usados
os.remove('sorteret' + str(int(i*2)) + '.csv')
#salvar o novo arquivo com o numero i
np.savetxt("sorteret" + str(int(i)) + ".csv",myList, delimiter =",", fmt ='% s')
else:
#Para o caso onde nós temos um numero impar de dados,
# aí o ultimo vai ser salvado sem fazendo o "merge".
np.savetxt("sorteret" + str(int(i)) + ".csv",list_of_csv_1, delimiter =",", fmt ='% s')
os.remove('sorteret' + str(int(i*2)) + '.csv')
merge_nr += 1
N = np.ceil(N/2)