무심코 사용하고 있는 용어들이 너무 햇갈린다...

라이브러리(Library)와 모듈(Module)

모듈의 의미는 구성 단위, 구성부분 이고 라이브러리는 도서관이라는 뜻을 가지고 있습니다. 개발에서는 라이브러리와 모듈을 동일한 의미라고 생각하면 됩니다. 자주 사용하게 되는 코드를 하나의 함수나 클래스라는 단위로 묶어서 코드를 재사용하게 됩니다. 즉, 이러한 함수 또는 클래스들을 모아서 라이브러리(library) 또는 모듈(module)이라 부릅니다. 라이브러리 또는 모듈은 개발자가 직접 만들 수도 있고 다른 사람이 만든 것을 설치받아 사용할 수도 있습니다. 다시 말해, 라이브러리와 모듈은 동일한 개념으로 재사용이 가능한 코드의 집합으로 볼 수 있습니다.

프레임워크(Framework)

라이브러리와 모듈을 공통적으로 사용하기 위한 부품이라 하면 프레임워크는 기본 뼈대라고 생각하면 됩니다. 개발자가 처음부터 모든 것을 개발을 할 수 있지만, 프레임워크를 사용하면 원하는 기능에만 집중하여 구현할 수 있습니다. 프레임워크 안에는 기본적으로 필요한 기능을 갖추고 있으므로 라이브러리(혹은 모듈)이 포함되어 있습니다.

백업과 아카이브는 엄연히 다른 기능입니다.

백업이란?

백업(Backup)은 데이터가 손상되거나 손실될 경우를 대비해 저장하는 데이터의 사본입니다. 원본 데이터는 백업을 생성한 후에도 지우지 않습니다. 백업의 예로 휴대폰의 사진을 클라우드에 복사하는 것부터 중요한 파일을 USB에 복사하는 등 다양합니다. 또한 파일 서버(비정형 데이터)와 데이터베이스(구조화 데이터)도 백업합니다. 이처럼 백업은 데이터를 그대로 복사하는 것에에 중점을 둡니다.

백업은 사고가 났을 때 데이터를 복원(Restore)하는 것입니다. 만약 휴대폰의 모든 사진을 클라우드로 백업했는데 휴대폰이 고장났으면 클라우드에 백업한 파일을 그대로 내려받아 사용할 수 있으며 서버 내 랜섬웨어가 걸렸다면 랜섬웨어 해결 후, 백업한 데이터를 받아 정상적으로 운영할 수 있습니다.

아카이브란?

아카이브(Archive)는 참고용으로 생성한 데이터 사본입니다. 종종 아카이브를 만든 후에는 원본 데이터를 지우기도 합니다. 백업의 목적이 어떤 것을 정상적인 상태로 되돌리는 것이라면, 아카이브는 여러 가지 목적이 있는데 보편적으로는 이전 데이터에서 일부 데이터를 찾는 것입니다. 예를 들어, 몇년 전에 고객이 서명한 계약서처럼 아주 중요한 내용을 담은 파일 하나를 찾는 것입니다.

또 하나의 데이터는 특정 시점을 증명할 수 있는 이메일이나 파일 같은 것입니다. 예를 들어, 3년간 홍길동이란 이름이 들어간 모든 메일을 찾는 행위입니다. 보통 데이터를 실시간 상태로 유지하고 싶어 하지만 데이터는 아카이브로 보존하며, 아카이브는 인덱스를 제공해 사용자는 오래된 콘텐츠에서 과거의 데이터를 되찾을 수 있도록 합니다. 일부 서버에서의 아카이브 시스템은 아카이브의 크기나 액세스 기간으로 아카이브를 삭제할 수 있습니다. 이러한 행동으로 시스템을 최적화하고 저장공간을 절약할 수 있습니다.

복원과 회수의 차이점

백업 시스템은 데이터를 복원(Restore)하고 아카이브 시스템은 데이터를 회수(Retrieval)합니다. 복원은 단일 파일이나 서버, 데이터베이스에 해당하는 경우가 대부분입니다. 하지만 뭔가를 회수한다고 하면, 보통은 관련 데이터 모음입니다. 이러한 데이터는 동일한 서버나 형식으로 저장되어 있지 않을 가능성이 큽니다.

복원은 특정 시점을 기준으로 이루어집니다. 예를 들어, 데이터베이스를 어제와 같은 상태로 복원하는 것입니다. 반면에 회수는 일정 시간대를 사용합니다. 예를 들어, 지난 3년 간의 모든 이메일과 같은 방식입니다. 복원을 하기 위해서는 데이터가 언제 어디에 저장되었는지 알아야 합니다. 1개라도 모를 경우 진행을 할 수 없습니다. 데이터가 있던 서버 이름부터 데이터베이스나 디렉토리를 알아야 하고, 복원하려는 파일 이름이나 테이블, 마지막으로 본 날짜와 시간도 알아야 합니다. 회수의 경우는 아카이브가 되어 있는 서버에서 찾고자 하는 특정 파라미터만 있으면, 파라미터와 일치하는 모든 데이터를 가져오면 끝납니다.

절차지향(Procedural Programming)이란?

절차지향 프로그래밍이란 물이 위에서 아래로 흐르는 것처럼 순차적인 처리가 중요시 되며 프로그램 전체가 유기적으로 연결되도록 만드는 프로그래밍 기법입니다. 대표적인 절차지향 언어에는 C언어가 있습니다. 이는 컴퓨터의 작업 처리 방식과 유사하기 때문에 객체지향 언어를 사용하는 것에 비해 더 빨리 처리되어 시간적으로 유리합니다. 옛날에는 하드웨어와 소프트웨어의 개발 속도차이가 크지 않았습니다. 하지만 소프트웨어 언어의 발달과 컴파일러의 발달로 하드웨어가 소프트웨어의 발달을 따라오지 못하는 상황이 발생했습니다. 이는 객체지향 언어가 등장하게 되는 계기로 작용했습니다. 객체지향 프로그래밍은 개발하려는 것을 기능별로 묶어 모듈화를 함으로써 하드웨어가 같은 기능을 중복으로 연산하지 않도록 하고, 모듈을 재활용하기 때문에 하드웨어의 처리양을 획기적으로 줄여주었습니다.

장점

  • 컴퓨터의 처리구조와 유사해 실행속도가 빠름

단점

  • 유지보수가 어려움
  • 실행 순서가 정해져 있으므로 코드의 순서가 바뀌면 동일한 결과를 보장하기 어려움
  • 디버깅이 어려움

객체지향(Object Oriented Programming)이란?

객체지향의 정의를 살펴보면 객체지향이란 실제 세계를 모델링하여 소프트웨어를 개발하는 방법입니다. 객체지향 프로그래밍에서는 데이터와 절차를 하나의 덩어리로 묶어서 생각하게 됩니다. 이는 마치 컴퓨터 부품을 하나씩 사다가 컴퓨터를 조립하는 것과 같은 방법입니다. 객체 지향의 3대 특성은 다음과 같습니다.

1. 캡슐화

  • 캡슐화란 관련된 데이터와 알고리즘(코드)이 하나의 묶음으로 정리된 것으로써 개발자가 만들었으며, 관련된 코드와 데이터가 묶여있고 오류가 없어 사용이 편리합니다. 데이터를 감추고 외부 세계와의 상호작용은 메소드를 통하는 방법인데, 라이브러리로 만들어 업그레이드하면 쉽게 바꿀 수 있습니다.
    • 메소드: 메시지에 따라 실행시킬 프로시저로서 객체지향 언어에서 사용되는 것. 객체지향 언어에서는 메시지를 보내 메소드를 수행시킴으로써 통신(communication)을 수행

2. 상속

  • 상속은 이미 작성된 클래스를 이어 받아서 새로운 클래스를 생성하는 기법으로 위에서 말한 기존 코드를 재활용해서 사용하는 것을 의미합니다. 객체지향 방법의 큰 장점중 하나입니다.

3. 다형성

  • 다형성이란 하나의 이름(방법)으로 많은 상황에 대처하는 기법입니다. 개념적으로 동일한 작업을 하는 함수들에 똑같은 이름을 부여할 수 있으므로 코드가 더 간단해지는 효과가 있습니다.

위의 특성들로 인해 생기는 객체지향 방법의 장점은 다음과 같습니다.

  •  신뢰성 있는 소프트웨어를 쉽게 작성할 수 있다. (개발자가 만든 데이터를 사용하기에 신뢰할 수 있다.)
  •  코드를 재사용하기 쉽다.
  •  업그레이드가 쉽다.
  •  디버깅이 쉽다.

이론적으로만 본다면 객체지향 언어는 절차지향 언어에 비해 장점이 많습니다. 하지만 프로그래밍을 할 때 항상 객체지향 언어만 사용하는 것은 아닙니다. 객체지향 언어는 어떤 모듈에 있는 하나의 기능만 필요하더라도 모듈 전체를 가져와야 하기 때문에 절차지향 프로그래밍보다 프로그램 사이즈가 더 커질 수도 있습니다. 또한 데이터에 대한 접근도 상대적으로 절차지향식보다 느려질 가능성이 많습니다. 메소드를 통해서만 접근이 가능하기 때문에 절차지향식처럼 특정 함수에 접근할 수 없고, 식으로만 접근이 가능해 속도적인 측면에서 불이익이 있습니다.

장점

  • 코드의 재활용성이 높음
  • 코딩이 절차지향보다 간편함
  • 디버깅이 쉬움

단점

  • 처리속도가 절차지향보다 느림
  • 설계에 많은 시간소요가 들어감

객체지향과 절차지향의 차이점

객체지향의 반대는 절차지향이 아니고 절차지향의 반대는 객체지향이 아닙니다. 위에서 설명한 것처럼 절차지향은 순차적으로 실행에 초점이 되어 있고 객체지향은 객체간의 관계/조직에 초점을 두고 있습니다. 이렇게 설명하면 객체지향은 절차적으로 실행되지 않냐? 라는 의문이 드는데 객체지향 역시 절차지향과 동일한 순서로 실행됩니다.



절차지향은 데이터를 중심으로 함수를 구현합니다. 이에 반해 객체지향은 기능을 중심으로 메서드를 구현하게 됩니다.
아래는 절차지향과 객체지향의 차이점 예시입니다.



someServiceCheck() {
    ...
    if (new Date().after(member.getExpirationDate()))) { ... } 
    ...
}



// Member의 일부
private Date expirationDate;
public Date getExpirationDate() {
    return expirationDate;
}
public void setExpirationDate(Date expDate) {
    expirationDate = expDate;
}

위 코드는 만료 여부를 확인하기 위해 member.getExpirationDate()로 만료일을 구합니다. 즉, someServiceCheck() 메서드는 member의 expirationDate 데이터를 사용하고 있습니다. 현재 시점에서 expirationDate 데이터는 someServiceCheck()와 Member가 공유하고 있습니다.

여기서 만료일을 1년 늘려주는 코드는 아래와 같이 구현됩니다.


renewContract() { Date date = member.getExpirationDate(); Date renewedDate = ... // date에 1년 더한 값 member.setExpirationDate(renewedDate); }

이제 Member의 expirationDate를 공유하는 함수는 someServiceCheck()와 renewContract()로 늘어났습니다. 여기서 Member는 객체가 아닙니다. Member는 객체라기 보다는 데이터를 담고 있는 구조체에 가깝습니다. 즉, 두 함수가 데이터를 공유하고 이를 기준으로 구현하는 전형적인 절차지향 방식입니다.

만료 여부를 확인하는 코드가 많아지거나 만료 데이터를 변경하는 코드가 많아질수록 expirationDate라는 데이터를 중심으로 함수를 구현하게 됩니다.


이렇게 절차 지향은 데이터를 중심으로 코드를 구현합니다. 개별 함수가 일부 기능을 구현하지만, 그 기능의 완성은 데이터 공유에 있습니다.절차 지향은 데이터를 중심으로 연관된 함수들을 묶어줍니다. 여기에 발생될 수 있는 문제점으로 예를 들어, 만료 없이 무한정 서비스를 받을 수 있다는 것을 표현하기 위해 expirationDate에 null을 할당하기로 했다고 가정합니다. 이 순간 데이터를 공유하는 모든 함수가 영향을 받습니다. 기존 코드에 null 검사를 추가해야 하고, null이면 에러가 아니라 만료일이 없도록 로직을 수정해야 되고 null 대신 9999년 12월 31일을 만료일자로 주기로 했다고 가정하면 남은 기간을 중심으로 환불 금액을 구하는 refund() 함수와 기타 만료일을 중심으로 중요 로직을 수행하는 코드들이 영향을 받게 됩니다.


객체 지향은 데이터 구조체가 아닌 기능을 중심으로 프로그램이 엮이게 됩니다. 예를 들어, Member를 구조체가 아닌 기능을 제공하는 객체로 바꾸면 다음과 같이 생성됩니다.


public class Member {
    private Date expirationDate;
    public boolean isExpired() {
        return new Date().after(expirationDate);
    }


    public int getRestDay() {
        ... //
    }


    public boolean renewContract() { // 데이터와 관련된 일부 기능이 객체로 들어옴
        .... //
    }
}

이제 다른 기능들은 만료 여부를 확인하기 위해 expirationDate 데이터를 사용하지 않고 Member가 제공하는 isExpired() 메서드를 사용합니다.


someServiceCheck() {
    ...
    if (member.isExpired())) { ... } 
    ...
}

계약 갱신 기능과 같이 일부 기능은 Member 안으로 들어가게 됩니다. 데이터와 밀접하게 연결된 기능을 데이터와 같은 객체의 기능으로 넣습니다. 이렇게 함으로써 객체의 내부 구현(특히 데이터)를 외부에 노출하지 않을 수 있습니다. 이를 캡슐화라 부릅니다.

기능 구현을 캡슐화하면 내부 구현 변경을 조금 더 쉽게 할 수 있습니다. Member 객체를 사용함으로써 만료 여부 로직을 변경할 때 다른 코드는 영향을 받지 않게 됩니다. 무한대로 사용할 수 있는 사용자의 만료 데이터를 null로 하든, 9999년 12월 31일로 하든, Member 객체를 사용하는 코드는 isExpired() 라는 기능을 사용하면 되기 때문입니다. 만료 데이터 저장 방식 때문에 영향을 받는 코드는 Member 객체 뿐이므로 변경이 수월해집니다.

자바나 C#과 같은 언어가 아니라 C와 같은 언어를 사용해도 객체 지향적으로 코딩할 수 있습니다. 핵심은 데이터 중심이 아닌 기능 중심으로 구현하는 것입니다. 즉, 여러 함수가 데이터를 공유하는 방식이 아니라 특정 함수가 다른 함수를 사용하는 방식으로 구현을 하고, 데이터 공유를 적절히 제한하면 캡슐화 효과를 얻을 수 있습니다.

요약

  • 절차지향은 데이터 중심, 객체지향은 기능 중심
  • 절차지향의 반대는 객체지향이 아니고 객체지향의 반대는 절차지향이 아님


Heap Sort

Heap

Tree에서의 Heap을 사용 (Max Heap 또는 Min Heap)

  • 따라서 complete binary tree 임
  • Max Heap일 때 parent node는 child node(subtree)의 key보다 무조건 큼
  • binary search tree가 아님
  • Tree의 Heap은 정렬을 위함이 아닌 Insert와 Delete를 위함
  • Max(Min) Heap의 내용은 Heap 에서 확인



1. Max(Min) Heap을 만든 다음 모든 데이터를 넣음

2. (Max Heap이라 할 때) 만든 heap tree에서 root node를 지우고 정렬하고자 하는 list에 지운 root node를 넣음

3. (Max Heap이라 할 때) heap tree를 재조정해서 루트를 결정한 다음, 다시 루트를 지우고 list에 해당 값을 넣음

4. 이 방식을 트리가 없어질 때 까지 진행

퍼포먼스

시간복잡도는 O(nlog₂n)

  • n은 트리의 노드 개수

Heap tree의 전체 높이가 log₂n(완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 Heap tree를 재구성하는데에 log₂n 만큼 소요됨

insertion 또는 deletion 하는 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 소요됨


저장공간이 적게 필요

  • Heap tree를 구성하는 공간만 필요함 (+ 정렬된 값을 저장하는 리스트)

빠르고 저장공간이 적게 필요하기에 임베디드 시스템에 유용

Quick Sort

정렬하고자 하는 값 중, 1개를 선택하고 선택된 값을 기준으로 작으면 왼쪽, 크면 오른쪽으로 나눈 다음 2개로 분할한 리스트에서 각 정렬한 후 합침.

  • 위와 같이 분할 후, 합치는 방식으로 divide and conquer 라고 부름

    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현

  • merge sort와 다르게 리스트를 균등하지 않게 분할함

Quick Sort 종류

  • Plain Quick Sort
  • Quick sort with randomized pivot
  • In-place quick sort


1. 정렬하고자 하는 리스트에서 값 1개를 선택 (선택한 값을 pivot이라 부름)

  • 보통 정렬하고자 하는 리스트의 가장 왼쪽, 중간 또는 가장 오른쪽을 선택

2. 다음 pivot을 중심으로 pivot 보다 작으면 왼쪽 pivot 보다 크면 오른쪽으로 분류 (divide)

3. 분류를 한 다음, 왼쪽과 오른쪽으로 분류된 값들 중, 각각 가장 왼쪽에 있는 수를 다시 pivot으로 잡고 다시 분류를 함.

  • 만약 수가 변하지 않으면 다음 수를 pivot으로 잡음
  • 가장 왼쪽에 있는 수가 바뀌었을 시, 해당 수를 pivot으로 잡고 다시 정렬

4. 더이상 정렬할 값이 없으면 분류한 값을 새로운 리스트에 담고 종료

예시


예시2


예시3

항상 마지막의 수를 선택

아래와 같은 방식이 in-place quick sort로 추가적인 저장공간이 필요없음

  • in-place : 입력된 리스트 내부에서 정렬이 일어남

예시4

상세 예시

6 3 8 7 9 2 1 5


pivot은 P, 왼쪽에서 시작하는 값은 L, 오른쪽에서 시작하는 값은 R이라 가정

L은 P보다 큰 값이 나올때까지 오른쪽으로 이동

R은 P보다 작거나 같은 값이 나올때까지 왼쪽으로 이동

L이나 R이 위 공식이 성립한다면 해당 값에 멈춤

  • L과 R이 전부 멈췄을 때 위치를 변경

R의 인덱스가 L보다 작아질 경우 P와 R 값의 위치를 변경

L과 R이 동일한 인덱스에 있을 경우, P와 R 값의 위치를 변경

pivot을 리스트의 가장 왼쪽 값을 선택하는 경우

1. 초기 값 세팅

6, 3, 8, 7, 9, 2, 1, 5

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

PL R

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

PㅤㅤL ㅤㅤ R

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

PL R

5. 두 값의 위치 변경

6, 3, 5, 1, 9, 2, 7, 8

PㅤㅤㅤL R

6. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 1, 9, 2, 7, 8

Pㅤㅤㅤㅤ L R

7. 두 값의 위치 변경

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ L R

8. 해당 위치부터 다시 2번내용

6, 3, 5, 1, 2, 9, 7, 8

Pㅤㅤㅤㅤ R L

9. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

2, 3, 5, 1, 6, 9, 7, 8

ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행 (왼쪽 먼저 진행)

2, 3, 5, 1, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

2, 3, 5, 1, 6, 9, 7, 8

P LR

3. 두 값의 위치 변경

2, 1, 5, 3, 6, 9, 7, 8

P LR

4. 해당 위치부터 다시 2번내용 수행

2, 1, 5, 3, 6, 9, 7, 8

P RㅤL

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 2, 5, 3, 6, 9, 7, 8

P


1. P의 위치가 변경 () 되었으므로 P의 양쪽 리스트에서 다시 P를 선택하여 재진행

  • 왼쪽에 값이 1개밖에 없으므로 오른쪽만 진행

1, 2, 5, 3, 6, 9, 7, 8

P R

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 5, 3, 6, 9, 7, 8

P R

L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 9, 7, 8

P



1. 처음 pivot을 6으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 9, 7, 8

PR

L

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 9, 7, 8

PㅤㅤR

ㅤㅤ L

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 8, 7, 9

P



P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

1, 2, 3, 5, 6, 8, 7, 9

P R

L

1. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 8, 7, 9

P R

L

2. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pivot을 리스트의 중간 값을 선택하는 경우

1. pivot을 리스트의 인덱스 중간으로 선택

6, 3, 8, 7, 9, 2, 1, 5

L ㅤPR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 8, 7, 9, 2, 1, 5

L PR

3. 두 값의 위치 변경

6, 3, 5, 7, 9, 2, 1, 8

ㅤ ㅤ L PR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 9, 2, 1, 8

P LR

5. 두 값의 위치 변경

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP LR

4. 해당 위치부터 다시 2번내용 수행

6, 3, 5, 7, 1, 2, 9, 8

ㅤㅤㅤㅤP ㅤ R L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

6, 3, 5, 2, 1, 7, 9, 8

ㅤㅤ ㅤㅤㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot을 리스트의 인덱스 중간으로 선택

6, 3, 5, 2, 1, 7, 9, 8

L PㅤR

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

6, 3, 5, 2, 1, 7, 9, 8

L ㅤ PㅤR

3. 두 값의 위치 변경

1, 3, 5, 2, 6, 7, 9, 8

L ㅤ PㅤR

4. 해당 위치부터 다시 2번내용 수행

1, 3, 5, 2, 6, 7, 9, 8

PR L

5. R의 인덱스가 L의 인덱스보다 커졌으므로 R과 P의 위치 변경

1, 3, 2, 5, 6, 7, 9, 8

ㅤㅤP


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • pivot 5의 우측 리스트는 값이 1개이므로 왼쪽만 진행

1, 3, 2, 5, 6, 7, 9, 8

L P R

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 3, 2, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 9, 8

P


1. P의 위치가 변경 () 되었으므로 P의 왼쪽 리스트에서 다시 P를 선택하여 재진행

  • 좌측의 경우 1, 2인데 1에 P와 R이 동일한 위치가 되므로 변경되는 값은 없음

1, 2, 3, 5, 6, 7, 9, 8

P L

R


1. 처음 pivot을 7으로 잡았을 때 기준으로 왼쪽은 모든 정렬이 완성됐으므로 오른쪽 진행

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

2. L이 P의 값보다 클때까지 왼쪽으로 이동, R은 P의 값보다 작거나 같을 때까지 오른쪽으로 이동

1, 2, 3, 5, 6, 7, 9, 8

P R

ㅤL

3. L이 오른쪽 리스트의 끝까지 이동하여 L과 R이 동일한 위치에 있으므로 P와 R의 위치 변경

1, 2, 3, 5, 6, 7, 8, 9

P


Quick Sort 완성

1, 2, 3, 5, 6, 7, 8, 9

pseudo code

위 예시를에 해당하는 코드 컨셉

int partition(int list[], int low, int high )
{
	int left, right; int pivot; int pivot_item;
	pivot_item = list[low];
	pivot = left = low;
	right = high;

	while ( left < right ) {
		/* Move left while item < pivot */ 
		while( list[left] <= pivot_item ) left++; 
		/* Move right while item > pivot */ 
		while( list[right] > pivot_item ) right--; 
		if ( left < right ) swap(&list[left],&list[right]);
	}
	
	/* right is final position for the pivot */
	list[low] = list[right];
	list[right] = pivot_item;
	
	return right;
}

퍼포먼스

시간복잡도는 O(n·log₂n) - worst case 제외

  • list의 개수인 n 번만큼 비교 x log₂n 실행

    log₂n 번 만큼 어떻게 실행?

    Quick Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


    따라서 n·log₂n


  • 시간복잡도가 worst case에서는 O(n²)까지 발생함

문제점


위와 같이 이미 정렬된 상태에서 가장 왼쪽의 값을 pivot으로 잡으면 시간복잡도가 O(n²)이 발생

  • O(n²)이 나오는 경우는 리스트에서 pivot을 가장 왼쪽이나 오른쪽을 잡을 때 발생함

해결책

  • 최악의 경우를 피하기 위해 pivot을 랜덤하게 선택
  • 3개의 pivot을 고른 후, median (중앙값)을 사용
  • Insertion Sort를 사용하여 확인
    • Insertion Sort는 규모가 작고 거의 정렬이 다된 리스트에서 효율적으로 동작

Merge Sort

Quick Sort와 마찬가지로 divide and conquer 


  • split: 주어진 리스트를 두개의 서브 리스트로 완벽하게 쪼갬
  • merge: 두개의 서브리스트를 정렬된 리스트에 합침


예시

예시2

상세 예시

6 5 3 1 8 7 2 4


Split


Merge

1. 6과 5를 비교하여 작은 수를 왼쪽, 큰 수를 오른쪽에 배치하여 길이가 2인 리스트에 저장

2. 나머지 값들도 동일하게 생성


3. [5, 6] 과 [1, 3] 에서 각 리스트의 값을 비교하여 작은 순서대로 길이가 4인 리스트에 저장


4. 나머지 리스트인 [7, 8] , [2, 4]도 동일한 로직으로 적용 

5. 두 리스트에 대해 위의 로직을 적용

6. 정렬 완성


퍼포먼스

O(nlog₂n) 만큼의 속도가 나옴

  • 리스트 내 키의 개수 n * 리스트를 쪼갠 뒤, 합치는 비용 log₂n

    log₂n 번 만큼 어떻게 실행?

    merge sort에서 split은 단순히 반씩 쪼개기 때문에 값의 비교나 각 단계별 비교한 값의 이동 연산이 수행되지 않음


    Merge Sort는 리스트를 반으로 쪼개나가는 형식. 최대 degree는 2라고 볼 수 있어서 binary tree라 볼 수 있다.

    더이상 쪼갤 수 없는 크기만큼 쪼갠다면 node는 1개만 가지게 되므로 위 그림처럼 트리의 높이만큼 실행이 됨. 따라서 트리의 높이 공식인 log₂n 번 만큼 쪼개 나간다는 것을 알 수 있음.

    n 번 만큼 어떻게 비교?

    위의 각 트리의 depth마다 리스트의 크기인 n번 만큼 비교가 일어남.


O(n)개의 저장공간이 필요함

merge sort는 stable sort라고 볼 수 있음

병렬처리가 가능함

external sorting에 적응력이 높음

어레이에 있는 키의 개수 n과 쪼개고 다시 합치는 데에 log₂n만큼 든다.

Stable Sort

서브로 정렬한 결과의 순서가 뒤바뀌지 않을 때 stable sort라 함

  • merge sort, insertion sort, bubble sort

다시 말해 {key:value} 쌍의 값들이 있을 때, 같은 키 값을 가지는 2개 이상의 데이터를 정렬할 때, 기존의 순서가 바뀌지 않으면 stable 이라 하고 아니라면 unstable이라 함

웹 페이지에서 특정 데이터의 정렬된 결과를 항상 동일하게 보여줘야 한다고 할 때, unstable sort는 보여주는 데이터와 연관 없는 데이터가 추가되어도 웹페이지를 새로고침 했을 때 순서가 계속 바뀔 수 있음.

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (2) 2018.08.17

대부분 정렬의 시간복잡도는 O(n·logn)와 O() 사이임

특별한 경우 O(n)까지 가능


Internal sorting - main memory 에서 일어나는 정렬

External sorting - secondary storage(하드디스크) 에서 일어나는 정렬

Bubble Sort

이웃되는 값끼리 비교하여 자리를 변경해나가는 방식

기본적으로 O(n²). 이미 정렬이 되어 있을 경우는 O(n)

예시

예시2

Selection Sort

array에서 가장 큰 수를 찾은 다음, 찾은 수를 어레이의 맨 끝인 n자리에 놓는다.

다음 큰수를 찾은 다음, 어레이의 n-1자리에 넣는다. 이때 찾은 수와 해당 자리에 있는 수의 자리를 바꾼다.

O(n²)의 performance가 나옴

  • bubble sort와 똑같이 O(n²)이지만 bubble sort에 비해 값의 교환 수가 적음

이미 정렬이 되어 있어도 O(n²)임

예시

예시2

Insertion Sort

새로운 키를 넣을 때, 정렬을 하고 있는 어레이에서 자신이 어디에 들어가야 할지 결정한 다음 맞는 자리에 넣는다.


performance: O(n²) 이미 모든 키가 정렬되어 있으면 O(n)

짧은 list에서 단순하고 좋음.
이미 부분적으로 정렬이 되어 있는 경우에 좋다

예시

예시2

Selection Sort vs Insertion Sort

Selection Sort는 정렬되어있지 않은 수를 전부 확인 해 가장 큰 수를 찾아야 함

  • 정렬이 전부 되어 있어도 모든 수를 비교

Insertion Sort는 정확한 위치에 들어가는 것을 결정하기 위해 정렬 중인 어레이를 확인 해야 함

  • 필요한 값만 읽고 정렬된 리스트에서 비교

n개의 element가 있다고 가정할 때, Selection은 n번만 쓰면 됨. 뒤에서부터 쓰기 때문에 어레이의 key들이 이동할 필요가 없지만, Insertion은 key들이 전부 이동할 수도 있기 때문에 write가 더 많이 일어남

  • 예를 들어, 2 3 4 5 1 의 값을 Insertion Sort로 정렬한다고 하면, 마지막 1을 정렬하기 위해 2 3 4 5 의 값이 한 칸씩 이동해야함

만약 write비용이 비쌀 경우 (예를 들어, flash memory) Insertion Sort보단 Selection Sort이 더 좋음

요약

  • bubble, selection, insertion sort의 시간복잡도 worst case는 O(n²)
  • 만약 전부 정렬된 리스트를 비교한다면 bubble, insertion sort는 O(n)이지만 selection은 여전히 O(n²)


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (2) 2018.08.17

Preorder

  • Visit the root.
  • Visit the left-subtree.
  • Visit the right-subtree.

Inorder

  • Visit the left-subtree.
  • Visit the root.
  • Visit the right-subtree.

Postorder

  • Visit the right-subtree.
  • Visit the left-subtree.
  • Visit the root.

Breadth First Search(BFS) or Level order traversals

  • starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Depth First Search(DFS)

예시


'공부 > 자료구조' 카테고리의 다른 글

Sorting (Heap, Quick, Merge Sort)  (0) 2018.09.30
Sorting (Bubble, Selection, Insertion Sort)  (0) 2018.09.30
트리 탐색 방법 (Tree traversal)  (0) 2018.09.28
Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)  (0) 2018.09.26
Graph  (0) 2018.09.26
AVL Tree  (2) 2018.08.17

+ Random Posts