(Python) Merge sorting algorithm의 구현
이번에는 Python으로 Merge sorting을 구현해봤습니다. 수업 과제라서... ㅋㅋㅋ
알고리즘은 인터넷에 이미 많이 올라와있으니까 알고리즘은 아래의 사이트에서 읽어보시면 됩니다!!
(알고리즘이 최적화가 되어있지 않고 variable convention이 안 맞는게 꽤 많습니다 ㅠ, .. 걸러 읽어주세요!!!)
----
사상은 우선 최소 단위인 2개까지 쪼개가지고
아래와 같이 왼쪽/오른쪽에 Handle을 배치해서 크거나 작은 순으로 데이터를 땡기고 핸들을 좌/우에서 밀어가지고 핸들이 끝까지 가면 반대쪽 데이터를 끝까지 append하는 거에요.
알고리즘이 너무 간단해서 설명이 엄청 짧네요!
1. 입력을 받은 후 처리되는 배열을 정하고, 핸들 배치한 뒤에 비교하는 알고리즘을 호출하는 부분과,
2. 위에서 입력받은 데이터를 비교해서 데이터를 처리하고 정리된 데이터를 리턴하는 부분을 만들어보려고 합니다.
-----
1. 여기서부터는 입력을 받은 후 처리되는 배열을 정하고 핸들 배치, Merge sort를 호출하는 부분입니다.
1) 먼저 List의 길이를 확인합니다. (MainCount_input)
위의 알고리즘을 보면 Merge sorting 하는 Array의 size가 2배씩 커지는데, (MainMultiIndex)에서 1부터 2씩 곱해가다보면 소팅하려고 투입하는 배열 사이즈가 원본 List보다 커지겠죠! 그 때 종료 시켜버리면 되겠죠!
2),3) MainIndex는 Sorting 시작할 부분을 지정해주는 거에요,
그러니까 아래와 같은 순서로 처리가 될 거에요.
(종료호출이 왜 있는지는 아래에다가 달아놓으려고 합니다!)
(2개 정렬)
정렬범위 : 0~1 / 종료호출 : 2
정렬범위 : 2~3 / 종료호출 : 4
정렬범위 : 4~5 / 종료호출 : 6
.. 2개 정렬이 끝나면
(4개 정렬)
정렬범위 : 0~3 / 종료호출 : 4
정렬범위 : 4~7 / 종료호출 : 8
정렬범위 : 8~11 / 종료호출 : 12
.. 4개 정렬이 끝나면
(8개 정렬)
정렬범위 : 0~7 / 종료호출 : 8
정렬범위 : 8~15 / 종료호출 : 16
정렬범위 : 16~23 / 종료호출 : 24
...
규칙을 적어보면
2개 정렬일 때는 [n번째정렬] = 시작점 : 2*(n-1) 종료호출 : 2*n
4개 정렬일 때는 [n번째정렬] = 시작점 : 2*2*(n-1) 종료호출 : 2*2*n
8개 정렬일 때는 [n번째정렬] = 시작점 : 2*2*2*(n-1) 종료호출 : 2*2*2*n
그러니까 x개 정렬시 n번째에는 시작점 : x*(n-1), 종료호출점 : x*n 이 되겠네요!
왜 종료호출점이냐면, 배열을 반으로 쪼갠다고 말씀드렸었는데요~
핸들이 오른쪽으로 검색한다고 쪼개진 왼쪽 핸들은 중간지점이 종료지점이 되지만, 오른쪽 핸들은 종료지점이 마지막 부분이기 때문이에요!
저는 배열을 0부터 시작했으니까 x*n이 되겠지요!
위에서 x와 n을 저는 x : MainMultiIndex, n : MainIndex로 표현하였읍니다.
그래서 n은 2씩 더하게 되고 전체 Array가 다 돌면 x는 1을 더해주면 되겠죠~~
뭔가 설명이 너무 복잡하고 어렵네요~ ㅋㅋ 알고리즘은 참 쉬운데 말이에요~
2.여기서부터는 비교하는 알고리즘 입니다.
위에서 배열을 입력받고 시작점을 정하고 Sorting size도 다 정했으니까 이 부분은 굉장히 간단해집니다. 위와 같이 핸들에 있는 데이터를 비교해서 순서대로 정리한 뒤에 리턴해주면 되니까요!
앞선 순서도를 보면 배열의 좌/우측 중 하나가 끝나면 나머지 부분을 모두 append시키고 리턴해줘야 합니다.
그래서 EndFlag라는걸 하나 위치시켜서 왼쪽이나 오른쪽이 끝나면 반대쪽 데이터를 모두 배열에 실어서 리턴해주면 됩니다.
1) 오름차순인지 내림차순인지에 따라서 판단조건을 설정하고
2)
비교하여 조건이 맞는 쪽의 데이터를 임시 배열에 밀어 넣습니다. (오름차순이냐 내림차순이냐에 따라서)
이를 반복하는데 , 한 쪽의 핸들이 마지막에 도착하면 배열 반대쪽 데이터를 임시배열에 끝까지 밀어넣습니다.
반대쪽의 데이터는 그대로 밀어넣어도 되는 이유가, 쪼개진 단위의 데이터는 순서대로 배열되어 있기 때문에 그렇습니다.
완성될 알고리즘으로 머지쏘트를 돌려보면 아래와 같이 처리되는데 진행되는 순서를 보시면 이해가 될 것 같습니다. (내림차순의 경우에요!)
3) 핸들이 마지막에 도착하면 원본 리스트에 옮겨 담아줍니다
-----
위의 과정을 반복한다면 한 가지 문제가 발생합니다.
바로 배열이 2^n개가 아니라면요? 라는 문제에요.
가장 큰 숫자를 한다면 나중에 해당 숫자를 제거해야 할테고
가장 작은 숫자를 해도 똑같겠죠?
그러니까 제가 사용할 방법은 입력된 배열을 반으로 쪼갠 뒤 오른쪽 절반의 핸들의 종료지점이 입력된 배열의 사이즈를 초과한다면 오른쪽 핸들의 종료호출 지점으로 입력된 배열의 사이즈를 지정하는거에요. 만약에 그 종료호출 지점이 오른쪽 시작지점보다 크다면 그대로 종료 시켜버리면 됩니다.
말은 길지만 코딩은 엄청 짧게 되었네요! ㅎ
※ Gap이라는 변수는 원본 배열에 복사하기 위해서 설정하였습니다.
(위와 같이 원래 Sort했어야 할 갯수와 최종 복사되는 갯수의 차이가 발생시에 그만큼 빼서 원래 배열에 복사하는데 오류가 발생하는 것을 방지합니다.)
----
처리가 잘 되었네요! ㅎㅎ
설명이 너무 어려운 것 같아서 죄송합니다만 ㅠ 실제로 해보시면 굉장히 쉽다는 것을 아시게 될 것 같습니다. 그럼 다음에도 뭔가 만들면 또 써놓을게요. 도움이 되신다면 좋겠습니다~~
아래에서 List_Input의 데이터와 Direction 변수만 "Up", "Down"으로 지정해주시면 확인이 가능하세용~~
def Shims_Merge (StartPoint, SortSize, DataSeries, Direction) :
'''
Handle Initialization
Using Mergesort Algorithm : https://www.geeksforgeeks.org/merge-sort/
When Each handle meets the endpoint of given side, then exit function
MH : Merge Handle (for left side / right side)
Temp : Temporary data address (for left side / right side)
Temp_List : Empty list to sort the data in 'DataSeries'
'''
n = len(DataSeries) -1
MH_L = StartPoint
MH_L_End = StartPoint + SortSize - 1
MH_R = StartPoint + SortSize
MH_R_End = StartPoint + 2 * SortSize - 1
CIndex = 0
Gap = 0
# If right handle is positioned at the value than right handle , then exit function.
# Left Handle will be always smaller then length of 'DataSeries' in input level, So it doesn't need to be cared in this function.
if MH_R_End > n :
Gap = MH_R_End - n
MH_R_End = n
if MH_R_End < MH_R :
return
EndPoint = MH_R_End
CopyCount = range(0,2 * SortSize - Gap,1)
Count = 0
Temp_L = DataSeries[MH_L]
Temp_R = DataSeries[MH_R]
Temp_List = []
EndFlag = False
#print ("MH_L : %d, MH_R : %d, MH_LE : %d, MH_RE : %d"%(MH_L,MH_R,MH_L_End,MH_R_End))
#When adds data to Empty list, user should use append inner function.-Important
while (1) :
if Direction == "Up" :
Criteria = Temp_L < Temp_R
else :
Criteria = Temp_L > Temp_R
if Criteria :
Temp_List.append(Temp_L)
MH_L = MH_L + 1
#Sweep datas into temporary list
if MH_L > MH_L_End :
EndFlag = True
while MH_R <= MH_R_End :
Temp_R = DataSeries[MH_R]
Temp_List.append(Temp_R)
MH_R = MH_R + 1
Temp_L = DataSeries[MH_L]
else :
Temp_List.append(Temp_R)
MH_R = MH_R + 1
#Sweep datas into temporary list
if MH_R > MH_R_End :
EndFlag = True
MH_R = MH_R_End
while MH_L <= MH_L_End :
Temp_L = DataSeries[MH_L]
Temp_List.append(Temp_L)
MH_L = MH_L + 1
Temp_R = DataSeries[MH_R]
if EndFlag == True :
for CIndex in CopyCount :
DataSeries[StartPoint + CIndex] = Temp_List[CIndex]
del(Temp_List)
return
def Shims_Input() :
num = []
i = 1
while i <= 20 :
try:
user_input = int(input(str(i)+"번째 숫자를 입력하세요 : "))
num.append(user_input)
i = i + 1
except ValueError:
print("숫자만 입력하세요.")
return num
#Main function is written from here.
'''
#Using this part when using manual input
List_input = Shims_Input()
MainCount_input = len(List_input)
MainMultiIndex = 1
'''
List_input = [1,5,6,123,2137,8,1,2,45,6,72,6,4,2,45,7,87,32,6,3,12]
Direction = "Down" #Set direction of sorting, "Up" for Upward or "Down" for Downward
#Processing merge sort algorithm from smaller group to larger group
print (List_input)
MainCount_input = len(List_input)
MainMultiIndex = 1
while MainMultiIndex < MainCount_input :
MainIndex = 0
while MainIndex*MainMultiIndex < MainCount_input :
Shims_Merge(MainIndex*MainMultiIndex, MainMultiIndex, List_input,Direction)
MainIndex = MainIndex + 2
print (List_input)
MainMultiIndex = MainMultiIndex * 2
print (List_input)
댓글
댓글 쓰기