[정렬알고리즘]퀵정렬 및 변수 할당 개념(python)

0. 당신의 개발공부에는 전혀 도움이 되지 않습니다. 

 

1. 퀵정렬 개요

 1) 이름처럼 웬만하면가장 빠른 정렬 방법이다.

 2) 분할정복 알고리즘이다.

 3) pivot을 정하여 양쪽을 비교하며 재귀적으로 정렬하는 방식이다.

 4) 상세한 원리는 다름 블로그에 자세히 설명이 되어 있어 참고하였다.

 

2. 코드

# 퀵 정렬 재귀함수 
def quick_sort(arr, left, right):
    pl = left # 첫번째 index 를 pl로 할당
    pr = right # 마지막 index를 pr로 할당 
    p = arr[(left+right) // 2] # 위 두개로 pivot을 계산해 리스트의 가운데 element를 p에 할당
    
    while pl <= pr: # 양끝점 두개가 붙꺼나 같아질때까지 반복해라
        while arr[pl] < p : pl += 1 # 리스트 제일 왼쪽 요소가 p보다 작은 것을 찾을때까지 pivot으로 이동, 발견하면 stop
        while arr[pr] > p : pr -= 1 # 리스트 제일 오른쪽 요소가 p보다 큰 것을 찾을때까지 pivot으로 이동, 발견하면 stop
        if pl <= pr : # 만약 이동하다가 pl과 pr이 만나거나 교차하게 되면
            arr[pl], arr[pr] = arr[pr], arr[pl] # pl과 pr의 위치를 바꿔라
            pl += 1 # 바뀐 pl은 +1
            pr -= 1 # 바뀐 pr은 -1
    # 교차된 후
    if left < pr : quick_sort(arr, left, pr) # 처음 pl(left)이 pr보다 작다면 처음 pl과 새로운 pr을 기준으로 다시 리스트를 만들어 재귀
    if pl < right : quick_sort(arr, pl, right) # 처음 pr(right)이 pl보다 크다면 처음 pr과 새로운 pl을 기준으로 다시 리스트를 만들어 재귀
    
quick_sort(N_list, 0, len(N_list)-1) # 함수로 보낼 element는 리스트, 0, 리스트의 길이-1
                                    # 0: 리스트의 첫번째 index, 리스트의 길이-1: 리스트의 마지막 index

 

3. 문제발생 및 해결(변수 할당 개념)

 1) 해당 함수는 리턴이 없다.

  - 기존에 N_list가 아닌 새로운 리스트에 할당하여 출력하려 했지만 되지않아 동기에게 조언을 구했다.

 2) 변수 할당의 개념 정리

  - 아래와 같이 코드를 작성하면 무엇이 출력될지 생각해보자

A = [1,2,3,4,5,6]
B = [0,9,8,7]

A2 = A
A2[1] = 30

print(A)

  - 정답은 [1, 2, 3, 4, 5, 6] 가 아닌 [1, 30, 3, 4, 5, 6] 가 출력 된다.

  - 좀더 찾아보니 위 코드에 A2=A는 A를 A2로 복사한다는 개념이 아닌 A의 주소가 A,A2 두개로 되었다고 생각 하면 된다. 

  - 집을 인테리어 한다고 집주소가 바뀌지 않는 것처럼 말이다. 

 3) 그렇다면 리스트를 복사할 방법은 없나? 있다. 많다. 많은 것중에 다음 예시만 정리한다.

A = [1,2,3,4,5,6]
B = [0,9,8,7]

A2=[x for x in A]

print(A)
print(A2)

  - for문으로 A의 모든 요소를 A2로 보냈고 이에 대한 출력값은 다음과 같다.

  - A = [1, 2, 3, 4, 5, 6], A2 = [1, 2, 3, 4, 5, 6]

  - 이렇게만 봤을때 잘 복사(?)되었는지 의심하는 나같은 사람을 위해 아래 코드보 보여 준다. 

A = [1,2,3,4,5,6]
B = [0,9,8,7]

A2=[x for x in A]

A2[1] = 30

print(A)
print(A2)
# 출력 [1, 2, 3, 4, 5, 6]
# 출력 [1, 30, 3, 4, 5, 6]

동기에게 감사하다.