Wrong merge sort

오늘 기술면접 때 쓴 Wrong merge sort.
주어진 과제는 def mergeSort(alist, blist): 를 완성하는 것. 내가 구현한건 merge sort가 아니였다!
nested for 문으로 시작했다가 아닌거 같아서 이런 식으로 작성하다 Timeout...
갑자기 Python 문법을 까먹었다 라 쓰고 공부하지 않는다로 읽는다
For statement에 ()를 써버려서 급하게 자바로 아래와 같은 로직의 코드를 짰다

	def merge(array1, array2):
	a_index = 0
	b_index = 0
	result = []
	# wrong while condition
	while a_index < len(array1) and b_index < len(array2):
	if array1[a_index] > array2[b_index]:
	result.append(array2[b_index])
	b_index+=1
	else:
	result.append(array1[a_index])
	a_index+=1
	return result
	a = [1, 2, 5]
	b = [3, 4, 6]
	print(merge(a, b))
	# [1, 2, 3, 4, 5]

view raw fail_merge.py hosted with ❤ by GitHub

다시 merge sort 만들면서 깨달은 것

1. for statement에는 ()가 필요치 않다
2. list add 기능은 append() 를 사용
3. ++가 없다. +=1 을 사용
4. random.shuffle은 return하지 않고 parameter를 섞음
5. sorted는 new list를 return
6. list copy는 alist[:]로 copy module 사용안하고 심플하게 가능

---

Updated

테스트 코드 포함! merge sort 코드는 여기를 참고

	def mergeSort(alist):
	print("Splitting ", alist)
	if len(alist)>1:
	mid = len(alist)//2
	lefthalf = alist[:mid]
	righthalf = alist[mid:]
	mergeSort(lefthalf)
	mergeSort(righthalf)
	i=0
	j=0
	k=0
	while i<len(lefthalf) and j<len(righthalf):
	if lefthalf[i] < righthalf[j]:
	alist[k] = lefthalf[i]
	i+=1
	else:
	alist[k] = righthalf[j]
	j+=1
	k+=1
	while i<len(lefthalf):
	alist[k] = lefthalf[i]
	i+=1
	k+=1
	while j<len(righthalf):
	alist[k] = righthalf[j]
	j+=1
	k+=1
	print("Merging ", alist)
	import random
	def mergeSortTest(number):
	alist = list(range(number))
	random.shuffle(alist)
	print("alist ", alist)
	blist = alist[:]
	mergeSort(alist)
	blist = sorted(blist)
	print("sorted alist ", alist)
	print("alist using python sorted", blist)
	assert alist == blist
	mergeSortTest(10)
	def many_times_test():
	testSet = list(range(random.randrange(100)))
	for n in testSet:
	mergeSortTest(n)
	many_times_test()

view raw mergeSort.py hosted with ❤ by GitHub

---

Outdated

아래의 코드에서 사용했던 예제에서 동작하지만, 실제로는 범위 검사를 먼저 안하면 비교에서 out of index error가 발생한다.
반복문을 줄이려면 이렇게하면 되겠지. 하지만 심플하게 나누는게 초기 접근에는 이와 같은 인덱스 문제를 줄일거 같다. 아무생각 없이 같은 로직이라고 축약했더니 이런 문제가.
더 큰 문제는 이게 merge sort가 아니라는거!

	def sort(a, b):
	a_index=0
	b_index=0
	result = []
	while a_index < len(a) or b_index < len(b):
	if b_index >= len(b):
	result.append(a[a_index])
	a_index+=1
	elif a_index >= len(a):
	result.append(b[b_index])
	b_index+=1
	elif a[a_index] < b[b_index]:
	result.append(a[a_index])
	a_index+=1
	else:
	result.append(b[b_index])
	b_index+=1
	return result

view raw sort.py hosted with ❤ by GitHub

---

Outdated

리스트 한쪽이 먼저 끝났을 때의 처리 - out of index 문제 내포

	def merge(array1, array2):
	a_index = 0
	b_index = 0
	result = []
	while a_index < len(array1) or b_index < len(array2):
	if a_index >= len(array1) or array1[a_index] > array2[b_index]:
	result.append(array2[b_index])
	b_index+=1
	elif b_index >= len(array2) or array1[a_index] <= array2[b_index]:
	result.append(array1[a_index])
	a_index+=1
	return result
	a = [1, 2, 5]
	b = [3, 4, 6]
	print(merge(a, b))

view raw merge.py hosted with ❤ by GitHub

나름 한다고 생각했었는데.. 기초가 너무 부족하다. 평소에도 계속 코딩을 해야된다는 생각을 하게되었다.