[TIL][Mon] 정렬

학습한 사이트

https://leetcode.com/explore/learn/card/sorting

정렬의 기초

Inversion: 순서관계에서 벗어나 있는 한 쌍의 요소들

stability : 동일한 요소의 순서를 보장하는 특징

• 컴퓨터 과학의 정렬=정렬/순서 관계ordering relation이며, 이는 두가지 필수 속성들을 갖고 있어야 한다. ( **Law of Trichotomy, Law of Transitivity** )
  • If a < b and b < c, it must be true that a < c
  • It must be true that a < b or a = b or a > b
• 정렬은 순서관계에 기반해서 비순서관계의 요소들을 다시 일련의 순서가 있는 요소들로 재배치하는 것.
• Inversion은 이 순서 관계ordering relation에 벗어나 있는 한 쌍의 요소들을 말한다. 쉽게 말해 정렬된 것들 중간중간 보이는 삐끗한 애들.
• 따라서 정렬 알고리즘은 n개의 inversion이 있는 일련의 요소들이 주어질 때, 이 inversion을 0으로 줄이는 일련의 행위operation이라고 할 수 있다.
• 정렬 알고리즘의 안전성 stability of sorting algorithms 은 동일한 요소의 순서를 보장한다는 것이다. (The key feature of a stable sorting algorithm is that it will preserve the order of equal elements.)

inversion

[3,4,6,5,2] 에서 inversion은 몇 개나 존재하나?
>> (3>2)
>> (4>2)
>> (6>5)
>> (6>2)
>> (5>2)
#5

stable

[“hello”, “world”, “we”, “are”, “learning, “sorting”] #origin

(1) [“we”, “are”, “hello”, “world”, “sorting”, “learning”] #more stable
(2) [“we”, “are”, “world”, “hello”, “sorting”, “learning”]

#원문의 “hello”, “world”의 순서가 **(1)에서는 동일하게 유지**되었고 
#(2)에서는 바뀌었기 때문에 (1) 이 좀 더 **안정성이 있다**고 할 수 있다.   

정렬 관련하여 생각해야 하는 포인트!

• 정렬별 시간 복잡도
• 정렬별 공갑 복잡도

시간복잡도 공간복잡도 관련정렬

선택정렬	O(n^2)	O(1)
버블정렬	O(n^2)	O(1)
삽입정렬	O(n^2)	O(1)
힙 정렬			선택정렬

비교 기반 정렬 Comparison Based Sort

가장 기본적인 정렬.

선택정렬 selection sort

시간복잡도: O(n2) / 공간복잡도: O(1)

Selection sort will build up the sorted list by repeatedly finding 
the minimum element in that list and moving it to the front of the list through a swap. 
It will proceed to swap elements appropriately until the entire list is sorted.

선택 정렬은 리스트에서 가장 작은 원소를 반복해서 찾아내 스왑하여 앞으로 보내어 정렬한다. 스왑은 리스트가 적절하게 정렬될 때까지 계속된다.

[선택정렬] 시간복잡도

[선택정렬] 공간복잡도

O(1) : 알고리즘이 실행될 때 다른 추가 공간을 사용하지 않음.

장점

직관적이라 적기 쉽다.

단점

느리다.

[**4(*)**,2,3,4,1] 
# first round of selection sort
[1,2,3,4,]
# 정렬은 되지만, 원래 앞에 있었던 4(*)가 원래 뒤에 있던 4의 뒤로 가버린다.

stable하지 않다. 배열은 정렬 되지만, 동일 요소의 순서의 순서를 보장하지 않는다.(it does not preserve the ordering of equal elements.)

def selection_sort(data:list):
    for i in range(len(data)):
        min_index=i #set min idx
        for j in range(i+1, len(data)): #비교
            if data[j]<data[min_index]:
                min_index=j #update idx
        #swap
        data[min_index], data[i]= data[i], data[min_index]
    return data

버블정렬 bubble sort

시간복잡도: O(n^2) 공간복잡도 :O(1)

인접한 두 원소를 비교해가며 가장 큰 원소를 끝으로 보내는 과정을 n-1번 반복하는 알고리즘.

이를 시행하기 위해서 두개의 인접한 원소들을 동시에 비교하는 과정을 진행한다. 오름차순으로 정렬하고자 할 때, 선행원소가 후행원소보다 크다면 둘을 스왑하고 이러한 과정들은 다음의 인접한 원소들끼리 진행하여 모든 인접 원소의 세트를 교환한다. 전부 정렬될 때까지 이런 정렬을 계속한다.

At pass 1:
Number of comparisons = (N-1)
Number of swaps = (N-1)

At pass 2:
Number of comparisons = (N-2)
Number of swaps = (N-2)

At pass 3:
Number of comparisons = (N-3)
Number of swaps = (N-3)
.
.
.
At pass N-1:
Number of comparisons = 1
Number of swaps = 1

Now, calculating total number of comparison required to sort the array
= (N-1) + (N-2) +  (N-3) + . . . 2 + 1
= (N-1)*(N-1+1)/2  { by using sum of N natural Number formula }
= (N * (N-1)) / 2

In worst case, Total number of swaps = Total number of comparison
Total number of comparison (Worst case) = N(N-1)/2
Total number of swaps (Worst case) = N(N-1)/2

So worst case time complexity is O(N2) as N2 is the highest order term.

#공간복잡도 
원래 넣어진 배열 내에서 swap되므로 추가공간이 필요하지 않아 O(1)이다. 

code

#while을 사용하는 버블정렬
def bubble_sort(arr:list):
    has_swapped=True
    n=len(arr)
    while has_swapped: 
        has_swapped=False 
        #아래 반복문에서 스왑이 발생하지 않았다면 
        #그 다음 회전에서 while을 탈출한다.
        for i in range(n-1): 
            if arr[i]>arr[i+1]:
                arr[i],arr[i+1]=arr[i+1],arr[i]
                has_swapped=True
    return arr

#for을 사용하는 버블정렬
def bubble_sort(arr:list):
    n=len(arr)
    has_swapped=False 
    #전부 정렬되었는지 확인을 위한 용도
    # #한번 다 봤는데 정렬된 게 없다면 여전히 False가 되므로 끝내야 한다. 
    
    for i in range(n):
        # 마지막 i번째 요소는 이미 정렬이 완료된 상태.
        for j in range(0,n-i-1):
            if arr[j]> arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
                has_swapped=True
                   
        if not has_swapped:
            break
    return arr

data=[7,3,2,1,5,6,10,9,8]
y=bubble_sort(data)
print(y)

정렬 시작: [7, 3, 2, 1, 5, 6, 10, 9, 8]
0번째 swap/ arr:[3, 7, 2, 1, 5, 6, 10, 9, 8]
0번째 지나감/ arr:[3, 7, 2, 1, 5, 6, 10, 9, 8]
1번째 swap/ arr:[3, 2, 7, 1, 5, 6, 10, 9, 8]
1번째 지나감/ arr:[3, 2, 7, 1, 5, 6, 10, 9, 8]
2번째 swap/ arr:[3, 2, 1, 7, 5, 6, 10, 9, 8]
2번째 지나감/ arr:[3, 2, 1, 7, 5, 6, 10, 9, 8]
3번째 swap/ arr:[3, 2, 1, 5, 7, 6, 10, 9, 8]
3번째 지나감/ arr:[3, 2, 1, 5, 7, 6, 10, 9, 8]
4번째 swap/ arr:[3, 2, 1, 5, 6, 7, 10, 9, 8]
4번째 지나감/ arr:[3, 2, 1, 5, 6, 7, 10, 9, 8]
5번째 지나감/ arr:[3, 2, 1, 5, 6, 7, 10, 9, 8]
6번째 swap/ arr:[3, 2, 1, 5, 6, 7, 9, 10, 8]
6번째 지나감/ arr:[3, 2, 1, 5, 6, 7, 9, 10, 8]
7번째 swap/ arr:[3, 2, 1, 5, 6, 7, 9, 8, 10]
7번째 지나감/ arr:[3, 2, 1, 5, 6, 7, 9, 8, 10]
=====0번째 pass end===
0번째 swap/ arr:[2, 3, 1, 5, 6, 7, 9, 8, 10]
0번째 지나감/ arr:[2, 3, 1, 5, 6, 7, 9, 8, 10]
1번째 swap/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
1번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
2번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
3번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
4번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
5번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 9, 8, 10]
6번째 swap/ arr:[2, 1, 3, 5, 6, 7, 8, 9, 10]
6번째 지나감/ arr:[2, 1, 3, 5, 6, 7, 8, 9, 10]
=====1번째 pass end===
0번째 swap/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
1번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
2번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
3번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
4번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
5번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====2번째 pass end===
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
1번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
2번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
3번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
4번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====3번째 pass end===
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
1번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
2번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
3번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====4번째 pass end===
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
1번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
2번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====5번째 pass end===
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
1번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====6번째 pass end===
0번째 지나감/ arr:[1, 2, 3, 5, 6, 7, 8, 9, 10]
=====7번째 pass end===
=====8번째 pass end===
[1, 2, 3, 5, 6, 7, 8, 9, 10]

[버블정렬] 장점

stable하다. 상대적인 순서가 보장된다.

[버블정렬] 단점

느려서 실전엔 잘 사용되지 않는다.

삽입정렬 insertion sort

시간복잡도: O(n^2) / 공간복잡도 O(1)

순서에서 벗어난 요소들을 발견하면 지금까지 처리한 내용을 바탕으로 상대적으로 정확한 위치에 삽입될때까지 스왑하여 계속 위치를 바꿀 수 있다.

하나를 정렬하기 위해 모든 데이터를 비교하는 방식은 2차 시간의 복잡도가 나오고, 이중for문을 돌아야 한다.

[삽입정렬] 장점

시간복잡도가 O(n^2) 지만 이점이 여럿 있다. stable한 정렬로 목록의 뒷부분에 있는 요소를 목록의 앞부분에 있는 동일한 요소로 교체하지 않는다.

배열 크기에 비해 반전 횟수가 상대적으로 적은, 거의 정렬된 배열에서는 스왑 수가 낮아 빠르다.

**작은 배열(<15)**에 최선의 선택이 될 수 있다. 여러 정렬 기능들은 컬렉션의 크기를 확인하여 일정 값보다 낮으면 삽입정렬을 사용한다. (ex java)

[삽입정렬] 단점

반전inversion이 많은 대규모 컬렉션에서는 다른 정렬이 성능이 더 좋다.

def insertion_sort(arr):
    n=len(arr)
    for i in range(1,n):
        #현재 뽑아서 들고 있는 수를 key라는 변수에 담는다.
        key=arr[i]
        #안쪽 loop에서 사용할 반복제어변수를 j로 지정하고
        #현재 외부 루프에서 살펴보고있는 i를 넣는다.
        j=i
        while j>0 and arr[j-1]>key: 
						#key(arr[i])와 비교하여 key의 바로 앞에 있는 값(arr[j-1])이 크다면
            arr[j]=arr[j-1] #자리를 바꿔준다. (선행 원소가 후행 원소의 자리를 꿰찬다)
            j-=1            #j를 앞으로 이동한다.
        #j가 0보다 작거나
        #선행원소(arr[j-1])이 key보다 작다면
        #드디어 key가 갖고 있는 값이 들어갈 자리가 특정된다. 
        #내부 loop에서 역행하던 j는 
        #드디어 험난한 여정을 멈출 수 있다.
        arr[j]=key 
        #j가 가리키는 자리에 key를 넣어준다.
    return arr

같은 원리, 조금 더 쉬운 코드

def insertion_sort(arr):
    n=len(arr)
    #바깥쪽을 도는 for문
    #시작은 index =1부터.
    #선행원소들을 탐색하는 loop(while)가 바깥쪽 for문의 값과 비교하기 때문에 
    #while이 0을 살피기 떄문에 바깥쪽 for문의 i는 1부터 시작한다.
    for i in range(1,n):
        j=i
        #i를 기준으로 왼쪽(앞서 정렬된) 내부를 탐색하는 안쪽 loop
        #j-1(선행원소)가 크다면 
        #swap 해주고 j의 pointer를 앞(선행)으로 한칸 더 가본다.
        #j-1를 통해 앞서 정렬된 선행원소들을 역순으로 탐색하며
        #적절한 자리에 값을 넣어준다.  
        while j>0 and arr[j-1]>arr[j]:
            arr[j-1],arr[j]=arr[j], arr[j-1]
            j-=1
    return arr

---

여기까지는 시간복잡도가 O(n^2) 걸렸다. 왜? 바로 자기 옆에 있는 원소들과 비교를 하니까…N개의 원소들을 N-1개들 끼리 비교를 하다보니 그렇게 되는 모양이다.

---

여기서부턴 시간복잡도가 O(nlogN)걸리는 정렬들이 이어진다.

그런데 nlogN이 대체 뭘까? 간단하게 생각해서 길이가 N이라면 나누는 데 log2N**, 합치는 게** n번이라 nlogN이 된다.

ex. 리스트의 길이가 32라면 32log32, 즉 32*5=160이 된다.

힙 정렬 heap sort

1. bottom-up beatification (상향식 힙화)를 통해
2. 정렬되지 않은 배열로부터 힙을 만들고
3. 배열을 정렬하는데 힙을 사용한다

• 힙정렬에서는 전통적으로 max-heap을 사용한다.

그러면 그 heap을 어떻게 찾을까?

받은 배열을 binary tree, 이진트리화 하는 것이 바로 힙이란 자료구조인 모양이다. 이진트리에서는 부모와 자식 노드가 있는데, 만약 부모 노드가 i번째 index에 저장된다면, 그 아래 존재할 왼쪽의 자식 노드는 2i+1 번째 index에, 오른쪽 자식 노드는 2i+2에 저장된다. (여기서 index는 0부터 시작한다고 가정한다!)

max-heap으로 변환하는 과정

1. 배열의 끝에서부터 시작한다. (이진 트리의 아랫부분)
2. 어떤 노드에게는 두가지 경우가 존재한다.
   1. 자식노드들(왼쪽/오른쪽 노드들, 존재한다면.)보다 이 노드가 큰 경우(=현재 노드가 자식 노드들보다 더 큰 값을 가지고 있는 경우)
      1. 이 경우 다음 노드로 이동한다.(현재 배열 인덱스보다 하나의 인덱스 앞)
   2. 현재 노드보다 더 큰 값을 갖고 있는 자식 노드가 존재할 경우.
      1. 현재 노드와 자식 노드를 swap한다. (max-heap 속성을 위반하고 있으므로 수정한다!)
      2. 이 과정을 max-heap 속성을 더 위반하지 않을 때까지 반복한다.
3. 2번 과정을 상향식(아래에서 위로)으로 이진 트리에 있는 모든 노드에 걸쳐 수행한다.

#힙화 하는 함수 
def heapify(arr, N, i):
    #largest를 root로 초기화한다.
    largest=i #i는 index number
    l= 2*i+1 #left node
    r= 2*i+2 #right node
    
    #왼쪽 노드가 root보다 큰지 확인.
    if l<N and arr[largest]<arr[l]:
        largest=l 
        # 왼쪽 노드의 index number를 넣어준다. 
        # 이로써 arr[largest]를 호출하면 
        # 처음에 왼쪽 노드에 할당되었던 배열의 값이 들어갈 것이다.
    if r<N and arr[largest]<arr[r]:
        largest=r
    
    if largest!=i:#값이 바뀌었다면
        #실제 배열에서의 값들을 swap해준다.
        arr[i], arr[largest]=arr[largest], arr[i]
        
        #그리고 이 과정을 재귀로 반복한다. 
        heapify(arr, N, i)

핵심 포인트! 이 방식의 상향식으로 노드들을 처리함으로써, 모든 자식 노드들은 또한 힙이란 게 중요한 속성이다. 일단 우리가 ‘힙화’된 input을 가지고 있다면 이제 이 max-heap을 사용해 리스트를 정렬할 수 있게 된다.

heapfified된 값으로 input된 배열을 정렬하는 과정

1. index 0 에 있는 최대값(우린 이미 ‘힙화’를 통해 max-heap property를 만족하는 배열을 만들어서 root node=최대값 임을 알고 있다!)을 배열의 맨 끝에 있는 원소와 swap한다. 이 최대값은 ‘적합한’ 자리에 들어간 것이다. (오름차순 정렬을 만드는 것이 목적이니까)
2. 원소 한 개(가장 맨 끝에 있는 원소)가 정렬되었다. 이제 이 원소는 무시하고, heap 의 사이즈를 하나 줄이고 생략함으로써 배열에서 (제자리에 들어간) 최대값 원소를 배열에 놔둘 수 있다.
3. 남은 원소들은 이제 다시 새로운 힙이 되고, 두가지 경우가 존재한다…
   1. root 원소(=배열의 index 0)가 max-heap 속성을 위배한다.
      1. node를 자식이 더이상 max-heap 속성을 위배하지 않을 때까지 부모자식 노드를 swap한다.
   2. root원소가 max-heap 속성을 위배하지 않으면 4번으로 넘어간다.
4. 남은 정렬되지 않은 원소들을 대상으로 1번 과정을 반복한다. 모든 원소가 정렬될때까지 계속한다.

#힙소트함수        
def heap_sort(arr):
    N=len(arr)
    mid_num=N//2-1
    #maxheap을 제작
    for i in range(mid_num, -1, -1): 
        #배열의 정중앙 index에서 맨 마지막 원소까지, 역순으로 반복한다.
        heapify(arr, N, i)
    
    for i in range(N-1,0,-1):
        #배열의 맨 마지막 원소에서부터 첫번째 원소까지 역순으로 반복한다.
        #heap화 후 [0]에 있을 최대값을 맨 뒤로 보내는 것.
        #시작 i가 N-1이므로 맨 끝에 있는 요소와 swap한다는 뜻.
        arr[i],arr[0]=arr[0], arr[i] #swap 
        heapify(arr,i,0) #다시 호출.

[힙정렬] 장점 (중요!)

1. 선택정렬보다 더 좋은 점은 시간복잡도가 O(N log N) 이라는 점이다. 이 정렬에서 중요한 작업인 힙에서 최대 원소를 제거하는 작업이 O(logN) operation이기 때문에 가능하다. (나눈단 소리 같다)이건 가장 최악의 경우 N-1번 반복된다. in-place 힙화가 O(n) 작업이기 때문에 힙소트의 최악의 경우에 영향을 주지 않는다고 한다. (아직 무슨 말인지는 모르겠다.)

O(n) 의 시간복잡도? :How can building a heap be O(n) time complexity?

2.이 정렬 알고리즘은 제자리에서 수행할 수 있으므로 공간복잡도 측면에서 배열을 하나의 힙으로 다루고 여분의 메모리를 사용하지 않기 때문에 힙소트는 O(1)의 공간복잡도를 갖는다.(all operations are in-place),

[힙정렬] 단점

1. stable한 정렬이 아니다. (non stable)

2. 다른 O(nlogN)정렬에 비하여 성능이 떨어진다. (this algorithm performs worse than other O(nlogN) sorts as a result of bad cache locality properties.) (* 차후 공부할 것!)

3. 힙 정렬은 힙 내의 위치에 기반하여 요소를 스왑하므로 랜덤한 순서로 인덱스에 접근하는 많은 읽기 작업을 유발할 수 있고, 이것은 많은 **캐시 미스(**cache miss)를 유발하여 실질적인 성능 hit를 초래할 수 있다고 한다.(Heapsort swaps elements based on locations in heaps, which can cause many read operations to access indices in a seemingly random order, causing many cache misses, which will result in practical performance hits.)

selection sort(선택 정렬)과의 관계는?

가장 큰 원소를 뒤로 보내는 건 동일한데, 단순하게 매번 쭉 돌면서(O(n^2)) 알아내는지, 힙을 사용해 쪼개며 알아내는지가 다르다. 선택정렬은 최악의 경우 O(n2)의 성능을 내지만 힙정렬은 항상 O(nlogN)의 성능을 낸다. → 퀵정렬과도 뭔가 연관이 있는 모양인데?

[힙소트] 코드

based on leetcode

아래의 geeksforgeeks의 코드보다는 조금 더 보기 편한 코드인 듯 싶다.

def heap_sort(arr:list):
    
    def max_heapify(heap_size, idx):
        #set idxes
        largest=idx
        left=idx*2+1
        right=idx*2+2
        
        #check max-heap property rule
        if left<heap_size and arr[left]>arr[largest]:
            largest=left
        if right<heap_size and arr[right]>arr[largest]:
            largest=right
        if largest!=idx: #바뀌었을 때!
            arr[idx], arr[largest]=arr[largest], arr[idx] #실제 배열 값을 swap
            max_heapify(heap_size, largest) 
            #바꾼 값들이 또 최대힙 속성을 위반할 수 있음
            #그래서 똑같은 걸 재귀로 해결한다. 
            #전달하는 idx가 largest임을 생각해두기.
        
    #heapify orinal arr
    #1차 힙화
    n=len(arr)
    for i in range(n//2-1, -1, -1):
        max_heapify(n, i)
        #heap size는 배열의 길이.
    
    #남은 요소들 정렬에 heap사용하기 
    #하나씩 빼면서 반복한다. 
    #맨 뒤로 0에 있는 원소를 보내야 하고
    #힙 사이즈를 전달해주어야 하므로
    #역순으로 진행한다.
    for i in range(n-1,0,-1):
        arr[0], arr[i]=arr[i], arr[0]
        #힙 사이즈는 현재 i를
        #largest에 들어갈 idx는 0으로 지정
        #남은 요소들 중 index=0인 원소를 root로 지정하여 힙화
        max_heapify(i, 0)
        
    return arr
            
arr = [12, 11, 13, 5, 6, 7]
print(heap_sort(arr))

based on geeksforgeeks

#힙화 하는 함수 
def heapify(arr, N, i):
    #largest를 root로 초기화한다.
    largest=i #i는 index number
    l= 2*i+1 #left node
    r= 2*i+2 #right node
    
    #왼쪽 노드가 root보다 큰지 확인.
    if l<N and arr[largest]<arr[l]:
        largest=l 
        # 왼쪽 노드의 index number를 넣어준다. 
        # 이로써 arr[largest]를 호출하면 
        # 처음에 왼쪽 노드에 할당되었던 배열의 값이 들어갈 것이다.
    if r<N and arr[largest]<arr[r]:
        largest=r
    
    if largest!=i:#값이 바뀌었다면
        #실제 배열에서의 값들을 swap해준다.
        arr[i], arr[largest]=arr[largest], arr[i]
        
        #그리고 이 과정을 재귀로 반복한다. 
        heapify(arr, N, i)

#힙소트함수        
def heap_sort(arr):
    N=len(arr)
    mid_num=N//2-1
    #maxheap을 제작
    for i in range(mid_num, -1, -1): 
        #배열의 정중앙 index에서 맨 마지막 원소까지, 역순으로 반복한다.
        heapify(arr, N, i)
    
    for i in range(N-1,0,-1):
        #배열의 맨 마지막 원소에서부터 첫번째 원소까지 역순으로 반복한다.
        #heap화 후 [0]에 있을 최대값을 맨 뒤로 보내는 것.
        #시작 i가 N-1이므로 맨 끝에 있는 요소와 swap한다는 뜻.
        arr[i],arr[0]=arr[0], arr[i] #swap 
        heapify(arr,i,0) #다시 호출.
    
    # Driver's code
if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
 
    # Function call
    heap_sort(arr)
    N = len(arr)
 
    print("Sorted array is")
    for i in range(N):
        print("%d" % arr[i], end=" ")
# This code is contributed by Mohit Kumra