고급정렬 알고리즘(3) - 힙 정렬

이번에 소개할 힙(heap) 정렬은 자료구조에서도 배울 수 있는 트리(Tree)의 구조를 이용한 방법이다.

트리는 데이터들을 관리할 때 나무모양처럼 맨위 Root라는 최상위 계층부터 밑에있는 하위 계층까지 펼쳐지는 모양이라서 트리라는 이름이 붙여졌으며, 가장 큰 특징은 위에있는 하나의 노드밑에 또 다른노드가 추가가 된다면, 하나의 노드는 부모가되고 추가된 노드는 자식노드라 부른다. 이 자식노드는 부모노드보다 값이 커야하는 특성을 가지고 힙 정렬을 구현할 수 있다.

쉽게 연결리스트로 구현할 수 있으나, 힙 정렬에서 사용 할 트리는 왼쪽부터 차례로 쌓아가며 최대 두개의 노드를 가질 수 있는 이진트리(Binary Tree)라는것이라 가정하에 정렬을 하므로 연결리스트를 사용하지 않고 구현하도록 하겠다.

힙 정렬 구현은 밑의 3가지 방법을 잘 이용하면 된다.

 (1) 입력받은 N개의 값들을 힙의 특징인 트리구조로 변환시키기.

 (2) 루트 노드부터 차례로 데이터를 뽑아서 최하위 노드와 값을 바꾸기.

 (3) 정렬이 되기 전까지 과정(2)에서의 위치가 바뀐 root노드를 제외하고 과정(1)부터 

     반복 수행하기.

간단히 말해, 전체 데이터의 갯수 N개를 트리구조로 만들어주고 루트를 최하위 노드와 위치를 바꿔주고, N(정렬 할 값의 크기)-(과정1,2,3을)반복횟수만큼 다시과정(1)부터 시작해 과정(3)까지 실행한다면, 힙 정렬이 완성된다.

ex) 힙 정렬 (1) 힙 만들기  A = { 4, 7, 2, 5, 9, 3, 1 }

 " 각 과정은 " A배열 갯수 / 2 " 에 해당하는 A배열의 위치를 기준으로 힙의 형태가

   완성되며, 각 힙에서 자식노드와 부모노드의 위치를 바꿀 시 자식노드를 기준으로 

   재귀호출을 하도록 해야함.(위치가 변환했을경우, 부모노드가 자식노드보다 커야 하는
    트리의 형태를 유지하기 위해서) "

▶시작 전 [ 4, 7, 2, 5, 9, 3, 1 ]

트리 구조 만족 X

▶1회 과정 (기준 : 3번째)   // 전체 0~6개 이므로 6 / 2 = 3 이 기준이 됨.

자식노드가 존재하지 않으므로 변화 X 

▶2회 과정 (기준 : 2번째) 

노드 2번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기

                                      

▼

위치가 바뀐 노드(값 : 2)를 기준으로 자식노드가 존재하지 않으므로 재귀 X 

▶3회 과정 (기준 : 1번째) 

노드 1번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기

▼

위치가 바뀐 노드(값 : 7)를 기준으로 자식노드가 존재하지 않으므로 재귀 X 

▶4회 과정 (기준 : 0번째) 

노드 0번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기

▼

위치가 바뀐 노드(값 : 4)를 기준으로 자식노드가 존재하므로 자식과 크기비교(재귀호출)

▼

위치가 바뀐 노드(값 : 4)를 기준으로 자식노드가 존재하지 않으므로 재귀 X 

▶힙 만들기 완료  A = { 1, 5, 2, 7, 9, 3, 4 }

힙을 만들기 완료 하지만 정렬되지 않음

위의 예시를 통해서 부모노드가 자식노드보다 크다는 특성을 만족하도록 트리를 만들어 보았다. 여기서 최상단에 존재하는 루트(부모노드)에서부터 자식노드들 중 값이 가장 작은것을 뽑아내서 뒤에 노드들과 차례로 위치를 교환시키면 정렬을 만들 수 있다.

위의 예시를 이어서 정렬시켜보자.


ex) 힙 정렬 (2) 정렬  (루트와 자식노드와의 교환방식)

▶정렬 전 : { 1, 5, 2, 7, 9, 3, 4 }

트리의구조는 만족하지만, 정렬이되어 있지않음

▶1회 과정 (기준 : 6번째) 

최상단의 노드(루트)와 6번째의 위치를 교환

: 위치를 교환하면 트리구조가 깨져버리므로 다시 트리구조로 바꾸어 주어야 한다.

힙의 구조로 다시 변환시키기(1)

힙의 구조로 다시 변환시키기(2)

▶2회 과정 (기준 : 5번째) 

최상단의 노드(루트)와 5번째의 위치를 교환

힙의 구조로 다시 변환시키기(1)

: 노드 2번째의 값 4의 자식노드가 존재하지 않으므로 힙 특성 만족



▶3회 과정 (기준 : 4번째) 

최상단의 노드(루트)와 4번째의 위치를 교환

힙의 구조로 다시 변환시키기(1)

: 노드 2번째의 값 9의 자식노드가 존재하지 않으므로 힙 특성 만족



▶4회 과정 (기준 : 3번째) 

최상단의 노드(루트)와 3번째의 위치를 교환

힙의 구조로 다시 변환시키기(1)

: 노드 1번째의 값 7의 자식노드가 존재하지 않으므로 힙 특성 만족


▶5회 과정 (기준 : 2번째) 

최상단의 노드(루트)와 2번째의 위치를 교환

힙의 구조로 다시 변환시키기(1)

▶6회 과정 (기준 : 1번째)

최상단의 노드(루트)와 1번째의 위치를 교환

힙 정렬 완료 

▶완료
: A = { 9, 7, 5, 4, 3, 2, 1 };


위의 예시 2가지(힙 만들기, 정렬시키기)를 통해서 힙 정렬을 만들어 보았다.
그림에서는 트리의 특징(부모노드 값 < 자식노드 값)을 이용한다면 힙 정렬을 만들 수 있다는 것을
알 수 있다.

힙 정렬의 수행시간을 알아보자.
힙 정렬을 만들때 가장 중요한 특징 두 가지를 보면,

1) 힙을 만드는 수행시간                 ▶ log n에 비례  
: 힙을 만들때 절반[전체 크기 / 2]의 원소 갯수만큼 트리 특성에 맞도록 구현함.

2) 정렬을 시켜주는 수행시간           ▶ n에 비례
: 정렬 시 전체크기-1 만큼 정렬과정이 필요한데, 이때 루트노드(최상단노드)와의 자리를 바꾸는 정렬과정이 발생할때에 (1의 과정을)재귀 호출하여 다시한번 힙을 만족시켜야 하는 과정이 필요함.

병합, 퀵 정렬과 마찬가지로 힙 정렬또한 평균수행시간은 n log n이라는것을 알 수 있다.

알고리즘을 살펴보면,


▶실행 결과

고급정렬 알고리즘(2) - 퀵 정렬

이전에 분리작업 후 병합작업을 통해서 정렬을하는 병합정렬에 대해 알아보았다.

이때 분리작업에서 가장 끝을 기준원소로 정해서 진행했는데, 퀵 정렬 또한 기준원소가 핵심이 되며, 재귀를 통해 정렬이 이루어진다.

퀵 정렬은 기준원소를 전체 원소들의 크기와 비교하여 (정렬이 되도록)알맞은 위치에 넣어주고 기준원소보다 작은 원소들을 모아두는 형태를 가진다. 그리고 기준원소의 앞 뒤를 전반, 후반부로 나누어 이전의 작업(기준원소를 알맞은 위치에 넣어주고 그 값보다 작은 원소들을 모아두는 작업)을 각각 반복한다며 정렬이 되어가는 형태를 볼 수 있다.

예를들어, 

7, 4, 5, 2, 1, 3일 경우에 맨 뒤의 원소(3)를 기준원소로 가정해보자.

정렬 전  :   7, 4, 5, 2, 1, 3      → 기준원소 (3)

1회 과정을 거치면 2, 1, 3, 7, 4, 5가 된다.

아까 위에서 설명한 것처럼 기준원소 3이 전체의 원소들과의 비교를 통해 적절한 위치에 맞춰준것을 볼 수 있으며, 이 작업들을 통해서 기준원소보다 작은 원소들(2, 1)은 앞에, 큰 원소들(4, 5, 7)은 뒤에 위치하는 (전반부, 후반부로 나누는)과정을 볼 수 있다. 

그리고 전반부의 원소들과 후반부를 각각 맨 끝값을 기준원소로 가정해서 위의과정을

똑같이 이어가면 된다. 

1회 퀵 정렬 :  7, 4, 5, 2, 1, 3 

맨 끝이 3이 기준원소로 전반부(2, 1)와 후반부(4, 5, 7)로 나누어 진다.

자세히 살펴보면, 기준원소 3을 나머지 원소(7, 4, 5, 2, 1)와 차례로 비교하면서

작거나 같은 값을 앞의 원소(3보다 큰 원소이어야 함)부터 위치를 바꾸어주면 된다.

ex) 1회 퀵 정렬의 과정들

- 첫 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 첫 번째 7을 비교하면, 7이 더 크므로 그대로 둔다.

- 두 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 두 번째 4를 비교하면, 4가 더 크므로 그대로 둔다.

- 세 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 세 번째 5를 비교하면, 5가 더 크므로 그대로 둔다.

- 네 번째 비교    7, 4, 5, 2, 1, 3      -  Exchanged  ( 2, 4, 5, 7, 1, 3 )

  : 기준원소 3과 네 번째 2를 비교하면, 2가 더 작으므로 앞의 3보다 

    큰 값(7)과 자리 교환!

- 다섯 번째 비교 2, 4, 5, 7, 1, 3      -  Exchanged  ( 2, 1, 5, 7, 4, 3 )

  : 기준원소 3과 다섯 번째 1를 비교하면, 1이 더 작으므로 앞의 3보다 

    큰 값(4)과 자리 교환!

- 여섯 번째 비교 2, 1, 5, 7, 4, 3      -  Exchanged  ( 2, 1, 3, 7, 4, 5 )

  : 기준원소 3을 전체원소와 비교과정을 마쳤다면, 이제 3을 알맞은 위치에 넣어주어야

    하는데, 맨 앞의 3보다 큰 값(5)과의 자리를 바꾸어주면, 알맞은 위치에 들어가며

    퀵 정렬 1회 과정을 마친셈이다.

기준원소를 어떻게 이용하는지 위에서 살펴보았으며,

전반부와 후반부의 각각의 기준원소를 정해서 위의 과정과 같은 비교를 진행하면 된다.
1회 결과  :   2, 1, 3, 7, 4, 5

▶ 전반부 : 2, 1              → 기준원소 (1)

▶ 후반부 : 7, 4, 5           → 기준원소 (7)

2회 퀵 정렬 :  2, 1 

맨 끝의 1이 기준원소로 2보다 작으므로 앞으로보내면 된다.

2회 결과  :  1, 2

▶ 전반부 :  없음.            → 전반부 원소가 없으므로 진행  X

▶ 후반부 :  2                 → 후반부 원소가 하나이므로 굳이 진행할 필요가 없다.

3회 퀵 정렬 :  7, 4, 5 

맨 끝의 5가 기준원소로 5보다 작은 값 4는 전반부이며, 5보다 큰 7은 후반부가 된다.

3회 결과  :  4, 5, 7

▶ 전반부 :  4                → 전반부 원소가 하나이므로 굳이 진행할 필요가 없다.

▶ 후반부 :  7                → 후반부 원소가 하나이므로 굳이 진행할 필요가 없다.

이처럼 전반부, 후반부로 나누어가며 진행을 하고 각각의 기준원소를 

각 (전반 or 후반)부의 전체 원소들과 비교를 하면서 기준원소를 적절히 위치시키면 된다.

복잡해 보이지만.. 실제 업무에서 퀵 정렬은 효율성이 좋아서 실제 업무에서도 빈번히

사용된다.

그렇다면, 퀵 정렬의 수행시간은?

위에서 살펴본 퀵 정렬의 과정들은 크게 2개의 수행으로 나눌 수 있다.

1) 먼저 기준원소를 전체와 비교하는 수행시간             →  n에 비례

: n에 갯수에 따라서 기준원소를 전체와 비교하는 시간은 증가할 것이다. 그러므로,

  n의 수행시간이 걸린다.

2) 기준원소를 통해 전반, 후반으로 나누는 수행시간     →  log(n)에 비례

: 기준원소에 따라서 전반부와 후반부를 나눌 수 있으므로, log(n)의 수행시간이 걸린다.

이 두개의 과정을 합치면 n log(n)의 수행시간이 걸린다. 

이는 병합정렬의 수행시간과 거의 흡사하며 이전에 살펴본 기초적인 정렬알고리즘에서

삽입, 선택, 버블정렬의 수행시간보다는 더 뛰어난 수행시간을 갖는다. 하지만 이것은

평균적인 수행시간의 비교했을 경우라는 점을 꼭 잊지말자!

퀵 정렬의 알고리즘을 살펴보면,

▶실행결과

리눅스의 파일처리 - write()

리눅스의 파일의 내용을 저장하기 위해 read()함수를 사용해 cat명령과 동일한 결과를 만들어냈다. 이 뿐만 아니라 파일의 내용에 저장할 수 있는 기능인 write()를 소개하겠다.

write함수는 read함수와 다르게 파일의 내용에 새로운 데이터를 저장할 수 있으며, 수정, 덧붙이기 등 필요한 작업을 수행할 시 사용된다.

write()의 사용법

: write(파일 디스크립터, 추가할 데이터, 추가할 데이터의 크기);

ex_1) "hello world" 출력 (write함수 사용)

        ( test.txt파일에 hello라는 내용이 저장되어 있음 )

▶실행결과

ex_2) 파일 두개를 결합하여 새로운 파일생성하기

( hello.txt : hello라는 내용  /   world.txt : world라는 내용이 저장되어 있음 )

▶실행결과