인공지능과목들로 인해 python을 다뤄보며 그 한 학기동안 개인적으로 힘든 일들로 인해 겨우 프로젝트를 끝내고 수업들을 끝냈었다
그 이후 번아웃이 격렬하게 오며 python이 아닌 JAVA와 C++로 개인적 공부들을 하며 python을 외면 해 온 올 한 해..

Merge Sort를 구현해 보려 하는 순간 for문에서 당황했다.

python for 문

The _for statement in Python differs a bi_t from what you may be used to in C or Pascal. Rather than always iterating over an arithmetic progression of numbers (like in Pascal), or giving the user the ability to define both the iteration step and halting condition (as C), Python’s for statement iterates over the items of any sequence (a list or a string), in the order that they appear in the sequence.

• 코드를 짜는 사람에게 iteration step 과 haltiding 조건을 정의하는 것을 맡기던 C언어나 C++. 과 달리 Python의 for문은 어떤 sequence의 item에 대해 iterate를 하는 것이다.
• 따라서

m_list =['a','b,'c']
my_str ="hello"

for ch in m_list:
	print(ch)
    
for idx in range(len(m_list)):
	print(m_list[idx])
    
for idx,ch in enumerate(m_list):
	print(str(idx)+" : "+ch)
    
for ch in my_str:
	print(ch)

이런 for문이 가능하다는 것.

Merge sort는?

• Merege Sort에서는, Merge의 대상이 되는 두 배열을 , 앞에서부터 비교해 나가며, Sorted 배열에 하나씩 채워나가야한다.
• 앞에서부터 비교하고, 이후, sorted에 sorted되지 않은 array를 처리하기 위해 C/C++에서는

int i=0,j=0,sorted=0; 
for(i,j;i<len_arr1 && j<len_arr2;){
	if(arr1[i]<arr2[j]) sortedArr[sorted++]=arr1[i++];
    	else sortedArr[sorted++]=arr2[j++]
}
if(i==len_arr1){
	for(;j<len_arr2;j++)
    	sortedArr[sorted++] = arr2[j];
}else{
	for(;i<len_arr1;i++)
    sortedArr[sorted++]=arr1[i];
    }

• Python에서는 이 부분을 while문으로 하면 되겠다.

python의 slicing

• built in sequence type에서 지원되는 slicing
• shallow copy of elements이다. 따라서, nested list의 경우 객체의 주소값을 복사하는 개념
  -->💥 동일 객체의 변경에 주의할 것.

python의 list 복사

new_list = old_list

--> reference 복사
new_list의 원소 변경 --> old_list에도 원소가 변경된다.

slicing이용한 복사 new_list = old_list[:]

t=[1,2,3,4]
new_list  = t[1:3]
print(new_list) #[2, 3]

• 이는 new_list를 만드는 경우 가능 . shallow copy를 한다는 것에 주의!
• slicing 은 list(instance)를 return한다

print(type(t[1:3])) # <class 'list'>

💥이런것도 가능하다!!! A list의 특정 구간을 B list의 특정구간으로 shallow copying

t=[1,2,3,4]
a= [66,77,88,99]
a[1:3] = t[1:3]
print(a) # [66, 2, 3, 99]

최종

my_list =[33,2,1,7,3453,546,2324]

Merge하며 Sort

my_list =[33,2,1,7,3453,546,2324]

# Merge하며 Sort
# ex . In case of (l,m,r) = (0,0,1) ,
def Merge(l,m,r):
    print("l , r "+str(l)+", "+str(r))
    arr_one = my_list[l:m+1]
    arr_two = my_list[m+1:r+1]
    arr_list =[arr_one,arr_two]

    sorted  = l
    i=0 # arr_one's index
    j=0 # arr_two's index


    ''' 
    yet_sorted__ : After comparing two array(arr_one,arr_two), ther's still not sorted array maybe. So to indicate information related to that arr . 
    flag 0 = arr_one,  1 = arr_two
    '''
    yet_sorted_flag =0
    yet_sorted_idx =0 # 뒤에서 setting, 단지 이런 변수의 존재를 알리기위함
    yet_sorted_len = len(arr_one)

    # l~m, m+1~r 를 비교해 나가며, 더 작은 것을 원본 list에 정렬 시켜나감.

    while (i<len(arr_one) and j<len(arr_two)):
        if(arr_one[i] < arr_two[j]) :
            my_list[sorted] = arr_one[i]
            i = i+1
        else:
            my_list[sorted] = arr_two[j]
            j=j+1
        sorted = sorted + 1

    # arr_one과 arr_two중 아직 sorted가 덜 끝난 것을 yet_sorted_flag에 setting시킨다
    # 아직 sorted가 덜끝난 arr의 index를 yet_sorted_idx에 setting시킨다.
    if(i == len(arr_one)):
        yet_sorted_flag =1
        yet_sorted_idx=j
        yet_sorted_len = len(arr_two)
    else:
        yet_sorted_idx=i
     #Copying remaining elements of arr_one or arr_two
    while(yet_sorted_idx<yet_sorted_len):
        my_list[sorted] = arr_list[yet_sorted_flag][yet_sorted_idx]
        sorted = sorted+1
        yet_sorted_idx=yet_sorted_idx+1


    print("my_list : " + str(my_list))



def MergeSort(l,r):
    print("MergeSort("+str(l)+","+str(r)+")")
    if l>=r:
        return
    else:
        m = int((l+r)/2);
        MergeSort(l,m);
        MergeSort(m+1,r);
        Merge(l,m,r);

MergeSort(0,len(my_list)-1)
print(my_list)

QuickSort

def quick_sort_py(array):
  # list가 하나 이하의 원소만을 담고 있다면 종료
  if len(array)<=1:
    return array
  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x<=pivot]
  right_side = [ x for x in tail if x>pivot]

  return quick_sort_py(left_sid) + [pivot]+quick_sort_py(right_side)
print(quick_sort_py(array))